三类特殊图的超欧拉指数
The Supereulerian Indices of Three Types of Special Graphs
DOI: 10.12677/AAM.2025.145261, PDF,    科研立项经费支持
作者: 马兴忠, 安子瑜：青海民族大学数学与统计学院，青海 西宁
关键词: 迭代线图；超欧拉指数；鲨鱼图；花鲨图；Thomassen图；Iterated Line Graph； Supereulerian Index； Snark Graph； Flower Snark Graph； Thomassen Graph
摘要: 1997年，Boesch、 Suffel 和Tindell 提出了超欧拉问题。 Pulleyblank随后证明，即使在平面 图中，确定图是否是超欧拉图也是NP-完全的。 超欧拉指标作为超欧拉问题的研究内容之一，也 是很多学者关注的焦点。 在这篇文章中，我们主要研究了三类特殊图的超欧拉指数，得到了鲨鱼图(Snark graph)、 花鲨图(Flower Snark graph)和Thomassen图的超欧拉指数都为1。 这也 为我们进一步研究一般图的超欧拉指数提供了方法。
Abstract: 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.
文章引用：马兴忠, 安子瑜. 三类特殊图的超欧拉指数[J]. 应用数学进展, 2025, 14(5): 319-327. https://doi.org/10.12677/AAM.2025.145261

参考文献

[1] Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. Macmillan and Else- vier.
[2] Boesch, F.T., Suffel, C. and Tindell, R. (1977) The Spanning Subgraphs of Eulerian Graphs. Journal of Graph Theory, 1, 79-84.
https://doi.org/10.1002/jgt.3190010115
[3] Pulleyblank, W.R. (1979) A Note on Graphs Spanned by Eulerian Graphs. Journal of Graph Theory, 3, 309-310.
https://doi.org/10.1002/jgt.3190030316
[4] Catlin, P.A. (1992) Supereulerian Graphs: A Survey. Journal of Graph Theory, 16, 177-196.
https://doi.org/10.1002/jgt.3190160209
[5] Lai, H.J., Shao, Y.H. and Yan, H.Y. (2013) An Update on Supereulerian Graphs. World Scientific and Engineering Academy and Society Transaction on Mathematics, 12, 926-940.
[6] Chen, Z. (2016) Snarks, Hypohamiltonian Graphs and Non-Supereulerian Graphs. Graphs and Combinatorics, 32, 2267-2273.
https://doi.org/10.1007/s00373-016-1718-7
[7] Li, X.M., Lei, L., Lai, H. and Zhang, M. (2014) Supereulerian Graphs and the Petersen Graph. Acta Mathematica Sinica, English Series, 30, 291-304.
https://doi.org/10.1007/s10114-014-2272-y
[8] Lai, H., Li, H., Shao, Y. and Zhan, M. (2010) On 3-Edge-Connected Supereulerian Graphs. Graphs and Combinatorics, 27, 207-214.
https://doi.org/10.1007/s00373-010-0974-1
[9] Harary, F. and Nash-Williams, C.S.J.A. (1965) On Eulerian and Hamiltonian Graphs and Line Graphs. Canadian Mathematical Bulletin, 8, 701-709.
https://doi.org/10.4153/cmb-1965-051-3
[10] Chartrand, G. and Wall, C.E. (1973) On the Hamiltonian Index of a Graph. Studia Scientiarum Mathematicarum Hungarica, 8, 43-48.
[11] Bertossi, A.A. (1981) The Edge Hamiltonian Path Problem Is NP-Complete. Information Processing Letters, 13, 157-159.
https://doi.org/10.1016/0020-0190(81)90048-x
[12] Saraˇzin, M.L. (1994) A Simple Upper Bound for the Hamiltonian Index of a Graph. Discrete Mathematics, 134, 85-91.
https://doi.org/10.1016/0012-365x(94)p2679-9
[13] Xiong, L.M. and Yan, H.Y. (2005) On the Supereulerian Index of a Graph. Journal of Beijing Institute of Technology, 14, 453-457.
[14] Han, L., Lai, H., Xiong, L. and Yan, H. (2010) The Chv´atal-Erd¨os Condition for Supereulerian Graphs and the Hamiltonian Index. Discrete Mathematics, 310, 2082-2090.
https://doi.org/10.1016/j.disc.2010.03.020
[15] Xiong, L.M. and Li, M.C. (2010) Supereulerian Index Is Stable under Contractions and Clo- sures. Ars Combinatoria, 97, 129-142.

为你推荐