首页 | 本学科首页   官方微博 | 高级检索  
     检索      


An <Emphasis Type="Italic">s</Emphasis>-Hamiltonian Line Graph Problem
Authors:Zhi-Hong Chen  Hong-Jian Lai  Wai-Chee Shiu  Deying Li
Institution:(1) Butler University, Indianapolis, IN 46208, USA;(2) West Virginia University, Morgantown, WV 26506, USA;(3) Hong Kong Baptist University, Hong Kong, China;(4) School of Information, Renmin University of China, Beijing, People’s Republic of China
Abstract:For an integer k > 0, a graph G is k-triangular if every edge of G lies in at least k distinct 3-cycles of G. In (J Graph Theory 11:399–407 (1987)), Broersma and Veldman proposed an open problem: for a given positive integer k, determine the value s for which the statement “Let G be a k-triangular graph. Then L(G), the line graph of G, is s-hamiltonian if and only L(G) is (s + 2)-connected” is valid. Broersma and Veldman proved in 1987 that the statement above holds for 0 ≤ sk and asked, specifically, if the statement holds when s = 2k. In this paper, we prove that the statement above holds for 0 ≤ s ≤ max{2k, 6k − 16}.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号