The irregularity strength of dense graphs -- on asymptotically optimal solutions of problems of Faudree, Jacobson, Kinch and Lehel
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929385694560256 |
|---|---|
| author | Przybyło, Jakub |
| author_facet | Przybyło, Jakub |
| contents | The irregularity strength of a graph $G$, $s(G)$, is the least $k$ such that there exists a $\{1,2,\ldots,k\}$-weighting of the edges of $G$ attributing distinct weighted degrees to all vertices, or equivalently the least $k$ enabling obtaining a multigraph with nonrecurring degrees by blowing each edge $e$ of $G$ to at most $k$ copies of $e$. In 1991 Faudree, Jacobson, Kinch and Lehel asked for the optimal lower bound for the minimum degree of a graph $G$ of order $n$ which implies that $s(G)\leq 3$. More generally, they also posed a similar question regarding the upper bound $s(G)\leq K$ for any given constant $K$. We provide asymptotically tight solutions of these problems by proving that such optimal lower bound is of order $\frac{1}{K-1}n$ for every fixed integer $K\geq 3$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_09584 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The irregularity strength of dense graphs -- on asymptotically optimal solutions of problems of Faudree, Jacobson, Kinch and Lehel Przybyło, Jakub Combinatorics 05C15, 05C78 The irregularity strength of a graph $G$, $s(G)$, is the least $k$ such that there exists a $\{1,2,\ldots,k\}$-weighting of the edges of $G$ attributing distinct weighted degrees to all vertices, or equivalently the least $k$ enabling obtaining a multigraph with nonrecurring degrees by blowing each edge $e$ of $G$ to at most $k$ copies of $e$. In 1991 Faudree, Jacobson, Kinch and Lehel asked for the optimal lower bound for the minimum degree of a graph $G$ of order $n$ which implies that $s(G)\leq 3$. More generally, they also posed a similar question regarding the upper bound $s(G)\leq K$ for any given constant $K$. We provide asymptotically tight solutions of these problems by proving that such optimal lower bound is of order $\frac{1}{K-1}n$ for every fixed integer $K\geq 3$. |
| title | The irregularity strength of dense graphs -- on asymptotically optimal solutions of problems of Faudree, Jacobson, Kinch and Lehel |
| topic | Combinatorics 05C15, 05C78 |
| url | https://arxiv.org/abs/2406.09584 |