hal-00531290, version 1
Graph Classes (Dis)satisfying the Zagreb Indices Inequality
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 :
- Faculty of Electrical Engineering and Information Technologies, Ss Cyril and Methodius Univ.
- 2 :
- INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
- 3 :
- University of Ljubljana
- Domaine : Mathématiques/Combinatoire
- hal-00531290, version 1
- http://hal.archives-ouvertes.fr/hal-00531290
- 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



Documents associés
Exporter