Stepwise irregular graph

In graph theory, a stepwise irregular graph (or SI graph) is a graph in which the degrees of any two adjacent vertices differ by exactly one. This concept was introduced by Ivan Gutman in 2018 as a way to study graphs with minimal irregularity among those with non-zero edge imbalance. ^[1]

Definition

A graph ${\displaystyle G=(V,E)}$ is called stepwise irregular if for every edge ${\displaystyle uv\in E(G)}$, we have ${\displaystyle |d(u)-d(v)|=1}$, where ${\displaystyle d(x)}$ denotes the degree of vertex ${\displaystyle x}$.

More generally, a graph ${\displaystyle G}$ is called a ${\displaystyle k}$-stepwise irregular graph (or ${\displaystyle k}$-SI graph) for a positive integer ${\displaystyle k\geq 1}$ if ${\displaystyle |d(u)-d(v)|=k}$ for every edge ${\displaystyle uv\in E(G)}$. ^[2] The original stepwise irregular graphs correspond to the case ${\displaystyle k=1}$.

Basic properties

Stepwise irregular graphs have several fundamental structural properties. Every stepwise irregular graph is bipartite. This follows from the fact that SI graphs cannot contain odd cycles. In any cycle, moving along consecutive vertices requires the degrees to alternately increase and decrease by one, which is only possible if the cycle has even length. ^[1]

Every stepwise irregular graph has an even number of edges. This is a direct consequence of the Albertson index property and the fact that for SI graphs, the Albertson index equals the number of edges. ^[1]

In a stepwise irregular graph, every integer between the minimum degree ${\displaystyle \delta (G)}$ and maximum degree ${\displaystyle \Delta (G)}$ must appear as the degree of some vertex. ^[3] The graph is naturally bipartitioned into vertices of even degree and vertices of odd degree.

Structural results

Order constraints

The possible orders (number of vertices) of stepwise irregular graphs depend on their cyclomatic number ${\displaystyle \gamma =m-n+1}$:

• Trees (${\displaystyle \gamma =0}$): The order is always odd. SI trees exist for all odd orders except 1, 5, 8, 13, and 17. ^[1]

• Unicyclic graphs (${\displaystyle \gamma =1}$): The order is always even. SI unicyclic graphs exist for all even orders except 2, 4, 6, 10, and 14. ^[1]

• Bicyclic graphs (${\displaystyle \gamma =2}$): The order is always odd. SI bicyclic graphs exist for all odd orders except 1, 3, 7, and 11. ^{[1] [3]}

• Tricyclic graphs (${\displaystyle \gamma =3}$): The order is always even. SI tricyclic graphs exist for all even orders except 2, 4, 6, and 8. ^[3]

Connected stepwise irregular graphs exist for all orders except 1, 2, 4, and 6. ^{[1] [3]}

Diameter results

For ${\displaystyle k}$-stepwise irregular graphs, it has been proven that for any ${\displaystyle k\geq 1}$ and any diameter ${\displaystyle d\geq 2}$, there exists a ${\displaystyle k}$-SI graph with diameter ${\displaystyle d}$. This can be achieved using graph products such as the Cartesian and lexicographic products. ^[2]

Extremal results

For a ${\displaystyle k}$-stepwise irregular graph ${\displaystyle G}$ of order ${\displaystyle n}$:

${\displaystyle \Delta (G)\leq \lfloor {\frac {n+k}{2}}\rfloor }$

Where ${\displaystyle \Delta (G)}$ is the maximum degree of ${\displaystyle G}$. The equality holds if and only if ${\displaystyle G}$ is isomorphic to the complete bipartite graph ${\displaystyle K_{(n+k)/2,(n-k)/2}}$. ^[2]

The number of edges ${\displaystyle m}$ in a ${\displaystyle k}$-SI graph ${\displaystyle G}$ satisfies:

${\displaystyle m(G)\leq {\frac {n\Delta (G)(\Delta (G)-k)}{2\Delta (G)-k}}}$

with equality if and only if the degree complexity ${\displaystyle C_{d}(G)=2}$ (i.e., the graph has exactly two distinct degree values). ^[2]

Graph operations

Stepwise irregular graphs are not closed under common graph operations. ^[3] Removing any edge or vertex from an SI graph results in a non-SI graph. The complement of a connected SI graph is never SI. The subdivision graph of an SI graph is generally not SI, except for specific cases (${\displaystyle K_{2}}$, ${\displaystyle K_{1,3}}$, and 3-regular graphs). The line graph of an SI graph is not SI, except when the original graph is ${\displaystyle P_{4}}$.

Connection to graph irregularity

Stepwise irregular graphs are closely related to the Albertson index, a measure of graph irregularity defined as:

${\displaystyle \operatorname {Alb} (G)=\sum _{uv\in E(G)}|d(u)-d(v)|}$

This is sometimes denoted by ${\displaystyle I(G)}$ and simply called the irregularity of a graph in the literature. ^[4] For stepwise irregular graphs, ${\displaystyle \operatorname {Alb} (G)=m}$, making them the least irregular graphs among those with non-zero edge imbalance. ^[1]

Topological indices

The Wiener index ${\displaystyle W(G)}$, degree distance ${\displaystyle DD(G)}$, and Gutman index ${\displaystyle ZZ(G)}$ of SI graphs are all even integers, as well as the first and second Zagreb indices ${\displaystyle M_{1}(G)}$ and ${\displaystyle M_{2}(G)}$, and the multiplicative Zagreb indices ${\displaystyle \Pi _{1}(G)}$ and ${\displaystyle \Pi _{2}(G)}$. ^[1]

References

1. Gutman, Ivan (2018). "Stepwise irregular graphs". Applied Mathematics and Computation. 325: 234–238. doi:10.1016/j.amc.2017.12.045.
2. Alizadeh, Yaser; Klavžar, Sandi; Langari, Javaher (2024). "Extremal results on k-stepwise irregular graphs". arXiv: 2411.15765 [math.CO].
3. Bera, Somnath; Paul, Prithwineel (2018). "Properties of stepwise irregular graphs". arXiv: 1809.03297 [math.CO].
4. Albertson, M. O. (1997). "The irregularity of a graph" (PDF). Ars Combinatoria. 46: 219–225.