21773 articles – 15587 Notices  [english version]

hal-00531290, version 1

## Graph Classes (Dis)satisfying the Zagreb Indices Inequality

Vesna Andova () 1, Nathann Cohen () 2, Riste Skrekovski 3

MATCH Communications in Mathematical and in Computer Chemistry 65, 3 (2011) 647-658

Résumé : {Recently Hansen and Vukicevic proved that the inequality $M_1/n \leq M_2/m$, where $M_1$ and $M_2$ are the first and second Zagreb indices, holds for chemical graphs, and Vukicevic and Graovac proved that this also holds for trees. In both works is given a distinct counterexample for which this inequality is false in general. Here, we present some classes of graphs with prescribed degrees, that satisfy $M_1/n \leq M_2/m$: Namely every graph $G$ whose degrees of vertices are in the interval $[c; c + \sqrt c]$ for some integer $c$ satisies this inequality. In addition, we prove that for any $\Delta \geq 5$, there is an infinite family of graphs of maximum degree $\Delta$ such that the inequality is false. Moreover, an alternative and slightly shorter proof for trees is presented, as well\ as for unicyclic graphs.

• 1 :  Institute of Mathematics and Physics [Skopje]
• Faculty of Electrical Engineering and Information Technologies, Ss Cyril and Methodius Univ.
• 2 :  MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
• INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
• 3 :  Faculty of Mathematics and Physics [Ljubljana] (FMF)
• University of Ljubljana
• Domaine : Mathématiques/Combinatoire

• hal-00531290, version 1
• oai:hal.archives-ouvertes.fr:hal-00531290
• Contributeur :
• Soumis le : Mardi 2 Novembre 2010, 12:28:11
• Dernière modification le : Mardi 2 Novembre 2010, 13:54:40