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