|
|
三类特殊图的超欧拉指数
|
Abstract:
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.
| [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. |
