Let G be a graph with vertex set and edge set . A graph invariant for G is a number related to the structure of G which is invariant under the symmetry of G. The Sombor and reduced Sombor indices of G are two new graph invariants defined as and , respectively, where is the degree of the vertex v in G. We denote by the graph constructed from the star by adding edge(s), , between a fixed pendent vertex and other pendent vertices. Réti et al. [T. Réti, T Došlić and A. Ali, On the Sombor index of graphs, Contrib. Math.3 (2021) 11–18] proposed a conjecture that the graph has the maximum Sombor index among all connected -cyclic graphs of order n, where . In some earlier works, the validity of this conjecture was proved for . In this paper, we confirm that this conjecture is true, when . The Sombor index in the case that the number of pendent vertices is less than or equal to is investigated, and the same results are obtained for the reduced Sombor index. Some relationships between Sombor, reduced Sombor, and first Zagreb indices of graphs are also obtained.
Let G be a simple and undirected graph with Laplacian polynomial . In earlier works, some formulas for computing , and in terms of the number of vertices, the Wiener, the first Zagreb and the forgotten indices are given. In this paper, we continue this work by computing , where T is a tree. A lower and an upper bound for are obtained.
A simple graph is said to be regular if its vertices have the same number of neighbors. Otherwise, is nonregular. So far, various formulas, such as the Albertson index, total Albertson index, and degree deviation, have been introduced to quantify the irregularity of a graph. In this paper, we present sharp lower bounds for these indices in terms of the order, size, maximum degree, minimum degree, and forgotten and Zagreb indices of the underlying graph. We also prove that if has the minimum value of degree deviation, among all nonregular - graphs, then .
Let G be a graph and let S(G), M(G), and T(G) be the subdivision, the middle, and the total graph of G, respectively. Let dim(G), edim(G), and mdim(G) be the metric dimension, the edge metric dimension, and the mixed metric dimension of G, respectively. In this paper, for the subdivision graph it is proved that max{dim(G), edim(G)} ≤ mdim(S(G)) ≤ mdim(G). A family of graphs Gn is constructed for which mdim(Gn) − mdim(S(Gn)) ≥ 2 holds and this shows that the inequality mdim(S(G)) ≤ mdim(G) can be strict, while for a cactus graph G, mdim(S(G)) = mdim(G). For the middle graph it is proved that dim(M(G)) ≤ mdim(G) holds, and if G is tree with n1(G) leaves, then dim(M(G)) = mdim(G) = n1(G). Moreover, for the total graph it is proved that mdim(T (G)) = 2n1(G) and dim(G) ≤ dim(T (G)) ≤ n1(G) hold when G is a tree.
Let G be a graph with edge set E G and e = u v ∈ E G . Define n u e , G and m u e , G to be the number of vertices of G closer to u than to v and the number of edges of G closer to u than to v , respectively. The numbers n v e , G and m v e , G can be defined in an analogous way. The Mostar and edge Mostar indices of G are new graph invariants defined as M o G = ∑ u v ∈ E G n u u v , G − n v u v , G and M o e G = ∑ u v ∈ E G m u u v , G − m v u v , G , respectively. In this paper, an upper bound for the Mostar and edge Mostar indices of a tree in terms of its diameter is given. Next, the trees with the smallest and the largest Mostar and edge Mostar indices are also given. Finally, a recent conjecture of Liu, Song, Xiao, and Tang (2020) on bicyclic graphs with a given order, for which extremal values of the edge Mostar index are attained, will be proved. In addition, some new open questions are presented.
11 June 2023 in Computational and Applied Mathematics