Authors: Vukičević, Damir
Sedlar, Jelena
Stevanović, Dragan 
Title: Comparing Zagreb indices for almost all graphs
Journal: Match
Volume: 78
Issue: 2
First page: 323
Last page: 326
Issue Date: 1-Jan-2017
Rank: M21a
ISSN: 0340-6253
It was conjectured in literature that the inequality M1(G)/n ≤ M2(G)/m holds for all simple graphs, where M1(G) and M2(G) are the first and the second Zagreb index. By further research it was proven that the inequality holds for several graph classes such as chemical graphs, trees, unicyclic graphs and subdivided graphs, but that generally it does not hold since counter examples have been established in several other graph classes. So, the conjecture generally does not hold. Given the behavior of graphs satisfying the conjecture to some general graph operations it was further conjectured that the inequality might hold for almost all simple graphs. In this paper we will prove that this conjecture is true, by proving that the probability of a random graph G on n vertices to satisfy the inequality tends to 1 as n tends to infinity.
Publisher: Faculty of Sciences, University of Kragujevac
Project: Slovenian Research Agency (research program P1-0285 and research projects J1-5433, J1-6720, J1-6743, and J7-6828)
Graph theory and mathematical programming with applications in chemistry and computer science 

Show full item record


checked on May 20, 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.