![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
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.
1 Introduction
Let be an undirected graph with no loops and no multiple edges. A function
is a (vertex)
-ranking of
if for
,
implies that every
path contains a vertex
such that
. By definition, every ranking is a proper coloring. The rank number of
, denoted
, is the minimum value of
such that
has a
-ranking. For a graph
, by optimal
-ranking we mean a
-ranking such that
. When the value of
is not important, we will call a
-ranking simply a ranking. It is known that
and
.
Vertex rankings of graphs are applicable to a plethora of other fields including designs of very large scale integration (VLSI) layouts, Cholesky factorizations of matrices in parallel, wi-fi analytics, and scheduling problems of assembly steps in manufacturing systems. The optimal tree node ranking problem is identical to the problem of generating a minimum height node separator tree for a tree. Node separator trees are extensively used in VLSI layout Citation[1]. Ranking of graphs is used in communication networks in which information flow between the nodes has to be monitored. An application of graph ranking to scheduling of assembly steps in manufacturing system is discussed in Citation[2].
The concept of ranking was introduced by Iyer et al., in Citation[3], for trees. It is shown by Bodlaender et al., in Citation[4], that for a graph and a positive integer
the question of whether
is NP-complete. The mathematical studies of vertex rankings were initiated by Ghoshal and Laskar in Citation[5]. Since then, the rank number of numerous families of graphs have been established, for example see Citation[6–14]. A generalization of
-ranking using the
norm is discussed in [Citation15].
Let be a graph of order
. We know that
. In this paper, we study the rankings of subdivided stars and identify graphs with large rank numbers. The rank number of a subdivided star is either
or
, where
is the longest path in the subdivided star. We characterize subdivided stars based on their rank numbers, and hence establish the rank number of a subdivided star. We also identify graphs with rank number
or
.
Let be a graph and let
be a subgraph of
. Throughout this paper, the graph
represents the graph obtained by deleting
from
. If
, then
denotes the graph obtained by deleting the vertices in
from
, that is, the subgraph induced by
. For any labeling
of a graph
, let
. Throughout this paper, we assume that for any optimal
-ranking
,
for
because of Lemma 1.1.
Lemma 1.1
Citation[5] There is an optimal ranking of
such that
.
Lemma 1.2
Citation[5] Let be a subgraph of
. Then
.
Lemma 1.3
[Citation14] Let and
be two vertex disjoint graphs such that
. Let
be a connected supergraph of
. Then
.
Lemma 1.4
Citation[5] Let be a graph of order
and let
be an independent set of
. Then
.
Theorem 1.5
Citation[4] , where
is a path on
vertices.
2 Subdivided stars
Let be a positive integer, and let
be positive integers. Let the edges of a complete bipartite graph
be
. For
, subdivide edge
times to obtain a subdivided star denoted by
. We consider the subdivided edges as paths,
, and refer to them as branches.
We can use a binary matrix to represent a subdivided star. For a subdivided star, , where
, construct an
matrix
where row
is the binary representation of
. An example of a subdivided star and its associated matrix
is given in . Using this binary representation of subdivided stars, we characterize subdivided stars based on their rank numbers.
Lemma 2.1
, where
.
Proof
Since is a subgraph of
,
.
Label the center vertex , and branch
using labels
. Since
, this will produce a ranking using
labels. Thus
.□
Theorem 2.2
For any subdivided star , with
,
Proof
Note that, since and
is a longest branch, the column
will contain at least one 1. Assume that for some
,
and
,
contains exactly one
. If
, then there would be two 1’s in the first column of
, which contradicts the assumption. Thus branch
is the only branch with rank number
.
Let and
. Label the outermost
vertices in
with
labels. Label the next outermost vertex,
, with label
. We have now labeled
vertices on the branch
so the number of vertices left unlabeled has the same binary representation as
but without the leading
. Remove the
labeled vertices on
from
. Now we have a new subdivided star,
for
, where
. Note that any path between vertices in
and the deleted vertices from
must contain the vertex labeled
. Also,
, since
has exactly one
. The matrix
can be considered a
matrix with the first column consisting of all zeros and the last
columns the same as that of
. Repeat this process until we get the
matrix. The matrix
will have zeros on the first
columns and the last
columns the same as that of
. Note that column
of
has all zeros.
At this point none of the branches of the subdivided star have a rank number greater than
, (because the first
columns of
are zeros), where
is the longest branch of the original subdivided star
. Label the branches of
using
labels or less and label the middle vertex
.
An example of this procedure is shown in . Note that in each of these figures the vertices with labels are the vertices that were deleted from the previous subdivided star.
Now any path between vertices in and the vertices deleted from
must contain the largest labeled vertex,
, that was deleted from the largest branch of
. Also note that
will not have a vertex labeled the same as the label of
because there is exactly one
in each of the first
columns of
. Therefore, this labeling will create a ranking using only
labels. This implies
, and hence, by Lemma 2.1,
.
Let and let
be an optimal labeling of
. Assume there is no
such that
and
,
contains only one 1. Let column
contain more than one 1 where
. Let
contain exactly one 1.
If , then
. Then by Lemma 1.3,
, a contradiction.
Suppose . Then, since
must use label
on the branch
, and the largest label can only be used once,
, where
is the middle vertex. When optimally ranking
, the vertex with the highest label of any branch can be placed as close to the middle vertex as possible while still maintaining optimality. Therefore, without loss of generality, assume that
has such property.
Now, follow the process defined earlier to create the subdivided star and matrix
whose first
columns contain zeros and the remaining
columns are the same as that of
. Note that in this process, the rank number of the largest branch in
is one less than the rank number of the longest branch in
where
(because the first
columns of
have exactly one 1). Thus the longest branch of
will have rank number
, and thus
. However, the column
has at least two
s, which means that there are at least two branches of
with rank number
. Then
, a contradiction.
If every column of has exactly one
, then using the above process we get
which is a contradiction.
Thus there is an such that
and
,
contains only one 1.□
3 Graphs with large rank numbers
We will first characterize graphs with rank number , where
is the order of the graph. In this section, we use the notation
to mean that
is a subgraph of
.
Lemma 3.1
Let be a graph of order
, and let
be a subgraph of
such that
. If
then
.
Proof
Let be a ranking of
such that
. Now extend
to a ranking of
by assigning distinct labels from the set
to vertices in
.□
Theorem 3.2
if and only if
,
, and
.
Proof
Let ,
, and
. Since
,
.
Consider a ranking of
. Suppose there exist vertices
such that
. Then
is an independent set in
, and hence form a
in
, which is a contradiction. Therefore, no label can appear three times or more under
.
Now, suppose there are vertices such that
and
, and without loss of generality, assume that
. Then
and
since
is a ranking of
. Moreover, since
and
, there exists at most one edge in
that has endpoints
or
and
or
. This implies that in
either
or
is a path that violates the requirements of a ranking, a contradiction. Therefore two labels cannot appear more than once under
. Since no label can be used three times and two labels cannot be used more than once,
. Therefore,
.
Now, suppose . Then
as
. If
, and
form
in
, then
,
form an independent set in
and thus, by Lemma 1.4,
, a contradiction. Lastly, assume that
. We know that
, and thus, by Lemma 3.1,
, a contradiction.□
From Theorem 3.2 we get the following corollaries.
Corollary 3.3
if and only if
,
, and
.
Corollary 3.4
For a tree on
vertices,
.
We now look at the characteristics of graphs with rank number , where
is the order of the graph. Let
, where
is a wheel on
vertices with center vertex
and
is a vertex in
. Note that
has two components, a
and a
and hence we have the following observation.
Observation 3.5
.
Since the graph has two
as components, we have the following observation.
Observation 3.6
.
Theorem 3.7
if and only if
or
,
,
and
.
Proof
Suppose that . If
and
, then either
or, by Theorem 3.2,
. If
, then
contains an independent set of size
, and thus, by Lemma 1.4,
. If either
or
, then by Observations 3.5 and 3.6 and by Lemma 3.1, we get
. Thus if
then
or
,
,
and
.
Let or
,
,
and
. Since
, or
, as discussed in the proof of Theorem 3.2, we can find a ranking
of
with
. Thus
.
Suppose that . Let
be an optimal ranking of
. Then, since
, one of the following three cases must occur.
Case 1: There exist vertices such that
. This means that these vertices form a
in
, a contradiction.
Case 2: There exist vertices such that
and
. Then the vertices
must form a
in
and the vertices
must be adjacent in
. Also, each of
must be adjacent to either
or
in
. (If
were adjacent to neither
nor
for some
then the path
would exist in
, making
not a ranking.) If each of the
’s is adjacent to the same
for some
then
, and
form a
in
. If, without loss of generality,
,
,
, and
, then the subgraph of
induced by
, and
contains a
with
as the center vertex. However, we assumed that
and
.
Case 3: There exist vertices such that
,
, and
. Then
. Let
,
, and
. Since
is a ranking, paths such as
or
, or
do not exist in
, and thus in
there must be at least two edges between every
and
, for all
. Moreover, the subgraph of
induced by
must be disconnected, since the highest label
is used twice in the subgraph. This means
is disconnected, where
is the subgraph of
induced by
. Thus
must contain one of the four graphs on six vertices given in .
Note that the first three graphs contain as a subgraph, and the last graph is a
. This is a contradiction, as we assumed that
and
.
Therefore, , and thus
.□
Corollary 3.8
if and only if
or
,
,
and
.
4 Conclusion
Finding the rank number of a general graph is known to be extremely difficult. In this paper, we identified graphs with rank numbers and
, where
is the order of the graph. The idea we used for finding
would still work for classifying graphs with smaller rank numbers. However, the number of labeling schemes that needs to be considered grows exponentially as the rank number decreases. Each of the labeling scheme produces multiple forbidden subgraphs, and hence this method, while not incorrect, will not be feasible for classifying graphs with smaller rank numbers. An interesting related question would be to identify the minimum number of edges required in an
vertex graph
such that rank number of
is either
or
. We also characterized subdivided stars based on their rank numbers, thus establishing the rank number of all subdivided stars. Rankings of some other classes of trees have also been studied by others, for example see Citation[7,10,14], however, the rank number of an arbitrary tree has not been established.
References
- LeisersonC., Area efficient graph layouts for VLSI Proc. 21st Ann IEEE Symp. FOCS1980 270–281
- IyerA.V.RatliffH.D.VijayanG., On an edge ranking problem of trees and graphs Discrete Appl. Math. 30 1 1991 43–52
- IyerA.V.RatliffH.D.VijayanG., Optimal node ranking of trees Inform. Process. Lett. 28 5 1988 225–229
- BodlaenderH.L.DeogunJ.S.JansenK.KloksT.KratschD.MüllerH.TuzaZ., Rankings of graphs Graph-Theoretic Concepts in Computer Science (Herrsching, 1994)Lecture Notes in Comput. Sci. vol. 9031995SpringerBerlin292–304
- GhoshalJ.LaskarR.PilloneD., Minimal rankings Networks 28 1 1996 45–53
- AlpertH., Rank numbers of grid graphs Discrete Math. 310 23 2010 3324–3333
- BlakeB.FieldE.JacobJ., Rank numbers of graphs that are combinations of paths and cycles Involve A J. Math. 6 3 2013 369–381
- BruothE.HorňákM., On-line ranking number for cycles and paths Discuss. Math. Graph Theory 19 2 1999 175–197The Seventh Workshop “3in1” Graphs ’98 (Krynica)
- DereniowskiD.NadolskiA., Vertex rankings of chordal graphs and weighted trees Inform. Process. Lett. 98 3 2006 96–100
- HsiehS., On vertex ranking of a starlike graph Inform. Process. Lett. 82 3 2002 131–135
- NovotnyS.OrtizJ.NarayanD.A., Minimal k-rankings and the rank number of Pn2 Inform. Process. Lett. 109 3 2009 193–198
- OrtizJ.ZemkeA.KingH.NarayanD.HorňákM., Minimal k-rankings for prism graphs Involve 3 2 2010 183–190
- RichterP.LevenE.TranA.EkB.JacobJ.NarayanD.A., Rank numbers for bent ladders Discuss. Math. Graph Theory 34 2 2014 309–329
- SergelE.RichterP.TranA.CurranP.JacobJ.NarayanD.A., Rank numbers for some trees and unicyclic graphs Aequationes Math. 82 1–2 2011 65–79
- JacobB.C.JacobJ., lp-Optimal rankings and max-optimal rankings are different Graphs Combin. 33 6 2017 1473–1483