Greedy trees have minimum Sombor indices
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929352768225280 |
|---|---|
| author | Damnjanović, Ivan Stevanović, Dragan |
| author_facet | Damnjanović, Ivan Stevanović, Dragan |
| contents | Recently, Gutman [MATCH Commun. Math. Comput. Chem. 86 (2021) 11-16] defined a new graph invariant which is named the Sombor index $\mathrm{SO}(G)$ of a graph $G$ and is computed via the expression \[
\mathrm{SO}(G) = \sum_{u \sim v} \sqrt{\mathrm{deg}(u)^2 + \mathrm{deg}(v)^2} , \] where $\mathrm{deg}(u)$ represents the degree of the vertex $u$ in $G$ and the summing is performed across all the unordered pairs of adjacent vertices $u$ and $v$. Here we take into consideration the set of all the trees $\mathcal{T}_D$ that have a specified degree sequence $D$ and show that the greedy tree attains the minimum Sombor index on the set $\mathcal{T}_D$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_05559 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Greedy trees have minimum Sombor indices Damnjanović, Ivan Stevanović, Dragan Combinatorics 05C35, 05C09, 05C05, 05C07 Recently, Gutman [MATCH Commun. Math. Comput. Chem. 86 (2021) 11-16] defined a new graph invariant which is named the Sombor index $\mathrm{SO}(G)$ of a graph $G$ and is computed via the expression \[ \mathrm{SO}(G) = \sum_{u \sim v} \sqrt{\mathrm{deg}(u)^2 + \mathrm{deg}(v)^2} , \] where $\mathrm{deg}(u)$ represents the degree of the vertex $u$ in $G$ and the summing is performed across all the unordered pairs of adjacent vertices $u$ and $v$. Here we take into consideration the set of all the trees $\mathcal{T}_D$ that have a specified degree sequence $D$ and show that the greedy tree attains the minimum Sombor index on the set $\mathcal{T}_D$. |
| title | Greedy trees have minimum Sombor indices |
| topic | Combinatorics 05C35, 05C09, 05C05, 05C07 |
| url | https://arxiv.org/abs/2211.05559 |