A Note on Edge-Disjoint Hamilton Cycles in Line Graphs

详细信息    查看全文

• 作者：Hao Li ; Weihua He ; Weihua Yang ; Yandong Bai
• 关键词：Hamilton cycle ; Edge ; disjoint Hamilton cycles ; Line graph
• 刊名：Graphs and Combinatorics
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：32
• 期：2
• 页码：741-744
• 全文大小：358 KB
• 参考文献：1.Alspach, B., Bermond, J.-C., Sotteau, D.: Decomposition into cycles I: Hamilton decompositions. In: Hahn, G., et al. (eds.) Cycles and rays, pp. 9–18. Norwell, MA (1990)CrossRef
  2.Bondy, J.A., Murty, U.S.R.: Graph theory with applications. American Elsevier, New York (1976)CrossRef MATH
  3.Harary, S.L., Nash-Williams, CStJA: On eulerian and hamiltonian grahs and line graphs. Can. Math. Bull. 8, 701–710 (1965)CrossRef MathSciNet MATH
  4.Jaeger, F.: A note on subeulerian graphs. J. Graph Theory 3, 91–93 (1979)CrossRef MathSciNet MATH
  5.Kundu, S.: Bounds on the number of edge-disjoint spanning trees. J. Combin Theory 7, 199–203 (1974)CrossRef
  6.Lai, H.-J.: Every 4-connected line graph of a planar graph is hamiltonian. Graphs Combin 10, 249–253 (1994)CrossRef MathSciNet MATH
  7.Lai, H.-J., Shao, Y., Zhan, M.: Every 4-connected line graph of a quasi claw-free graph is hamiltonian connected. Discrete Math 308, 5312–5316 (2008)CrossRef MathSciNet MATH
  8.Lai, H.-J., Shao, Y., Wu, H., Zhou, J.: Every 3-connected, essentially 11-connected line graph is Hamiltonian. J. Combin. Theory Ser. B 96, 571–576 (2006)CrossRef MathSciNet MATH
  9.Lai, H.-J., Xiong, L., Yan, H., Yan, J.: Every 3-connected claw-free \(Z_8\) -free graph is Hamiltonian. J. Graph Theory 64, 1–11 (2010)CrossRef MathSciNet MATH
  10.Lai, H.-J., Shao, Y., Yu, G., Zhan, M.: Hamiltonian connectedness in 3-connected line graphs. Discrete Appl. Math. 157(5), 982–990 (2009)CrossRef MathSciNet MATH
  11.Nash-Williams, CStJA: Edge-disjoint spanning trees of finite graphs. J. London Mtah. Soc. 36, 445–450 (1961)CrossRef MathSciNet MATH
  12.Ryjáček, Z.: On a closure concept in claw-free graphs. J. Combin. Theory Ser. B 70, 217–224 (1997)CrossRef MathSciNet MATH
  13.Ryjáček, Z., Vrána, P.: Line graphs of multigraphs and Hamilton-connectedness of claw-free graphs. J. Graph Theory 66, 152–173 (2011)CrossRef MathSciNet MATH
  14.Tutte, W.T.: On the problem of decomposing a graph into \(n\) connected factors. J. London Math. Soc. 36, 221–230 (1961)CrossRef MathSciNet MATH
  
• 作者单位：Hao Li (1) (2)
  Weihua He (1) (3)
  Weihua Yang (4)
  Yandong Bai (1)
  
  1. Laboratoire de Recherche en Informatique, UMR 8623, C.N.R.S.-Université Paris-sud, 91405, Orsay cedex, France
  2. Institute for Interdisciplinary Research, Jianghan University, Wuhan, China
  3. Department of Applied Mathematics, Guangdong University of Technology, Guangzhou, China
  4. Departement of Mathematics, Taiyuan University of Technology, Taiyuan, China
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Engineering Design
  
• 出版者：Springer Japan
• ISSN：1435-5914

文摘

It is well known that if a graph G contains a spanning closed trail, then its line graph L(G) is Hamiltonian. In this note, it is proved that if a graph G with minimum degree at least 4k has k edge-disjoint spanning closed trails, then L(G) contains k edge-disjoint Hamilton cycles.