Maximizing the Zagreb indices of \((n,m)\)-graphs. (English) Zbl 1464.05118
Summary: For a (molecular) graph, the first and second Zagreb indices (\(M_1\) and \(M_2\)) are two well-known topological indices in chemical graph theory introduced by I. Gutman and N. Trinajstić [“Graph theory and molecular orbitals. Total \(\varphi\)-electron energy of alternant hydrocarbons”, Chem. Phys. Lett. 17, 535–538 (1972; doi:10.1016/0009-2614(72)85099-1)]. Let \(\mathcal{G}_{n,m}\) be the set of connected graphs of order \(n\) and with \(m\) edges. In this paper we characterize the extremal graphs from \(\mathcal{G}_{n,m}\) with \(n + 2\ge m \ge 2n-4\) with maximal first Zagreb index and from \(\mathcal{G}_{n,m}\) with \(m-n = \binom{k}{2}-k\) for \(k\ge 4\) with maximal second Zagreb index, respectively. Finally a related conjecture has been proposed to the extremal graphs with respect to second Zagreb index.
MSC:
05C09 | Graphical indices (Wiener index, Zagreb index, Randić index, etc.) |
05C07 | Vertex degrees |
05C92 | Chemical graph theory |
92E10 | Molecular structure (graph-theoretic methods, methods of differential topology, etc.) |
05C12 | Distance in graphs |
05C35 | Extremal problems in graph theory |