Vol. 8, No. 3, 2015

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

Volume 11, 1 issue

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
Cover Page
Editorial Board
Editors’ Addresses
Editors’ Interests
About the Journal
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Subscriptions
Editorial Login
Author Index
Coming Soon
Contacts
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
On distance labelings of amalgamations and injective labelings of general graphs

Nathaniel Karst, Jessica Oehrlein, Denise Sakai Troxell and Junjie Zhu

Vol. 8 (2015), No. 3, 535–540
Abstract

An L(2,1)-labeling of a graph G is a function assigning a nonnegative integer to each vertex such that adjacent vertices are labeled with integers differing by at least 2 and vertices at distance two are labeled with integers differing by at least 1. The minimum span across all L(2,1)-labelings of G is denoted λ(G). An L(2,1)-labeling of G and the number λ(G) are defined analogously, with the additional restriction that the labelings must be injective. We determine λ(H) when H is a join-page amalgamation of graphs, which is defined as follows: given p 2, H is obtained from the pairwise disjoint union of graphs H0,H1,,Hp by adding all the edges between a vertex in H0 and a vertex in Hi for i = 1,2,,p. Motivated by these join-page amalgamations and the partial relationships between λ(G) and λ(G) for general graphs G provided by Chang and Kuo, we go on to show that λ(G) = max{nG 1,λ(G)}, where nG is the number of vertices in G.

Keywords
$L(2,1)$-labeling, distance two labeling, injective $L(2,1)$-labeling, amalgamation of graphs, channel assignment problem
Mathematical Subject Classification 2010
Primary: 68R10, 94C15
Secondary: 05C15, 05C78
Milestones
Received: 3 February 2014
Revised: 24 May 2014
Accepted: 31 May 2014
Published: 5 June 2015

Communicated by Jerrold Griggs
Authors
Nathaniel Karst
Mathematics and Sciences Division
Babson College
Babson Park, MA 02457
United States
Jessica Oehrlein
Franklin W. Olin College of Engineering
Olin Way
Needham, MA 02492
United States
Denise Sakai Troxell
Mathematics and Sciences Division
Babson College
Babson Park, MA 02457
United States
Junjie Zhu
Department of Electrical Engineering
Stanford University
Stanford, CA 94305
United States