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 well-known subclass of maximal $k$-degenerate graphs is the $k$-trees. Albertson irregularity (resp., sigma irregularity) of a graph is the summation of edge imbalances (resp., squares of edge imbalances) over all edges of the graph, where an edge imbalance is the absolute value of the degree difference of its two end vertices. In this talk, we will present a sharp upper bound on the Albertson irregularities of maximal $k$-degenerate graphs of order $n$ and characterize the extremal graphs as $k$-stars. Similar results also hold for sigma irregularity. Finding lower bounds on irregularities of maximal $k$-degenerate graphs is challenging. We will provide sharp lower bounds on Albertson irregularities of $k$-trees of order $n$ and characterize the extremal graphs as $k$th powers of paths.
Graph irregularities of maximal k-degenerate graphs
Zhongyuan Che, Penn State University, Beaver Campus
Authors: Alan Bickle and Zhongyuan Che
2022 AWM Research Symposium
Women from the Graduate Research Workshop in Combinatorics