Extremal graphs with maximum complementary second Zagreb index
Hui Gao · 2025
Read Extremal graphs with maximum complementary second Zagreb index by Hui Gao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-01343.txt.
Introduction
Hui Gao confirms a guess about which graphs push a new degree based index, the complementary second Zagreb index, to its max for a set size. Such indices boil a graph's shape down to one number used in chem-ical graph work. The work came out in twenty twenty-five.
The index came from a fresh geometric view of graph edges, set out by Furtula and Oz. In that same work, the authors guessed which graphs of a given order reach the top value. Gao proves the guess holds, which pins down the extremal graphs fully. The result closes an open point in the study of these new indices.
Catalog record
| CREATOR | Hui Gao |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 23 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-01343
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Extremal graphs with maximum complementary second Zagreb index Hui Gao Abstract Recently, a couple of degree-based topological indices, defined using a geometrical point of view of a graph edge, have attracted significant attention and being extensively investigated. Furtula and Oz [Complementary Topological Indices, MATCH Commun. Math. Comput. Chem. 93 (2025) 247–263] introduced a novel approach for devising “geometrical” topological indices and focused special attention on the complementary second Zagreb index as a representation of the introduced approach. In the same paper, they also conjectured the maximal graphs of order n n with the maximum complementary second Zagreb index. In this paper, we confirm their conjecture. 1 Introduction All graphs, digraphs and mixed graphs in this paper are considered to be simple, that is they have no loops or parallel edges or arcs. Let F be a mixed graph with vertex set V(F) , edge set E(F) and arc set A(F) . Since a graph or digraph can be seen as a special mixed graph with empty arc set or empty edge set respectively, the following definitions are claimed only for mixed graphs. For X\subseteq V(F) , denote by F[X] the mixed graph with vertex set X and edge set and arc set consisting of edges and arcs in F with both of their end-vertices in X respectively. For u\in V(F) , denote by d_{F}^{+}(u) , d_{F}^{-}(u) and d_{F}(u) the number of arcs with u as their tails, the number of arcs with u as their heads and the total number of edges and arcs incident with u , respectively. For an edge set E_{0} and arc set A_{0} , denote by F\pm E_{0} ( F\pm A_{0} ) the mixed graph by adding to F or deleting in F all edges in E_{0} (all arcs in A_{0} ) respectively. Let G and H be graphs. Denote by \overline{G} the graph with vertex set V(G) and edge set consisting of pairs of nonadjacent vertices of G . Denote by G\vee H the graph by starting with a disjoint union of two graphs G and H and adding edges joining every vertex of G to every vertex of H . Chemical Graph Theory is a branch of Mathematical Chemistry which has an important effect on the development of Chemical Sciences. A molecular graph or chemical graph is a simple graph such that its vertices correspond to the atoms and the edges to the bonds. In Chemistry, degree-based topological indices have been found to be useful in discrimination, chemical documentation, structure property relationships, structure activity relationships and pharmaceutical drug design. There has been considerable interest in the general problem of determining degree-based topological indices, see [ 3 , 7 ] . Furtula and Oz [ 1 ] introduced a novel way to construct the indices using complement degree points: by substituting end-vertex degrees d_{G}(u) and d_{G}(v) with d_{G}(u)+d_{G}(v) and d_{G}(u)-d_{G}(v) in the definitions of the existing degree-based topological indices. Using this approach they got a whole new group of degree topological descriptors named as complementary topological indices. Special attention was focused on the existing second Zagreb index M_{2}(G) of a graph G , where M_{2}(G):=\sum_{uv\in E(G)}d_{G}(u)d_{G}(v). As a representation of the introduced approach, with a slight rectification, they introduced the complementary second Zagreb index cM_{2}(G) : cM_{2}(G)=\sum_{uv\in E(G)}|d_{G}(u)^{2}-d_{G}(v)^{2}|. However, this index is not put forward here for the first time. It was introduced and reintroduced in several recent and unrelated papers, which resulted in several names for this index, such as nano Zagreb index [ 5 ] , minus- F index [ 6 ] , modified Albertson index [ 10 ] and first Sombor index [ 2 , 4 , 9 ] . Later, this index was investigated for some supramolecular chains [ 4 ] , and maximal trees and unicyclic graphs with some given parameters were determined in [ 8 ] . Additionally, in [ 8 ] the correlations of this index with some physicochemical properties of octanes and benzenoid hydrocarbons were displayed. Also, Furtula and Oz [ 1 ] conjectured the structure of the maximal graphs of order n with the maximum complementary second Zagreb index. Conjecture 1 ( [ 1 ] ) . The graph with n vertices and the maximum complementary second Zagreb index is isomorphic to K_{m}\vee\overline{K_{n-m}} for some 1\leq m\leq n-1 . In this paper, we confirm their conjecture. Theorem 1 . Conjecture 1 is true. 2 Preliminaries Let G=(V,E) be an undirected graph with n vertices and F be the mixed graph obtained by orienting some edges in G as follows: (i) \overrightarrow{uv}\in A(F)\text{~if~}uv\in E(G)\text{~and~}d_{G}(u)>d_{G}(v),\\ (ii) uv\in E(F)\text{~if~}uv\in E(G)\text{~and~}d_{G}(u)=d_{G}(v). Denote by X and Y the set of vertices satisfying d_{F}^{+}(u)\geq d_{F}^{-}(u) and d_{F}^{+}(u)<d_{F}^{-}(u) respectively. In this section, we will show some basic properties of cM_{2}(G) and graph operations that will increase cM_{2}(G) . Observation 1 . For any mixed graph F^{\prime} obtained by orienting some edges in G , we have cM_{2}(G)\geq\sum_{\overrightarrow{uv}\in A(F^{\prime})}(d_{F^{\prime}}(u)^{2}-d_{F^{\prime}}(v)^{2}). If the mixed graph F^{\prime}=F , the equality holds. Observation 2 . For any mixed graph F^{\prime} obtained by orienting some edges in G , we have \begin{split}cM_{2}(G)&\geq\sum_{\overrightarrow{uv}\in A(F^{\prime})}(d_{F^{\prime}}(u)^{2}-d_{F^{\prime}}(v)^{2})~~\text{(by Observation~\ref{OB-1})}\\ &=\sum_{v\in V(G)}(-\sum_{\overrightarrow{uv}\in A(F^{\prime})}d_{F^{\prime}}(v)^{2}+\sum_{\overrightarrow{vw}\in A(F^{\prime})}d_{F^{\prime}}(v)^{2})\\ &=\sum_{v\in V(G)}(d_{F^{\prime}}^{+}(v)-d_{F^{\prime}}^{-}(v))d_{F^{\prime}}(v)^{2}.\end{split} If the mixed graph F^{\prime}=F , the equality holds. Operation A: For any u,v\in X , if uv\notin E(G) , then cM_{2}(G+uv)\geq cM_{2}(G) . If the equality holds, then d_{F}(u)=d_{F}(v) , d_{F}^{+}(u)=d_{F}^{-}(u) and d_{F}^{+}(v)=d_{F}^{-}(v) . Proof. Without loss of generality, suppose d_{G}(u)\geq d_{G}(v) . Add \overrightarrow{uv} to F . Then for any vertex v^{\prime} in G except u and v , the degree, out-degree and in-degree of v^{\prime} in F+\overrightarrow{uv} is the same as in F . Note that since u,v\in X , d_{F}^{+}(u)\geq d_{F}^{-}(u) and d_{F}^{+}(v)\geq d_{F}^{-}(v) . Then we have \begin{split}&cM_{2}(G+uv)-cM_{2}(G)\\ &\geq\sum_{v^{\prime}\in V(G)}(d_{F+\overrightarrow{uv}}^{+}(v^{\prime})-d_{F+\overrightarrow{uv}}^{-}(v^{\prime}))d_{F+\overrightarrow{uv}}(v^{\prime})^{2}\\ &~~~-\sum_{v^{\prime}\in V(G)}(d_{F}^{+}(v^{\prime})-d_{F}^{-}(v^{\prime}))d_{F}(v^{\prime})^{2}~~~\text{(by Observation\ref{OB-2})}\\ &=(d_{F+\overrightarrow{uv}}^{+}(u)-d_{F+\overrightarrow{uv}}^{-}(u))d_{F+\overrightarrow{uv}}(u)^{2}+(d_{F+\overrightarrow{uv}}^{+}(v)-d_{F+\overrightarrow{uv}}^{-}(v))d_{F+\overrightarrow{uv}}(v)^{2}\\ &~~~-((d_{F}^{+}(u)-d_{F}^{-}(u))d_{F}(u)^{2}+(d_{F}^{+}(v)-d_{F}^{-}(v))d_{F}(v)^{2})\\ &=(d_{F}^{+}(u)+1-d_{F}^{-}(u))(d_{F}(u)+1)^{2}+(d_{F}^{+}(v)-d_{F}^{-}(v)-1)(d_{F}(v)+1)^{2}\\ &~~~-((d_{F}^{+}(u)-d_{F}^{-}(u))d_{F}(u)^{2}+(d_{F}^{+}(v)-d_{F}^{-}(v))d_{F}(v)^{2})\\ &=(d_{F}^{+}(u)-d_{F}^{-}(u))(2d_{F}(u)+1)+(d_{F}^{+}(v)-d_{F}^{-}(v))(2d_{F}(v)+1)\\ &~~~+(d_{F}(u)+1)^{2}-(d_{F}(v)+1)^{2}\\ &\geq 0~~\text{(since $d_{F}^{+}(u)\geq d_{F}^{-}(u)$, $d_{F}^{+}(v)\geq d_{F}^{-}(v)$ by $u,v\in X$ and $d_{G}(u)\geq d_{G}(v)$)}.\end{split} If cM_{2}(G+uv)=cM_{2}(G) , then the second “ \geq ” should be “ = ”, which induces that d_{F}(u)=d_{F}(v) , d_{F}^{+}(u)=d_{F}^{-}(u) and d_{F}^{+}(v)=d_{F}^{-}(v) . ∎ Operation B: For any u,w\in V,v\in Y , if \overrightarrow{uv},\overrightarrow{vw}\in A(F) , uw\notin E(G) , then cM_{2}(G-uv-vw+uw)>cM_{2}(G) . Proof. Notice that G-uv-vw+uw is the underlying graph of the mixed graph F-\overrightarrow{uv}-\overrightarrow{vw}+\overrightarrow{uw} , and for any vertex v^{\prime} in G except v , the degree, out-degree and in-degree of v^{\prime} in F-\overrightarrow{uv}-\overrightarrow{vw}+\overrightarrow{uw} is same as in F . Hence we have \begin{split}&cM_{2}(G-uv-vw+uw)-cM_{2}(G)\\ &\geq(d_{F-\overrightarrow{uv}-\overrightarrow{vw}+\overrightarrow{uw}}^{+}(v)-d_{F-\overrightarrow{uv}-\overrightarrow{vw}+\overrightarrow{uw}}^{-}(v))d_{F-\overrightarrow{uv}-\overrightarrow{vw}+\overrightarrow{uw}}(v)^{2}\\ &~~~-(d_{F}^{+}(v)-d_{F}^{-}(v))d_{F}(v)^{2}~~~\text{(by Observation~\ref{OB-2}) }\\ &=((d_{F}^{+}(v)-1)-(d_{F}^{-}(v)-1))(d_{F}(v)-2)^{2}-(d_{F}^{+}(v)-d_{F}^{-}(v))d_{F}(v)^{2}\\ &=-4(d_{F}^{+}(v)-d_{F}^{-}(v))(d_{F}(v)-1)\\ &>0~~~\text{(since $d_{F}^{+}(v)<d_{F}^{-}(v)$ by $v\in Y$)}.\end{split} ∎ 3 Proof of Theorem 1 Suppose G=(V,E) is an undirected graph with n vertices and maximum complementary second Zagreb index. Let F be the mixed graph as the last section stated. Then we will show that G is isomorphic to K_{m}\vee\overline{K_{n-m}} for some 1\leq m\leq n-1 . Claim 1 . For any u,v\in X , if uv\notin E(G) , then d_{G}(u)=d_{G}(v) and for any w\in X\setminus\{u,v\} , d_{G}(w)\neq d_{G}(u) . Proof. By Operation A, cM_{2}(G+uv)\geq cM_{2}(G) . Since G has maximum complementary second Zagreb index, cM_{2}(G+uv)=cM_{2}(G) . Hence, by Operation A, d_{G}(u)=d_{G}(v) , d_{F}^{+}(u)=d_{F}^{-}(u) and d_{F}^{+}(v)=d_{F}^{-}(v) . Suppose to the contrary that there exists w\in X\setminus\{u,v\} such that d_{G}(w)=d_{G}(u) . Case 1: If uw\neq E(G) , then by Operation A, d_{F}^{+}(w)=d_{F}^{-}(w) . Add \overrightarrow{uv} and \overrightarrow{uw} to F . Then we have \begin{split}&cM_{2}(G+uv+uw)-cM_{2}(G)\\ &\geq\sum_{v^{\prime}=u,v,w}(d_{F+\overrightarrow{uv}+\overrightarrow{uw}}^{+}(v^{\prime})-d_{F+\overrightarrow{uv}+\overrightarrow{uw}}^{-}(v^{\prime}))d_{F+\overrightarrow{uv}+\overrightarrow{uw}}(v^{\prime})^{2}\\ &~~~-\sum_{v^{\prime}=u,v,w}(d_{F}^{+}(v^{\prime})-d_{F}^{-}(v^{\prime}))d_{F}(v^{\prime})^{2}~~~\text{(by