TY - JOUR

T1 - Irregularities of maximal k-degenerate graphs

AU - Bickle, Allan

AU - Che, Zhongyuan

N1 - Funding Information:
We would like to thank referees for their careful reading and helpful suggestions.
Publisher Copyright:
© 2023 Elsevier B.V.

PY - 2023/5/31

Y1 - 2023/5/31

N2 - A graph is maximal k-degenerate if every subgraph has a vertex of degree at most k, and the property does not hold if any new edge is added to the graph. A k-tree is a maximal k-degenerate graph that does not contain any induced cycle with more than three edges. We study Albertson irregularity and sigma irregularity for a maximal k-degenerate graph of order n≥k+2. Sharp upper bounds on both irregularity indices of maximal k-degenerate graphs are provided and their extremal graphs are characterized as k-stars Kk+K¯n−k. Sharp lower bounds on both irregularity indices of k-trees are obtained and their extremal graphs are characterized as kth powers of paths Pnk. Sharp lower bounds on irregularities of maximal 2-degenerate graphs are also proved.

AB - A graph is maximal k-degenerate if every subgraph has a vertex of degree at most k, and the property does not hold if any new edge is added to the graph. A k-tree is a maximal k-degenerate graph that does not contain any induced cycle with more than three edges. We study Albertson irregularity and sigma irregularity for a maximal k-degenerate graph of order n≥k+2. Sharp upper bounds on both irregularity indices of maximal k-degenerate graphs are provided and their extremal graphs are characterized as k-stars Kk+K¯n−k. Sharp lower bounds on both irregularity indices of k-trees are obtained and their extremal graphs are characterized as kth powers of paths Pnk. Sharp lower bounds on irregularities of maximal 2-degenerate graphs are also proved.

UR - http://www.scopus.com/inward/record.url?scp=85147120160&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85147120160&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2023.01.020

DO - 10.1016/j.dam.2023.01.020

M3 - Article

AN - SCOPUS:85147120160

SN - 0166-218X

VL - 331

SP - 70

EP - 87

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -