On the relation between Wiener index and eccentricity of a graph
| Autor: | Hamid Darabi, Kinkar Chandra Das, Sandi Klavžar, Yaser Alizadeh |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Control and Optimization
Conjecture Applied Mathematics Wiener index Radius Type (model theory) Upper and lower bounds Computer Science Applications Combinatorics Computational Theory and Mathematics Discrete Mathematics and Combinatorics Order (group theory) Astrophysics::Earth and Planetary Astrophysics Tree (set theory) Eccentricity (mathematics) Mathematics |
| Zdroj: | Journal of Combinatorial Optimization. 41:817-829 |
| ISSN: | 1573-2886 1382-6905 |
| DOI: | 10.1007/s10878-021-00724-2 |
| Popis: | The relation between the Wiener index W(G) and the eccentricity $$\varepsilon (G)$$ of a graph G is studied. Lower and upper bounds on W(G) in terms of $$\varepsilon (G)$$ are proved and extremal graphs characterized. A Nordhaus–Gaddum type result on W(G) involving $$\varepsilon (G)$$ is given. A sharp upper bound on the Wiener index of a tree in terms of its eccentricity is proved. It is shown that in the class of trees of the same order, the difference $$W(T) - \varepsilon (T)$$ is minimized on caterpillars. An exact formula for $$W(T) - \varepsilon (T)$$ in terms of the radius of a tree T is obtained. A lower bound on the eccentricity of a tree in terms of its radius is also given. Two conjectures are proposed. The first asserts that the difference $$W(G) - \varepsilon (G)$$ does not increase after contracting an edge of G. The second conjecture asserts that the difference between the Wiener index of a graph and its eccentricity is largest on paths. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink