Closures, cycles, and paths
Closures, cycles, and paths
复制标题
闭包、循环和路径
DOI：
10.1002/jgt.20584
复制
发表时间：
2012
影响因子：
0.9
通讯作者：
I. Schiermeyer
中科院分区：
文献类型：
--
作者：
J. Harant;A. Kemnitz;Akira Saito;I. Schiermeyer
1960年，Ore证明了如下定理：设G是n阶图。若对每对不相邻的顶点u和v，d（u）+ d（v）≥n，则G是Hamilton的.从那时起，对于其他几个图形属性，已经获得了类似的充分度条件，即所谓的“Ore型度条件”。在[R. J. Faudree，R. H. Schelp，A.斋藤和我。Schiermeyer，Discrete Math 307（2007），873-877]，Faudree等人加强了Ore定理如下：他们确定了度和小于n的不相邻顶点对的最大数量（即违反Ore条件），但仍然意味着图是哈密尔顿的。在这篇文章中，我们证明了对于其他一些图的性质，相应的Ore-型度条件也可以被加强。这些图的性质包括可迹图、哈密尔顿连通图、k叶连通图、泛圈图和具有两个分量的2因子的图。计算图闭包来显示这些结果。© 2011 Wiley Periodicals，Inc. J Graph Theory 69：314-323，2012
In 1960 Ore proved the following theorem: Let G be a graph of order n. If d(u) + d(v)≥n for every pair of nonadjacent vertices u and v, then G is hamiltonian. Since then for several other graph properties similar sufficient degree conditions have been obtained, so‐called “Ore‐type degree conditions”. In [R. J. Faudree, R. H. Schelp, A. Saito, and I. Schiermeyer, Discrete Math 307 (2007), 873–877], Faudree et al. strengthened Ore's theorem as follows: They determined the maximum number of pairs of nonadjacent vertices that can have degree sum less than n (i.e. violate Ore's condition) but still imply that the graph is hamiltonian. In this article we prove that for some other graph properties the corresponding Ore‐type degree conditions can be strengthened as well. These graph properties include traceable graphs, hamiltonian‐connected graphs, k‐leaf‐connected graphs, pancyclic graphs, and graphs having a 2‐factor with two components. Graph closures are computed to show these results. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 314–323, 2012
DOI：
--
发表时间：
2007
期刊：
Discrete Mathematics Vol.307
影响因子：
--
作者：
R.J. Faudree;A. Saito;R.H. Schelp;I. Schiermeyer
通讯作者：
I. Schiermeyer