(2,1)-Total labeling of planar graphs with large maximum degree

Yong Yu, Xin Zhang, Guanghui Wang, Jinbo LiarXiv 2011 · arXiv · OpenReview

Abstract

The ($d$,1)-total labelling of graphs was introduced by Havet and Yu. In this paper, we prove that, for planar graph $G$ with maximum degree $\Delta \geq 12$ and $d=2$, the (2,1)-total labelling number $\lambda_2^T(G)$ is at most $\Delta+2$.

Introduction

Graph labeling is a cornerstone of combinatorics, with significant implications for real-world systems like wireless frequency assignment and circuit layout. A (d,1)-total labeling assigns integers (colors) to both vertices and edges of a graph $G$ such that:

  1. Adjacent vertices receive distinct colors.
  2. Adjacent edges receive distinct colors.
  3. A vertex and any edge incident to it receive colors with a difference of at least $d$.

The minimum number of colors required for such a labeling is denoted by $\lambda_d^T(G)$. Havet and Yu proposed the (d,1)-Total Labeling Conjecture, which posits that $\lambda_d^T(G) \leq \Delta + 2d - 1$, where $\Delta$ is the maximum degree of the graph. For $d=2$, this conjecture suggests a bound of $\Delta + 3$. This research focuses on improving this bound specifically for planar graphs with $\Delta \geq 12$.

Methodology: Discharging and Reducibility

The proof utilizes a standard technique in planar graph theory: the discharging method applied to a minimal counterexample.

Minimal Counterexample and Reducible Configurations

The authors assume the existence of a planar graph $G$ with $\Delta \geq 12$ that violates the theorem ($\lambda_2^T(G) > \Delta + 2$). They select a "minimal" such graph in terms of the number of vertices and edges. A key step is identifying reducible configurations—subgraphs that cannot exist within this minimal counterexample. If such a configuration were present, the graph could be reduced to a smaller one that is already labeled, and that labeling could then be extended back to the original graph, contradicting its minimality.

Examples of reducible configurations (c), (d), (e1), and (e2) used in the structural analysis of the minimal counterexample.

For example, the analysis proves constraints on vertex degrees; a vertex with degree 4 must be adjacent to vertices with significantly higher degrees (at least 8) to maintain the labeling constraints.

The Discharging Process

Following the structural analysis, the authors apply the discharging method. Initial "charges" are assigned to vertices and faces based on their degrees, derived from Euler's formula ($|V| - |E| + |F| = 2$). In any planar graph, the sum of these charges is negative (-8). By defining specific rules to redistribute (discharge) these values, the authors demonstrate that if the graph contains no reducible configurations, every vertex and face must end up with a non-negative charge. This results in a contradiction (a sum of non-negative values cannot be -8), thereby proving that the minimal counterexample cannot exist.

Key Results

The primary contribution of this work is the Main Theorem: For any planar graph $G$ with maximum degree $\Delta \geq 12$, the (2,1)-total labeling number $\lambda_2^T(G)$ is at most $\Delta + 2$.

This result is significant because:

  • Tightness: Given that the lower bound $\Delta + 1$ is trivial, the labeling number is constrained within a very narrow range ($\Delta + 1$ or $\Delta + 2$).
  • Planar Constraints: It shows that the structural properties of planarity allow for a tighter bound than the $\Delta + 3$ predicted by the general conjecture for $d=2$.
  • Generalization: The proof extends to graphs embedded in surfaces with a non-negative Euler characteristic, such as the torus or Klein bottle, provided $\Delta \geq 12$.

Discussion and Future Directions

The reliance on a high maximum degree ($\Delta \geq 12$) is a central limitation. High-degree vertices are essential in the discharging phase, acting as sources of charge for lower-degree neighbors. Future research could explore whether this threshold can be lowered (e.g., for $3 \leq \Delta < 12$) or if similar techniques can be applied to higher values of $d$ in the (d,1)-total labeling context. While this work strongly supports the (d,1)-Total Labeling Conjecture for a specific class of graphs, the general conjecture remains an open challenge.

Summary updated

Abstract

The ($d$,1)-total labelling of graphs was introduced by Havet and Yu. In this paper, we prove that, for planar graph $G$ with maximum degree $Δ\geq12$ and $d=2$, the (2,1)-total labelling number $λ_2^T(G)$ is at most $Δ+2$.
BibTeX
@misc{yu2011total,
  author = {Yong Yu and Xin Zhang and Guanghui Wang and Jinbo Li},
  title = {{(2,1)-Total labeling of planar graphs with large maximum degree}},
  year = {2011},
  eprint = {1105.1908},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1105.1908},
}

Loading related content...

Figure