Rank numbers of graphs that are combinations of paths and cycles

Blake, Brianna; Field, Elizabeth; Jacob, Jobby

doi:10.2140/involve.2013.6.369

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

Rank numbers of graphs that are combinations of paths and cycles

Brianna Blake, Elizabeth Field and Jobby Jacob

Vol. 6 (2013), No. 3, 369–381

DOI: 10.2140/involve.2013.6.369

Abstract

A $k$ -ranking of a graph $G$ is a function $f : V (G) \to {1, 2, \dots, k}$ such that if $f (u) = f (v)$ , then every $u$ - $v$ path contains a vertex $w$ such that $f (w) > f (u)$ . The rank number of $G$ , denoted $χ_{r} (G)$ , is the minimum $k$ such that a $k$ -ranking exists for $G$ . It is shown that given a graph $G$ and a positive integer $t$ , the question of whether $χ_{r} (G) \leq t$ is NP-complete. However, the rank number of numerous families of graphs have been established. We study and establish rank numbers of some more families of graphs that are combinations of paths and cycles.

Keywords

ranking, $k$-ranking, rank number, paths, cycles

Mathematical Subject Classification 2010

Primary: 05C15, 05C78

Secondary: 05C38

Milestones

Received: 25 April 2013

Accepted: 29 July 2013

Published: 8 September 2013

Communicated by Joseph A. Gallian

Authors

Brianna Blake
Mathematics Department Augsburg College Minneapolis, MN 55454 United States

Elizabeth Field
Department of Mathematics Southern Connecticut State University New Haven, CT 06515 United States

Jobby Jacob
School of Mathematical Sciences Rochester Institute of Technology Rochester, NY 14623 United States

Vol. 6, No. 3, 2013