Graphs with large rank numbers and rank numbers of subdivided stars

A -ranking of a graph is a function such that if then every path contains a vertex such that . The rank number of , denoted , is the minimum such that a -ranking exists for . It is known that given a graph and a positive integer the question of whether is NP-complete. In this paper we characterize g...

Full description

Saved in:
Bibliographic Details
Published in:AKCE international journal of graphs and combinatorics 2020-01, Vol.ahead-of-print (ahead-of-print), p.1-6
Main Authors: Boynton, Hayley, Burroughs, Ethan, Gaston, Stephanie, Jacob, Jobby
Format: Article
Language:English
Subjects:
Rank number
Stars
Subdivided stars
Vertex ranking
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A -ranking of a graph is a function such that if then every path contains a vertex such that . The rank number of , denoted , is the minimum such that a -ranking exists for . It is known that given a graph and a positive integer the question of whether is NP-complete. In this paper we characterize graphs with large rank numbers. In addition, we characterize subdivided stars based on their rank numbers.
ISSN:0972-8600
2543-3474
DOI:10.1016/j.akcej.2019.03.023