Symmetry (Feb 2023)
Minimizing the Gutman Index among Unicyclic Graphs with Given Matching Number
Abstract
For a connected graph G with vertex set V, denote by d(v) the degree of vertex v and d(u, v) the distance between u and v. The value Gut(G)=∑{u,v}⊆Vd(u)d(v)d(u,v) is called the Gutman index of G. Recently, the graph minimizing the Gutman index among unicyclic graphs with pendent edges was characterized. Denoted by U(n,m) the set of unicyclic graphs on n vertices with matching number m. Motivated by that work, in this paper, we obtain a sharp lower bound for Gutman index of graphs in U(n,m), and the extremal graph attaining the bound is also obtained. It is worth noticing that all the extremal graphs are of high symmetry, that is, they have large automorphic groups.
Keywords