%0 Journal Article
%T 三类特殊图的超欧拉指数
The Supereulerian Indices of Three Types of Special Graphs
%A 马兴忠
%A 安子瑜
%J Advances in Applied Mathematics
%P 319-327
%@ 2324-8009
%D 2025
%I Hans Publishing
%R 10.12677/AAM.2025.145261
%X 1997年,Boesch、 Suffel 和Tindell 提出了超欧拉问题。 Pulleyblank随后证明,即使在平面 图中,确定图是否是超欧拉图也是NP-完全的。 超欧拉指标作为超欧拉问题的研究内容之一,也 是很多学者关注的焦点。 在这篇文章中,我们主要研究了三类特殊图的超欧拉指数,得到了鲨鱼图(Snark graph)、 花鲨图(Flower Snark graph)和Thomassen图的超欧拉指数都为1。 这也 为我们进一步研究一般图的超欧拉指数提供了方法。
Boesch, Suffel and Tindell in 1997 proposed the supereulerian problem. Pulleyblank subsequently proved that determining whether a graph is supereulerian, even within planar graphs, is NP-complete. The supereulerian index, as one of the research topics of the supereulerian problem, is also a focal point of interest for many scholars. In this paper, we mainly study the supereulerian indices of three types of special graphs and obtain that the supereulerian index of the snark graph, the flower Snark graph and the thomassen graph are both 1. This also provides a method for us to further study the supereulerian indices of general graphs.
%K 迭代线图,超欧拉指数,鲨鱼图,花鲨图,Thomassen图
Iterated Line Graph
%K Supereulerian Index
%K Snark Graph
%K Flower Snark Graph
%K Thomassen Graph
%U http://www.hanspub.org/journal/PaperInformation.aspx?PaperID=115339