Hamiltonian cycles in n-extendable graphs
Hamiltonian cycles in n-extendable graphs
复制标题
DOI：
10.1002/jgt.v40:2
复制
发表时间：
2002-06
影响因子：
0.9
通讯作者：
K. Kawarabayashi;K. Ota;Akira Saito
中科院分区：
文献类型：
--
作者：
K. Kawarabayashi;K. Ota;Akira Saito
称阶至少为2n+2的图G是n-可扩的，如果G有一个完美匹配，且每一组n条独立边都可扩到G中的一个完美匹配.证明了p阶连通n-可扩图的每对不相邻顶点x和y满足degGx + degGy ≥ p-n- 1，则G是Hamilton图或G同构于两个例外图之一.© 2002 Wiley Periodicals，Inc. J Graph Theory 40：75-82，2002
A graph G of order at least 2n+2 is said to be n-extendable if G has a perfect matching and every set of n independent edges extends to a perfect matching in G. We prove that every pair of nonadjacent vertices x and y in a connected n-extendable graph of order p satisfy degG x+degG y ≥ p - n - 1, then either G is hamiltonian or G is isomorphic to one of two exceptional graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 75–82, 2002