Minimum eccentric connectivity index for graphs with fixed order and fixed number of pendant vertices
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...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Belgrade
2019-01-01
|
| Series: | Yugoslav Journal of Operations Research |
| Subjects: | |
| Online Access: | http://www.doiserbia.nb.rs/img/doi/0354-0243/2019/0354-02431900010D.pdf |
| _version_ | 1828487852079448064 |
|---|---|
| author | Devillez Gauvain Hertz Alain Mélot Hadrien Hauweele Pierre |
| author_facet | Devillez Gauvain Hertz Alain Mélot Hadrien Hauweele Pierre |
| author_sort | Devillez Gauvain |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-11T09:59:29Z |
| format | Article |
| id | doaj.art-98575346a9b54b1fb9562a30b747b57c |
| institution | Directory Open Access Journal |
| issn | 0354-0243 1820-743X |
| language | English |
| last_indexed | 2024-12-11T09:59:29Z |
| publishDate | 2019-01-01 |
| publisher | University of Belgrade |
| record_format | Article |
| series | Yugoslav Journal of Operations Research |
| spelling | doaj.art-98575346a9b54b1fb9562a30b747b57c2022-12-22T01:12:11ZengUniversity of BelgradeYugoslav Journal of Operations Research0354-02431820-743X2019-01-0129219320210.2298/YJOR181115010D0354-02431900010DMinimum eccentric connectivity index for graphs with fixed order and fixed number of pendant verticesDevillez Gauvain0Hertz Alain1Mélot Hadrien2Hauweele Pierre3Computer Science Department - Algorithms Lab, University of Mons, Mons, BelgiumDepartment of Mathematics and Industrial Engineering, Polytechnique Moontréal - Gerad, Montréal, CanadaComputer Science Department - Algorithms Lab, University of Mons, Mons, BelgiumComputer Science Department - Algorithms Lab, University of Mons, Mons, BelgiumThe 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.http://www.doiserbia.nb.rs/img/doi/0354-0243/2019/0354-02431900010D.pdfextremal graph theoryeccentric connectivity indexpendant vertices |
| spellingShingle | Devillez Gauvain Hertz Alain Mélot Hadrien Hauweele Pierre Minimum eccentric connectivity index for graphs with fixed order and fixed number of pendant vertices Yugoslav Journal of Operations Research extremal graph theory eccentric connectivity index pendant vertices |
| title | Minimum eccentric connectivity index for graphs with fixed order and fixed number of pendant vertices |
| title_full | Minimum eccentric connectivity index for graphs with fixed order and fixed number of pendant vertices |
| title_fullStr | Minimum eccentric connectivity index for graphs with fixed order and fixed number of pendant vertices |
| title_full_unstemmed | Minimum eccentric connectivity index for graphs with fixed order and fixed number of pendant vertices |
| title_short | Minimum eccentric connectivity index for graphs with fixed order and fixed number of pendant vertices |
| title_sort | minimum eccentric connectivity index for graphs with fixed order and fixed number of pendant vertices |
| topic | extremal graph theory eccentric connectivity index pendant vertices |
| url | http://www.doiserbia.nb.rs/img/doi/0354-0243/2019/0354-02431900010D.pdf |
| work_keys_str_mv | AT devillezgauvain minimumeccentricconnectivityindexforgraphswithfixedorderandfixednumberofpendantvertices AT hertzalain minimumeccentricconnectivityindexforgraphswithfixedorderandfixednumberofpendantvertices AT melothadrien minimumeccentricconnectivityindexforgraphswithfixedorderandfixednumberofpendantvertices AT hauweelepierre minimumeccentricconnectivityindexforgraphswithfixedorderandfixednumberofpendantvertices |