The Δ2 conjecture holds for graphs of small order

Franks, Cole

doi:10.2140/involve.2015.8.541

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

The $\Delta^2$ conjecture holds for graphs of small order

Cole Franks

Vol. 8 (2015), No. 4, 541–549

DOI: 10.2140/involve.2015.8.541

Abstract

An $L (2, 1)$ -labeling of a simple graph $G$ is a function $f : V (G) \to ℤ$ such that if $x y \in E (G)$ , then $| f (x) - f (y) | \geq 2$ , and if the distance between $x$ and $y$ is two, then $| f (x) - f (y) | \geq 1$ . $L (2, 1)$ -labelings are motivated by radio channel assignment problems. Denote by $λ_{2, 1} (G)$ the smallest integer such that there exists an $L (2, 1)$ -labeling of $G$ using the integers ${0, \dots, λ_{2, 1} (G)}$ . We prove that $λ_{2, 1} (G) \leq Δ^{2}$ , where $Δ = Δ (G)$ , if the order of $G$ is no greater than $(⌊ Δ ∕ 2 ⌋ + 1) (Δ^{2} - Δ + 1) - 1$ . This shows that for graphs no larger than the given order, the 1992 “ $Δ^{2}$ conjecture” of Griggs and Yeh holds. In fact, we prove more generally that if $L \geq Δ^{2} + 1$ , $Δ \geq 1$ , and

| V (G) | \leq (L - Δ) (⌊ \frac{L - 1}{2 Δ} ⌋ + 1) - 1,

then $λ_{2, 1} (G) \leq L - 1$ . In addition, we exhibit an infinite family of graphs with $λ_{2, 1} (G) = Δ^{2} - Δ + 1$ .

Keywords

L(2,1)-labeling, graph labeling, channel assignment

Mathematical Subject Classification 2010

Primary: 97K30

Milestones

Received: 15 February 2013

Revised: 15 April 2013

Accepted: 2 October 2013

Published: 23 June 2015

Communicated by Ronald Gould

Authors

Cole Franks
Department of Mathematics Rutgers University Hill Center - Busch Campus 110 Frelinghuysen Road Piscataway, NJ 08854 United States

Vol. 8, No. 4, 2015