Total edge irregularity strength of cubic graphs
We show that every finite simple cubic graph on $n$ vertices has total edge irregularity strength $n/2+1$, confirming the Ivančo-Jendrol' conjecture for cubic graphs. The key step is to algorithmically construct a $\{1,n/2+1\}$-vertex labeling such that half of the vertices are labeled $1$ and the average degree of the subgraph induced by them is close enough to two. We extend such a labeling to a total edge irregular $(n/2+1)$-labeling, possibly after a local adjustment to a single vertex.
Authors
- Suhadi Wido Saputro (ORCID: https://orcid.org/0000-0003-3886-400X)
- Aleams Barra (ORCID: https://orcid.org/0000-0001-8618-4821)
- Hajime Tanaka
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-12
- DOI
- https://doi.org/10.48550/arxiv.2611.16338
- Primary Topic
- Graph Labeling and Dimension Problems
- Type
- preprint