[1]熊黎明,朱倩倩.关于哈密尔顿指数的综述[J].江西师范大学学报(自然科学版),2014,(03):229-235.
 XIONG Li-ming,ZHU Qian-qian.The Hamiltonian Index of a Graph---A Survey[J].Journal of Jiangxi Normal University:Natural Science Edition,2014,(03):229-235.
点击复制

关于哈密尔顿指数的综述()
分享到:

《江西师范大学学报》(自然科学版)[ISSN:1006-6977/CN:61-1281/TN]

卷:
期数:
2014年03期
页码:
229-235
栏目:
出版日期:
2014-06-30

文章信息/Info

Title:
The Hamiltonian Index of a Graph---A Survey
作者:
熊黎明;朱倩倩
北京理工大学数学与统计学院,北京,100081
Author(s):
XIONG Li-ming;ZHU Qian-qian
关键词:
迭代线图哈密尔顿指数类哈密尔顿指数
Keywords:
iterated line graphhamiltonian indexhamiltonian-like index
分类号:
O157.6
文献标志码:
A
摘要:
图G的线图L( G)是指以G的边集E( G)为顶点集且L( G)的2个顶点邻接当且仅当它们在G中有公共顶点。 n次迭代线图Ln(G)递归地定义为L0(G)=G,Ln(G)=L(Ln-1(G))(n∈N={0,1,2,…}),其中L1( G)=L( G)并且假设Ln-1( G)非空,使得Ln( G)是哈密尔顿的最小整数n称为哈密尔顿指数,用h( G)表示。该文综述了(类)哈密尔顿指数的一些结果。
Abstract:
Let G be a simple graph. The line graph L( G)of a graph G is a graph which has E( G)as its vertex set and two vertices are adjacent in L( G)if and only if they share an end vertex in G. The n-th iterated line graph Ln(G)is defined recursively by L0(G)=G,Ln(G)=L(Ln-1(G))(n∈N={0,1,2,…}),where L1(G)=L(G) and Ln-1( G)is assumed to be nonempty. The hamiltonian index of a graph G,denoted by h( G),is the smallest in-teger n such that Ln(G)is hamiltonian. The results of hamiltonian(like)indices of graphs have been summaric-zed.

参考文献/References:

[1] Bondy J A,Murty U S R.Graph theory with applications [M].New York:American Elsevier,1976.
[2] Clark L H,Wormald N C.Hamiltonian-like indices of graphs [J].Ars Combinatoria,1983,15:131-148.
[3] Harary F,Nash-Williams C St J A.On Eulerian and Hamiltonian graphs and line graphs [J].Canad Math Bull,1965,8(6):701-709.
[4] Chartrand G,Wall C E.On the Hamiltonian index of a graph [J].Studia Sci Math Hungar,1973,8:43-48.
[5] Xiong Liming,Liu Zhanhong.Hamiltonian iterated line graphs [J].Discrete Math,2002,256(1/2):407-422.
[6] Sarazin M L.A simple upper bound for the Hamiltonian index of a graph [J].Discrete Math,1994,134(1/2/3):85-91.
[7] Xiong Liming,Broersma H J,Li Xueliang,et al.The Hamiltonian index of a graph and its branch-bonds [J].Discrete Math,2004,285(1/2/3):279-288.
[8] Yi Hong,Lin Jianliang,Tao Zhisui,et al.The Hamiltonian index of graphs [J].Discrete Math,2009,309(1):288-292.
[9] 熊黎明,刘展鸿,易桂生.Super-Euler迭代线图的特征刻划 [J].江西师范大学学报:自然科学版,2000,24(2):107-110.
[10] Xiong Liming,Yan Huiya.On the supereulerian index of a graph [J].Journal of Beijing Institute of Technology,2005,14(5):453-457.
[11] Gould R,Hynds E.A note on cycles in 2-factors of line graphs [J].Bull ICA 1999,26:46-48.
[12] Ferrara M,Gould R,Hartke S.The structure and existence of 2-factors in iterated line graphs [J].Discussiones Mathematicae:Graph Theory,2007,27(3):507-526.
[13] Xiong Liming,Li Mingchu.On the 2-factor index of a graph [J].Discrete Math,2007,307(21):2478-2483.
[14] Xiong Liming.The existence of even factors in iterated line graphs [J].Discrete Math,2008,308(23):5891-5894.
[15] Sabir Eminjan,Vumar Elkin.Spanning connectivity of the power of a graph and Hamiltonian connected index of a graph [J].Graphs and Combinatorics(to appear).DOI:10.1007/s00373-013-1362-4.
[16] Garey M R,Johnson D S,Tarjan R E.The planar Hamiltonian circuit problem is NP-complete [J].SIAM J Comput,1976,5(4):704-714.
[17] Bertossi A A.The edge Hamiltonian path problem is NP-complete [J].Inform Process Lett,1981,13(4/5):157-159.
[18] Ryjácek Z,Woeginger G J,Xiong Liming.Hamiltonian index is NP-complete [J].Discrete Applied Math,2011,159(4):246-250.
[19] Lai Hongjian.On the Hamiltonian index [J].Discrete Math,1988,69(1):43-53.
[20] Xiong Liming.The Hamiltonian index of a graph [J].Graphs Combin,2001,17(4):775-784.
[21] Xiong Liming,Wu Quxin.The Hamiltonian index of a 2-connected graph [J].Discrete Math,2008,308(24):6373-6382.
[22] Holub P.Forbidden subgraphs and the Hamiltonian index of a 2-connected graph [EB/OL].Ars Combin.
[2014-03-12].http://www.combinatorialmath.ca/arscombinatoria/toc.html.
[23] Han Longsheng,Lai Hongjian,Xiong Liming,et al.The Chvátal-Erdös condition for supereulerian graphs and the Hamiltonian index [J].Discrete Math,2010,310(15/16):2082-2090.
[24] Chen Zhihong,Lai Hongjian,Xiong Liming,et al.Hamilton-connected indices of graphs [J].Discrete Math,2009,309(14):4819-4827.
[25] Zhang Lili,Shao Yehong,Chen Guihai,et al.s-vertex pancyclic index [J].Graphs and Combinatorics,2012,28(3):393-406.
[26] Xiong Liming,Ryjácek Z,Broersma H J.On stability of the Hamiltonian index under contractions and closures [J].Journal of Graph Theory,2005,49(2):104-115.
[27] 王丽娜,熊黎明.闭无爪图在圈闭包运算下哈密尔顿指数的稳定性 [J].应用数学学报,2010,33(3):424-431.
[28] Saito A,Xiong Liming.Closure,stability and iterated line graphs with a 2-factor [J].Discrete Math,2009,309(16):5000-5010.
[29] Xiong Liming,Li Mingchu.Supereulerian index is stable under contractions and closures [J].Ars Combinatoria,2010,97:129-142.

备注/Memo

备注/Memo:
国家自然科学基金(11071016;11171129);教育部博士点基金(20131101110048)
更新日期/Last Update: 1900-01-01