On the maximum size of stepwise irregular graphs

作者：

Highlights：

• The paper is concerned with so-called “stepwise irregular graphs” (SI) and establishes a few interesting properties thereof.

• In many applications and problems, it is important to know how irregular a given graph is. Stepwise irregular graph is the least irregular graph among all graphs with non-zero edge imbalance.

• Some upper bounds on the maximum degree and sharp upper bounds on the size of stepwise irregular graphs are obtained.

• Among all connected stepwise irregular graphs of the given order, the graphs with maximum size are completely characterized.

摘要

•The paper is concerned with so-called “stepwise irregular graphs” (SI) and establishes a few interesting properties thereof.•In many applications and problems, it is important to know how irregular a given graph is. Stepwise irregular graph is the least irregular graph among all graphs with non-zero edge imbalance.•Some upper bounds on the maximum degree and sharp upper bounds on the size of stepwise irregular graphs are obtained.•Among all connected stepwise irregular graphs of the given order, the graphs with maximum size are completely characterized.

论文关键词：Irregularity,Maximum degree,Stepwise irregular graph,Bipartite graph

论文评审过程：Received 20 May 2020, Revised 9 September 2020, Accepted 13 September 2020, Available online 6 October 2020, Version of Record 6 October 2020.

论文官网地址：https://doi.org/10.1016/j.amc.2020.125683