Authors: Ilić, Aleksandar
Stevanović, Dragan 
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: On comparing Zagreb indices
Journal: Match
Volume: 62
Issue: 3
First page: 681
Last page: 687
Issue Date: 1-Dec-2009
Rank: M21a
ISSN: 0340-6253
Let G = (V, E) be a simple graph with n = |V| vertices and m = |E| edges. The first and second Zagreb indices are among the oldest and the most famous topological indices, defined as M1 = Σiεv di2and M2 = Σ(i,j)εE d 1d2, where d1 denote the degree of vertex i. Recently proposed conjecture M1/n ≤ M2/m has been proven to hold for trees, unicyclic graphs and chemical graphs, while counterexamples were found for both connected and disconnected graphs. Our goal is twofold, both in favor of a conjecture and against it. Firstly, we show that the expressions M1/n and M2/m have the same lower and upper bounds, which attain equality for and only for regular graphs. We also establish sharp lower bound for variable first and second Zagreb indices. Secondly, we show that for any fixed number k > 2, there exists a connected graph with k cycles for which M1/n > M2/m holds, effectively showing that the conjecture cannot hold unless there exists some kind of limitation on the number of cycles or the maximum vertex degree in a graph. In particular, we show that the conjecture holds for subdivision graphs.
Publisher: Faculty of Sciences, University of Kragujevac
Project: Serbian Ministry of Science and Environmental Protection, Research Grants 144007 and 144015G
Slovenian Agency for Research, program P1-0285

Show full item record


checked on May 23, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.