No Detail Found!

On the pancyclicity of 1-tough graphs

Author(s)
Rao Li Department of Mathematical Sciences, University of South Carolina Aiken,Aiken, SC 29801,USA
Abstract
Let G be a graph of order n 6r 2, size e, and minimum degree r, where r is an integer greater than 1. The main result obtained in this note is that if G is 1-tough with the degree sequence (d1; d2; ; dn) and if e ((n r)(n r 1)+r(2r 1))=2, then G is pancyclic, Hamiltonian bipartite, or Hamiltonian such that d1 = d2 = = dk = k, dk+1 = dk+2 = = dn k+1 = n k 1, and dn k+2 = dn k+3 = = dn = n 1, where k < n=2. This result implies that the following conjecture of Hoa, posed in 2002, is true under the conditions n 40 and 7: every path-tough graph on n vertices and with at least ((n 6)(n 7) + 34)=2 edges is Hamiltonian. Using the main result of this note, additional sufficient conditions for 1-tough graphs to be pancyclic are also obtained.
Publication Details
Page(s) 1-4
Published Journal: Discrete Mathematics Letters, Volume: 5, Issue: 0, Year: 2021

Request the full text from PASTIC

Keywords
pancyclic graph, 1-tough graph, Hamiltonian graph
References
Bondy J. A.,Murty U. S. R. .1976 .. Graph Theory with Applications, : .
Chva V. .1973 .´ tal, Tough graphs and Hamiltonian circuits. Discrete Math. 5, : 215-228.
Dankelmann P.,Niessen T.,I. Schiermeyer T. .1994 .On path-tough graphs. SIAM J. Discrete Math. 7, : 571-584.
Feng L. .2009 .On three conjectures involving the signless Laplacian spectral radius of graphs. Publ. Inst. Math, 85 : 35-38.
Fiedler M. .1973 .. , 23 : 298-305.
Hoa V. D. .2002 .Conditions for Existence of Hamiltonian Cycles in Path-Tough Graphs. Sep. 7 - Sep. 10, : .
Hoa C. T. .1995 .` ng, Hamiltonian degree conditions for tough graphs. , 142 : 121-139.
Hong Y. .1988 .A bound on the spectral radius of graphs. Linear Algebra Appl, 108 : 135-139.
Hua H.,Wang M. .2013 .On Harary index and traceable graphs. MATCH Commun. Math. Comput. Chem, 70 : 297-300.
Ivanciuc O.,Balaban T. S.,Balaban A. T. .1993 .Reciprocal distance matrix, related local vertex invariants and topological indices. J. Math. Chem, 12 : 309-318.
D. Plavsˇic Z. .1993 .Mihalic´, On the Harary index for the characterization of chemical graphs. J. Math. Chem, 12 : 235-250.
Wiener H. .1947 .Structural determination of paraffin boiling points. J. Am. Chem. Soc, 69 : 17-20.
Yang L. .2013 .Wiener index and traceable graphs. Bull. Aust. Math. Soc, 88 : 380-383.
0

Citations

0

Downloads

16

Views