A degree sum condition for graphs to be prism hamiltonian

详细信息    查看全文

• 作者：Kenta Ozeki
• 关键词：Degree sum ; ; none ; color ; black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4VG35R5-1&_mathId=mml7&_user=10&_cdi=5632&_pii=S0012365X09000065&_rdoc=8&_issn=0012365X&_acct=C000050221&_version=1&_userid=
• 刊名：Discrete Mathematics
• 出版年：2009
• 出版时间：6 July 2009
• 年：2009
• 卷：309
• 期：13
• 页码：4266-4269
• 全文大小：362 K

文摘

Win, in 1975, and Jackson and Wormald, in 1990, found the best sufficient conditions on the degree sum of a graph to guarantee the properties of “having a k-tree” and “having a k-walk”, respectively. The property of “being prism hamiltonian” is an intermediate property between “having a 2-tree” and “having a 2-walk”. Thus, it is natural to ask what is the best degree sum condition for graphs to be prism hamiltonian. As an answer to this problem, in this paper, we show that a connected graph G of order n with σ₃(G)≥n is prism hamiltonian. The degree sum condition “σ₃(G)≥n” is best possible.