On distance labelings of amalgamations and injective labelings of general graphs

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

doi:10.2140/involve.2015.8.535

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

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

DOI: 10.2140/involve.2015.8.535

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 \geq 2$ , $H$ is obtained from the pairwise disjoint union of graphs $H_{0}, H_{1}, \dots, H_{p}$ by adding all the edges between a vertex in $H_{0}$ and a vertex in $H_{i}$ for $i = 1, 2, \dots, 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 {n_{G} - 1, λ (G)}$ , where $n_{G}$ 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

Vol. 8, No. 3, 2015