Total Vertex Irregularity Strength of Cubic and 4-Regular Graphs

Songling Shan; Yucheng Zhong

En palabras de los autores

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, \dots, 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 $t v s (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 $t v s (G) \geq ⌈(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 \geq 2$ , a recent theorem on prescribed degree frequencies implies the assertion for all sufficiently large $r$ -regular graphs.

Resultado principalLimitación que admiten los autores

Total Vertex Irregularity Strength of Cubic and 4-Regular Graphs

En palabras de los autores

Más de Combinatoria y matemática discreta ese día

Thinning and sprinkling: from robust sampling to almost Hamiltonicity

Boolean threshold functions, neuron capacity, and memory retrieval

The Marcus-Minc Transform Inequality

The coarse Erd\H{o}s-P\'{o}sa theorem

A Combinatorial Proof of Hilton's Conjecture and Beyond