Complete solution to a conjecture of Zhang-Liu-Zhou

Document Type: Research Paper

Authors

1 Ferdowsi University of Mashhad

2 University of Kashan

Abstract

‎‎Let $d_{n,m}=\big[\frac{2n+1-\sqrt{17+8(m-n)}}{2}\big]$ and‎ ‎$E_{n,m}$ be the graph obtained from a path‎ ‎$P_{d_{n,m}+1}=v_0v_1 \cdots v_{d_{n,m}}$ by joining each vertex of‎ ‎$K_{n-d_{n,m}-1}$ to $v_{d_{n,m}}$ and $v_{d_{n,m}-1}$‎, ‎and by‎ ‎joining $m-n+1-{n-d_{n,m}\choose 2}$ vertices of $K_{n-d_{n,m}-1}$‎ ‎to $v_{d_{n,m}-2}$‎. ‎Zhang‎, ‎Liu and Zhou [On the maximal eccentric‎ ‎connectivity indices of graphs‎, ‎Appl‎. ‎Math‎. ‎J‎. ‎Chinese Univ.‎, ‎in‎ ‎press] conjectured that if $d_{n,m}\geqslant 3$‎, ‎then $E_{n,m}$‎ ‎is the graph with maximal eccentric connectivity index among all‎ ‎connected graph with $n$ vertices and $m$ edges‎. ‎In this note‎, ‎we‎ ‎prove this conjecture‎. ‎Moreover‎, ‎we present the graph with‎ ‎maximal eccentric connectivity index among the connected graphs‎ ‎with $n$ vertices‎. ‎Finally‎, ‎the minimum of this graph invariant‎ ‎in the classes of tricyclic and tetracyclic graphs are computed‎.

Keywords

Main Subjects

References

D. B. West (1996). Introduction to G raph Theory. Prentice Hall, Inc., Upper Saddle River, NJ.
V. Sharma, R. Goswami and A. K. Madan (1997). Eccentric connectivity index: a novel highly discriminating topological descriptor for structure property and structure activity studies. J. Chem. Inf. Comput. Sci.. 37, 273-282
A. R. Ashrafi, T. Doslic and M. Saheli (2011). The eccentric connectivity index of TUC4 C8 (R) nanotubes. MATCH Commun. Math. Comput. Chem.. 65 (1), 221-230
A. R. Ashrafi, M. Saheli and M. Ghorbani (2011). The eccentric connectivity index of nanotubes and nanotori. J. Comput. Appl. Math.. 235, 4561-4566
G. Yu, L. Feng and A. Ilic (2011). On the eccentric distance sum of trees and unicyclic graphs. J. Math. Anal. Appl.. 375, 99-107
B. Zhou and Z. Du (2010). On eccentric connectivity index. MATCH Commun. Math. Comput. Chem.. 63, 181-198
A. Ilic and I. Gutman (2011). Eccentric connectivity index of chemical trees. MATCH Commun. Math. Comput. Chem.. 65, 731-744
M. J. Morgan, S. Mukwembi and H. C. Swart (2011). On the eccentric connectivity index of a graph. Discrete Math.. 311, 1229-1234
T. Doslic, M. Saheli and D. Vukicevic (2010). Eccentric Connectivity Index: Extremal Graphs and Values. Iranian J. Math. Chem.. 1 (2), 45-56
J. Zhang, Z. Liu and B. Zhou (in press). On the maximal eccentric connectivity indices of graphs. Appl. Math. J. Chinese Univ..
Transactions on Combinatorics

Volume 3, Issue 4
December 2014
Pages 55-58

Files

Share

How to cite

Statistics