On the average eccentricity‎, ‎the harmonic index and the largest signless Laplacian eigenvalue of a graph

Document Type: Research Paper

Authors

1 College of Mathematics and Computer Science, Hunan Normal University, Changsha, Hunan 410081, P. R. China

2 Department of Mathematics, School of Humanities and Sciences,SASTRA University, Thanjavur, India

Abstract

The eccentricity of a vertex is the maximum distance from it to‎ ‎another vertex and the average eccentricity $ecc\left(G\right)$ of a‎ ‎graph $G$ is the mean value of eccentricities of all vertices of‎ ‎$G$‎. ‎The harmonic index $H\left(G\right)$ of a graph $G$ is defined‎ ‎as the sum of $\frac{2}{d_{i}+d_{j}}$ over all edges $v_{i}v_{j}$ of‎ ‎$G$‎, ‎where $d_{i}$ denotes the degree of a vertex $v_{i}$ in $G$‎. ‎In‎ ‎this paper‎, ‎we determine the unique tree with minimum average‎ ‎eccentricity among the set of trees with given number of pendent‎ ‎vertices and determine the unique tree with maximum average‎ ‎eccentricity among the set of $n$-vertex trees with two adjacent‎ ‎vertices of maximum degree $\Delta$‎, ‎where $n\geq 2\Delta$‎. ‎Also‎, ‎we‎ ‎give some relations between the average eccentricity‎, ‎the harmonic‎ ‎index and the largest signless Laplacian eigenvalue‎, ‎and strengthen‎ ‎a result on the Randi'{c} index and the largest signless Laplacian‎ ‎eigenvalue conjectured by Hansen and Lucas \cite{hl}‎.

Keywords

Main Subjects


[1] Y. Chen, Prop erties of sp ectra of graphs and line graphs, Appl. Math. J. Ser. B, 3 (2002) 371-376.

[2] D. Cvetkovic, P. Rowlinson and S. K. Simic, Eigenvalue b ounds for the signless Laplacian, Publ. Inst. Math. (Beograd) (N. S), 81 (95) (2007) 11-27.

[3] P. Dankelmann, W. Go ddard and C. S. Swart, The average eccentricity of a graph and its subgraph, Util. Math., 65 (2004) 41-51.

[4] H. Deng, S. Balachandran, S. K. Ayyaswamy and Y. B. Venkatakrishnan, On the harmonic index and the chromatic numb er of a graph, Discrete Appl. Math., 161 (2013) 2740-2744.

[5] H. Deng, S. Balachandran, S. K. Ayyaswamy and Y. B. Venkatakrishnan, On harmonic indices of trees, unicyclic graphs and bicyclic graphs, ARS Combinatoria , CXXX (2017) 239-248.

[6] A. A. Dobrynin, R. C. Entringer and I. Gutman, Wiener index of trees: Theory and applications, Acta Appl. Math., 66 (2001) 211-249.

[7] Z. Du and A. Ilic, On AGX conjectures regarding average eccentricity, MATCH Commun. Math. Comput. Chem., 69 (2013) 597-609.

[8] S. Fa jtlowicz, On conjectures of Graffiti-I I, Cong. Numer., 60 (1987) 187{197.

[9] O. Favaron, M. Mahio and J. F. Sacle, Some eigenvalue prop erties in graphs (Conjectures of Graffiti-II), Discrete Math., 111 (1993) 197-220.

[10] L. Feng and G. Yu, On three conjectures involving the signless Laplacian sp ectral radius of graphs, Publ. Inst. Math. (Beograd) (N.S), 85 (99) (2009) 35-38.

[11] P. Hansen, C. Lucas, Bounds and conjectures for the signless Laplacian index of graphs, Linear Algebra Appl., 432 (2010) 3319-3336.

[12] P. Hansen, D. Vukicevic, Variable neighb orho o d search for extremal graphs. 23. On the Randic index and the chromatic numb er, Discrete Math., 309 (2009) 4228-4234.

[13] A. Ilic, Note on the harmonic index of a graph, Arxiv preprint arXiv: 1204.3313, (2012).

[14] A. Ilic, Eccentric connectivity index, Novel Molecular Structure Descriptors-Theory and Applications II, Univ. Kragujevac, Kragujevac, 2010 139-168.

[15] A. Ilic and I. Gutman, Eccentric connectivity index of chemical trees, MATCH Commun. Math. Comput. Chem., 65 (2011) 731{744.

[16] M. K. Khalifeh, H. Youse -Azari, A. R. Ashra and S. G. Wagner, Some new results on distance-based graph invariants, European J. Combin., 30 (2009) 1149-1163.

[17] M. J. Morgan, S. Mukwembi and H. C. Swart, On the eccentric connectivity index of a graph, Discrete Math., 311 (2011) 1229-1234.

[18] V. Sharma, R. Goswami and A. K. Madan, Eccentric connectivity index: A noval highly discriminating top ological descriptor for structure-prop erty and structure-activity studies, J. Chem. Inf. Comput. Sci., 37 (1997) 273-282.

[19] Y. Tang and B. Zhou, On average eccentricity, MATCH Commun. Math. Comput. Chem., 67 (2012) 405-423.

[20] R. Wu, Z. Tang and H. Deng, A lower b ound for the harmonic index of a graph with minimum degree at least two, Filomat, 27 (1) (2013) 49-53.

[21] R. Wu, Z. Tang and H. Deng, On the harmonic index and the girth of a graph, Utilitas Math., 91 (2013) 65-69.

[22] L. Zhong, The harmonic index for graphs, Appl. Math. Lett., 25 (2012) 561-566.

[23] B. Zhou and Z. Du, On eccentric connectivity index, MATCH Commun. Math. Comput. Chem., 63 (2010) 181-198.