Quasi-tree graphs with the minimal Sombor indices

Li, Yibo ; Liu, Huiqing ; Zhang, Ruiting

Czechoslovak Mathematical Journal, Tome 72 (2022) no. 4, pp. 1227-1238.

Résumé

The Sombor index $SO(G)$ of a graph $G$ is the sum of the edge weights $\sqrt {d^2_G(u)+d^2_G(v)}$ of all edges $uv$ of $G$, where $d_G(u)$ denotes the degree of the vertex $u$ in $G$. A connected graph $G = (V ,E)$ is called a quasi-tree if there exists $u\in V (G)$ such that $G-u$ is a tree. Denote $\mathscr {Q}(n,k)=\{G \colon G$ is a quasi-tree graph of order $n$ with $G-u$ being a tree and $d_G(u)=k\}$. We determined the minimum and the second minimum Sombor indices of all quasi-trees in $\mathscr {Q}(n,k)$. Furthermore, we characterized the corresponding extremal graphs, respectively.

Détail

DOI : 10.21136/CMJ.2022.0152-22

Classification : 05C07, 05C09, 05C35
Keywords: Sombor index; quasi-tree; tree