Minimum eccentric connectivity index for graphs with fixed order and fixed number of pendant vertices

Authors

  • Gauvain Devillez Computer Science Department - Algorithms Lab, University of Mons, Mons, Belgium
  • Alain Hertz Department of Mathematics and Industrial Engineering, Polytechnique Moontréal - Gerad, Montréal, Canada
  • Hadrien Mélot Computer Science Department - Algorithms Lab, University of Mons, Mons, Belgium
  • Pierre Hauweele Computer Science Department - Algorithms Lab, University of Mons, Mons, Belgium

DOI:

https://doi.org/10.2298/YJOR181115010D

Keywords:

Extremal Graph Theory, Eccentric Connectivity Index, Pendant Vertices

Abstract

The eccentric connectivity index of a connected graph G is the sum over all vertices v of the product dG(v)eG(v), where dG(v) is the degree of v in G and eG(v) is the maximum distance between v and any other vertex of G. We characterize, with a new elegant proof, those graphs which have the smallest eccentric connectivity index among all connected graphs of a given order n. Then, given two integers n and p with p ≤ n - 1, we characterize those graphs which have the smallest eccentric connectivity index among all connected graphs of order n with p pendant vertices.

References

Cayley, F.R.S., On the mathematical theory of isomers, The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 47 (314) (1874) 444-447.

Dureja, H., Gupta, S., and Madan, A., Predicting anti-HIV-1 activity of 6-arylbenzonitriles: Computational approach using superaugmented eccentric connectivity topochemical indices, Journal of Molecular Graphics and Modelling, 26 (6) (2008) 1020-1029.

Gupta, S., Singh, M., and Madan, A., Eccentric distance sum: A novel graph invariant for predicting biological and physical properties, Journal of Mathematical Analysis and Applications, 275 (1) (2002) 386-401.

Hansen, P., and Melot, H., Variable neighborhood search for extremal graphs: Analyzing bounds for the connectivity index, Journal of Chemical Information and Computer Sciences, 43 (1) (2003) 1-14.

Hauweele, P., Hertz, A., Melot, H., Ries, B., and Devillez, G., Maximum eccentric connectivity index for graphs with given diameter, arXiv preprint arXiv:1808.10203, to appear in Discrete Applied Mathematics (2018).

Ilić, A., and Gutman, I., Eccentric connectivity index of chemical trees, MATCH, Communications in Mathematical and in Computer Chemistry, 65 (3) (2011) 731-744.

Karelson, M., Molecular Descriptors in QSAR/QSPR, Wiley-Interscience, 2000.

Kumar, V., Sardana, S., and Madan, A. K., Predicting anti-HIV activity of 2,3-diaryl-1,3-thiazolidin-4-ones: Computational approach using reformed eccentric connectivity index, Journal of Molecular Modeling, 10 (2004) 399-407.

Sardana, S., and Madan, A. K., Application of graph theory: Relationship of molecular connectivity index, Wiener's index and eccentric connectivity index with diuretic activity, MATCH, Communications in Mathematical and in Computer Chemistry, 43 (2001) 85-98.

Sharma, V., Goswami, R., and Madan, A., Eccentric connectivity index: A novel highly discriminating topological descriptor for structure property and structure activity studies, Journal of Chemical Information and Computer Sciences, 37 (2) (1997) 273-282.

Todeschini, R., and Consonni, V., Handbook of Molecular Descriptors, Wiley-VCH, 2008.

Wiener, H., Structural determination of paraffin boiling points, Journal of the American Chemical Society, 69 (1) (1947) 17-20.

Zhou, B., and Du, Z., On eccentric connectivity index, MATCH, Communications in Mathematical and in Computer Chemistry, 63 (1) (2010) 181-198.

Downloads

Published

2019-05-01

Issue

Vol. 29 No. 2 (2019)

Section

Research Articles

License

Copyright (c) 2019 YUJOR

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.