Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2401.12370 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917572653350912 |
|---|---|
| author | Ghebleh, Mohammad Kanso, Ali |
| author_facet | Ghebleh, Mohammad Kanso, Ali |
| contents | The Wiener index W(G) of a graph G is the sum of distances between all unordered pairs of its vertices. Dobrynin and Mel'nikov [in: Distance in Molecular Graphs - Theory, 2012, p. 85-121] propose the study of estimates for extremal values of the ratio R_k(G) = W(L^k(G))/W(G) where L^k(G) denotes the k-th iterated line graph of G. Hriňáková, Knor and Škrekovski [Art Discrete Appl. Math. 1 (2018) #P1.09] prove that for each k>2, the path P_n has the smallest value of the ratio R_k among all trees of large order n, and they conjecture that the same holds for the case k=2. We give a counterexample of every order n>21 to this conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_12370 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Second-Order Wiener Ratios of Iterated Line Graphs Ghebleh, Mohammad Kanso, Ali Combinatorics The Wiener index W(G) of a graph G is the sum of distances between all unordered pairs of its vertices. Dobrynin and Mel'nikov [in: Distance in Molecular Graphs - Theory, 2012, p. 85-121] propose the study of estimates for extremal values of the ratio R_k(G) = W(L^k(G))/W(G) where L^k(G) denotes the k-th iterated line graph of G. Hriňáková, Knor and Škrekovski [Art Discrete Appl. Math. 1 (2018) #P1.09] prove that for each k>2, the path P_n has the smallest value of the ratio R_k among all trees of large order n, and they conjecture that the same holds for the case k=2. We give a counterexample of every order n>21 to this conjecture. |
| title | On the Second-Order Wiener Ratios of Iterated Line Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2401.12370 |