2003, Volume 5, Issue 11
Strategic Study of CAE >> 2003, Volume 5, Issue 11
A New Sufficient Conditions and Hamiltonian graphs
Department of Mathematics , Qiongzhou University, Wuzhishan, Hainan 572200, China
Next Previous
Abstract
Let G be a simple graph, δ and a be minimum degree and independence number of G, respectively, Faudree et al showed, in 1991, the Hamiltonian result with condition | N(x)∪ N(y) | ≥n-8. In 1993, Chen further considered the Hamiltonian with condition max |d{x) , d(y)| n/2 for each pair of non-adjacent vertices x , y with 1≤|N(x)∩NV(y)|≤a-l. In this paper a sufficient condition for a graph to be Hamiltonian graph is shown and the following result is obtained ： let G be a 2-connected graph of order n , if| N(x) U N(y) |≥ n-δ-1 for each pair of non-adjacent vertices x, y with 1≤ | N(x)∩ N(y) |α-1, then G is Hamiltonian or G∈{K(n-1)/2, (n + 1)/2, K2* V3K(n-2)/3}，This result generalizes some results in Hamiltonian graphs .
References
[ 1 ] SwamyMNS , ThulasiramanK .图论、网络与算法[M ].北京:高等教育出版社, 1988
[ 2 ] FanGH .Newsufficientconditionsforcyclesingraphs[J].JCombinTheorySerB 1984, 37:221～227
[ 3 ] ChenGT .Hamiltoniangraphsinvolvingneighborhoodintersections[J].DiscreteMath1993, 112:253～258
[ 4 ] FaudreeRJ , GouldRJ , JacobsonMS , etal.Neighborhoodunionsandhighlyhamiltongraphs[J].ArsCombinatoria, 1991, 31:139～148
[ 5 ] 尹家洪, 邻集并与hamiltonian性[J], 东南大学学报, 1991, 21:21～25
[ 6 ] 吴启迪.多变量系统的图论方法[M ].上海:同济大学出版社, 1995 link1
[ 7 ] Efe.Avariationonthehypercubewithdiameter[J].IEEETransonComputers, 1991, (11) :1312～1316
[ 8 ] 樊建席, 何力勤.BC互连网络及其性质[J].计算机学报, 2003, (1) :84～90 link1
京公网安备 11010502051620号
