Article ID Journal Published Year Pages File Type
418479 Discrete Applied Mathematics 2012 8 Pages PDF
Abstract

For a simple graph G=(V,E)G=(V,E) with nn vertices and mm edges, the first Zagreb index and the second Zagreb index are defined as M1(G)=∑v∈Vd(v)2M1(G)=∑v∈Vd(v)2 and M2(G)=∑uv∈Ed(u)d(v)M2(G)=∑uv∈Ed(u)d(v), where d(u)d(u) is the degree of a vertex uu of GG. In [28], it was shown that if a connected graph GG has maximal degree 4, then GG satisfies M1(G)/n=M2(G)/mM1(G)/n=M2(G)/m (also known as the Zagreb indices equality) if and only if GG is regular or biregular of class 1 (a biregular graph whose no two vertices of same degree are adjacent). There, it was also shown that there exist infinitely many connected graphs of maximal degree Δ=5Δ=5 that are neither regular nor biregular of class 1 which satisfy the Zagreb indices equality. Here, we generalize that result by showing that there exist infinitely many connected graphs of maximal degree Δ≥5Δ≥5 that are neither regular nor biregular graphs of class 1 which satisfy the Zagreb indices equality. We also consider when the above equality holds when the degrees of vertices of a given graph are in a prescribed interval of integers.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,