Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-27T19:55:48.806Z Has data issue: false hasContentIssue false
  • English
  • Français

WIENER INDEX ON TRACEABLE AND HAMILTONIAN GRAPHS

Part of: Graph theory

Published online by Cambridge University Press:  30 August 2016

RUIFANG LIU ,
XUE DU  and
HUICAI JIA
RUIFANG LIU*
Affiliation:
School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, Henan 450001, China email [email protected]
XUE DU
Affiliation:
School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, Henan 450001, China email [email protected]
HUICAI JIA
Affiliation:
College of Science, Henan Institute of Engineering, Zhengzhou, Henan 451191, China email [email protected]
*
✉[email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We give sufficient conditions for a graph to be traceable and Hamiltonian in terms of the Wiener index and the complement of the graph, which correct and extend the result of Yang [‘Wiener index and traceable graphs’, Bull. Aust. Math. Soc.88 (2013), 380–383]. We also present sufficient conditions for a bipartite graph to be traceable and Hamiltonian in terms of its Wiener index and quasicomplement. Finally, we give sufficient conditions for a graph or a bipartite graph to be traceable and Hamiltonian in terms of its distance spectral radius.

Keywords

complementtraceable graphHamiltonian graphquasicomplementbipartite graphWiener indexdistance spectral radius

MSC classification

Primary: 05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)
Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 94 , Issue 3 , December 2016 , pp. 362 - 372
Copyright
© 2016 Australian Mathematical Publishing Association Inc. 

References

Bondy, J. A. and Murty, U. S. R., Graph Theory, Graduate Texts in Mathematics, 244 (Springer, New York, 2008).Google Scholar
Indual, G., ‘Sharp bounds on the distance spectral radius and the distance energy of graphs’, Linear Algebra Appl. 430 (2009), 106–113.Google Scholar
Karp, R. M., ‘Reducibility among combinatorial problems’, in: Complexity of Computer Computations (eds. Miller, R. E. and Thatcher, J. M.) (Plenum, New York, 1972), 85–103.CrossRefGoogle Scholar
Kuang, M. J., Huang, G. H. and Deng, H. Y., ‘Some sufficient conditions for Hamiltonian property in terms of Wiener-type invariants’, Proc. Math. Sci. 126 (2016), 1–9.CrossRefGoogle Scholar
Li, R., ‘Wiener index and some Hamiltonian properties of graphs’, Int. J. Math. Soft Comput. 5 (2015), 11–16.CrossRefGoogle Scholar
Liu, Z. Z., Lin, S. S. and Yang, G. Q., ‘Distance spectral radius and Hamiltonicity’, J. Huizhou Univ. 33 (2013), 40–43.Google Scholar
Liu, R. F., Shiu, W. C. and Xue, J., ‘Sufficient spectral conditions on Hamiltonian and traceable graphs’, Linear Algebra Appl. 467 (2015), 254–266.Google Scholar
Ning, B. and Ge, J., ‘Spectral radius and Hamiltonian properties of graphs’, Linear Multilinear Algebra 63 (2014), 1520–1530.Google Scholar
Wiener, H., ‘Structural determination of paraffin boiling points’, J. Amer. Chem. Soc. 69 (1947), 17–20.CrossRefGoogle ScholarPubMed
Yang, L., ‘Wiener index and traceable graphs’, Bull. Aust. Math. Soc. 88 (2013), 380–383.CrossRefGoogle Scholar