Total Vertex Irregularity Strength of Cubic and 4-Regular Graphs

@misc{shan2026total,
  title = {{Total Vertex Irregularity Strength of Cubic and 4-Regular Graphs}},
  author = {Songling Shan and Yucheng Zhong},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.30114},
  eprint = {2609.30114},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.30114},
}

TY  - UNPB
TI  - Total Vertex Irregularity Strength of Cubic and 4-Regular Graphs
AU  - Songling Shan
AU  - Yucheng Zhong
PY  - 2026
DA  - 2026/09/24
PB  - arXiv
DO  - 10.48550/arxiv.2609.30114
UR  - https://arxiv.org/abs/2609.30114
AB  - Let G be a graph and k be a positive integer. A total k-labeling of G assigns to each vertex and each edge a label from {1,…,k}. The weight of a vertex is the sum of its label and the labels of its incident edges. A total labeling is vertex irregular if all vertex weights are distinct. The total vertex irregularity strength tvs(G) is the smallest k for which G has a vertex irregular total k-labeling. For an r-regular graph G on n vertices, a counting argument gives tvs(G)≥⌈(n+r)/(r+1)⌉. The restriction of a conjecture of Nurdin, Baskoro, Salman, and Gaos to regular graphs asserts that this bound is attained. We prove this assertion for cubic and $4$-regular graphs. We also show that, for every fixed r≥2, a recent theorem on prescribed degree frequencies implies the assertion for all sufficiently large r-regular graphs.
ER  -