18-21 June 2015
Kranjska Gora, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

Comparing Zagreb Indices for Almost All Graphs

Presented by Dr. Jelena SEDLAR
Type: Oral presentation


It was conjectured in litearature that the inequality $\frac{M_{1}(G)}{n}\leq\frac{M_{2}(G)}{m}$ holds for all simple graphs, where $M_{1}(G)$ and $M_{2}(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 behaviour of graphs sattisfying the conjecture to some general graph operations it was further conjectured that the inequality might hold for almost all simple graphs. 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. This is a joint work with Damir Vukičević and Dragan Stevanović.


Location: Kranjska Gora, Slovenia
Address: Ramada resort hotel Borovška cesta 99 4280 Kranjska Gora

Primary authors