Wiener index and traceable graphs

DOI10.1017/S0004972712000901MaRDI QIDQ2872004zbMATH OpenFDO

Authors Lihui Yang

Publication date 14 January 2014

Published in Bulletin of the Australian Mathematical Society (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/S0004972712000901

zbMATH Keywords

degree sequencetraceable graphWiener index

Mathematics Subject Classification ID

Vertex degrees (05C07) Distance in graphs (05C12) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Applications of graph theory (05C90)

Review text

The Wiener number \(W(G)\) of a connected graph \(G\) is a well-known distance-based chemical index, which is defined as the sum of distances between all pairs of vertices in \(G\). A graph is called traceable if it has a path including all vertices. Applying Chvátal's degree condition for a graph to be traceable [\textit{V. Chvátal}, J. Comb. Theory, Ser. B 12, 163--168 (1972; Zbl 0213.50803)], this short paper obtained a new sufficient condition in terms of the Wiener number: For a simple connected graph of order \(n\geq 4\), if \(W(G)\leq (n+5)(n-2)/2\), then \(G\) is traceable unless \(G\) is isomorphic to \(K_1+(K_{n-3}\cup 2K_1)\) or \(K_2+(3K_1\cup K_2)\) or \(K_4+6K_1\).

Recommendations

• Wiener index on traceable and Hamiltonian graphs
• Wiener index and Harary index on Hamilton-connected and traceable graphs.
• Measures of traceability in graphs
• Wiener index, Harary index and Hamiltonicity of graphs
• Wiener index, hyper-Wiener index, Harary index and Hamiltonicity properties of graphs

Cites work

• Wiener index of trees: Theory and applications

Cited in

(20)

• Wiener index and Harary index on Hamilton-connected graphs with large minimum degree
• Reciprocal degree distance and graph properties
• On sufficient topological indices conditions for properties of graphs
• Wiener index, Harary index and graph properties
• Computing Wiener and hyper-Wiener indices of zero-divisor graph of \(\mathbb{Z}_{g^3}\times\mathbb{Z}_{\mathfrak{I}_1\mathfrak{I}_2}\)
• The first Zagreb index, reciprocal degree distance and Hamiltonian-connectedness of graphs
• Some sufficient conditions on \(k\)-connected graphs
• Hosoya and Harary polynomials of \(TOX(n)\), \(RTOX(n)\), \(TSL(n)\) and \(RTSL(n)\)
• Some sufficient conditions for Hamiltonian property in terms of Wiener-type invariants
• Wiener index on traceable and Hamiltonian graphs
• Wiener-type invariants on graph properties
• Distance and eccentricity based invariants of windmill graph
• Some topological indices and graph properties
• Distance and eccentricity based polynomials and indices of m-level wheel graph
• On the pancyclicity of 1-tough graphs
• Wiener-type invariants and Hamiltonian properties of graphs
• Wiener index and vulnerability parameters of graphs
• Sufficient conditions for k-leaf-connected graphs in terms of the first Zagreb index, the reciprocal degree distance and the forgotten topological index
• Reciprocal degree distance and Hamiltonian properties of graphs
• Several graph properties in terms of the multiplicative version of the first Zagreb index

This page was built for publication: Wiener index and traceable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2872004)