Vol. 8, No. 4, 2015

Download this article
Download this article For screen
For printing
Recent Issues

Volume 11
Issue 3, 361–540
Issue 2, 181–359
Issue 1, 1–179

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
About the Journal
Subscriptions
Editorial Board
Editors’ Addresses
Editors’ Interests
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Editorial Login
Author Index
Coming Soon
Contacts
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
The $\Delta^2$ conjecture holds for graphs of small order

Cole Franks

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

An L(2,1)-labeling of a simple graph G is a function f : V (G) such that if xy E(G), then |f(x) f(y)| 2, and if the distance between x and y is two, then |f(x) f(y)| 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,,λ2,1(G)}. We prove that λ2,1(G) Δ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 Δ2 + 1, Δ 1, and

|V (G)| (L Δ)(L 1 2Δ + 1) 1,

then λ2,1(G) 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