Extremal results on $k$-stepwise irregular graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909949773217792 |
|---|---|
| author | Alizadeh, Yaser Klavžar, Sandi Langari, Javaher |
| author_facet | Alizadeh, Yaser Klavžar, Sandi Langari, Javaher |
| contents | For a positive integer $k\ge 1$, a graph $G$ is $k$-stepwise irregular ($k$-SI graph) if the degrees of every pair of adjacent vertices differ by exactly $k$. Such graphs are necessarily bipartite. Using graph products it is demonstrated that for any $k\ge 1$ and any $d \ge 2$ there exists a $k$-SI graph of diameter $d$. A sharp upper bound for the maximum degree of a $k$-SI graph of a given order is proved. The size of $k$-SI graphs is bounded in general and in the special case when $\gcd(Δ(G), k) = 1$. Along the way the degree complexity of a graph is introduced and used. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_15765 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Extremal results on $k$-stepwise irregular graphs Alizadeh, Yaser Klavžar, Sandi Langari, Javaher Combinatorics For a positive integer $k\ge 1$, a graph $G$ is $k$-stepwise irregular ($k$-SI graph) if the degrees of every pair of adjacent vertices differ by exactly $k$. Such graphs are necessarily bipartite. Using graph products it is demonstrated that for any $k\ge 1$ and any $d \ge 2$ there exists a $k$-SI graph of diameter $d$. A sharp upper bound for the maximum degree of a $k$-SI graph of a given order is proved. The size of $k$-SI graphs is bounded in general and in the special case when $\gcd(Δ(G), k) = 1$. Along the way the degree complexity of a graph is introduced and used. |
| title | Extremal results on $k$-stepwise irregular graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2411.15765 |