Graphs whose $l_p$-optimal rankings are $l_{\mathrm{\infty }}$ Optimal

1. Introduction

A $k$-ranking (or simply “ranking”) on a graph $G$ is defined to be a function $f:V(G)\to \{1,2,\dots ,k\}$ with the following restriction: if $f(u)=f(v)$ for any $u,v\in V(G)$, then on every $uv$ path in $G$, there exists a vertex $w$ with $f(w)>f(u)$. This vertex labeling problem has generated great interest because of its applications to Cholesky factorization of matrices in parallel [2-4], VLSI layout [5,6] and scheduling steps in manufacturing systems [7,8].

The focus of much of the literature on rankings has been on minimizing $k$. That is, given a graph $G$, the goal is to determine the minimum number of labels required to produce a valid ranking on $G$. The minimum number of labels required to produce a ranking on a graph $G$ is called the rank number of $G$, and is denoted ${\chi }_r(G)$. Note that on a graph $G$, a ranking with ${\chi }_r(G)$ labels is a ranking with smallest $l_{\mathrm{\infty }}$ or max norm.

However, in [9], Jamison and Narayan compare the rank number of $G$ with the lowest possible sum, or $l_1$ norm, of all rankings on $G$. In particular, they show that for paths and cycles, $l_1$-optimal rankings are also max optimal.

The results in [9] give rise to the question of how changing the value of $p$ affects $l_p$ optimality of a ranking. While most commonly known applications of $l_p$ norms with finite $p$ use $p\in \{1,2\}$, some applications have used finite $p$ with $p\notin \{1,2\}$. Some examples include machine learning [10,11], compressed sensing [12], image deconvolution [13], and two-dimensional phase unwrapping [14]. Specific to $k$-rankings on graphs, a graph may have distinct $l_p$-optimal rankings for two different values of $p$, even if both values of $p$ satisfy $1<p<\mathrm{\infty }$. For example, Figures 1–2 display a graph whose sets of $l_2$– and $l_3$-optimal rankings are disjoint.

In [1] we showed that for any $p\ge 0$ and any non-negative integer $c$, we can construct a graph with $c$ cycles such that the sets of $l_p$-optimal and $l_{\mathrm{\infty }}$-optimal rankings are disjoint. In this paper, we show that there are families of graphs including paths, cycles, and complete multipartite graphs such any $l_p$-optimal ranking is also $l_{\mathrm{\infty }}$ optimal for any $p$ with $0\le p<\mathrm{\infty }$.

We will use the notion of minimality of a ranking throughout the paper.

The concept of a reduction, defined by Ghoshal, Laskar and Pillone will also be used throughout.

For a ranking $f$ on a graph $G$, define $S_i(f)$ by $S_i(f)=\{v\in G|f(v)=i\}.$ In general, a reduction can be applied with respect to any set $S\subseteq V(G)$. However, for the purposes of our paper, we primarily consider the case where $S=S_1(f)$ for some ranking $f$ on $G$. When the set $S$ is understood, we denote $G_S^{\mathrm{♭}}$ by $G^{\mathrm{♭}}$.

Because for our purposes the reduction often depends on the ranking we consider, we also define a new ranking associated with $G^{\mathrm{♭}}$ as follows. Let $G$ be a graph, and $f$ a ranking on $G$. For any subgraph $H$ of $G$, we define a ranking $f_H$ by setting $f_H(v)=f(v)$ for all $v\in V(H)$. If $H=G_{S_1(f)}^{\mathrm{♭}}$, set $f_H(v)=f(v)-1$ for all $v\in V(H)$. Note that $f_H$ is a ranking on $H$ and is called a reduction ranking.

We can define a similar labeling if $S\ne S_1(f)$ by setting $f_H(v)=f(v)$ for all $v\in V(H)$ where $H$ is the reduction. However, the resulting labeling is not guaranteed to be a ranking. In this case we call the labeling a reduction labeling. An expansion of $G$ is a graph $G^{\mathrm{♯}}$ such that ${\left(G^{\mathrm{♯}}\right)}_S^{\mathrm{♭}}=G$ for some $S\subseteq V(G^{\mathrm{♯}})$.

Finally, we note the following result from [15].

1.1. Optimality of Rankings

For a graph $G$ with ranking $f$, and $1\le p<\mathrm{\infty }$, the $l_p$ norm of $f$ is given by the $l_p$ norm of the labels of $f$: $$\begin{array}{}\text{(1)}& {\parallel f\parallel }_p={\left(\sum _{v\in V(G)}{[f(v)]}^p\right)}^{1/p}.\end{array}$$ If $p=1$, this describes the norm considered in [9], and $p=2$ corresponds to the standard Euclidean norm. The standard existing norm in the literature on graph rankings is the supremum or max, or $l_{\mathrm{\infty }}$ norm: $${\parallel f\parallel }_{\mathrm{\infty }}=\underset{v\in V(G)}{max}f(v).$$ For $0<p<1$, $||\cdot |{|}_p$ is defined as in (1), but fails to be a norm. The case $p=0$ is considered separately in Section 5.

We refer to a ranking $f$ on $G$ that achieves $||f|{|}_{\mathrm{\infty }}={\chi }_r(G)$ as a max optimal ranking. Given a graph $G$, a ranking $f$ and non-negative real number $p$, we say that $f$ is $l_p$ optimal if $${\parallel f\parallel }_p=min\{{\parallel g\parallel }_p\mid g\text{ is a ranking on }G\}.$$ We define an analog of the rank number to $l_p$ optimality.

1.2. General Results about $l_p$ Optimality

For any non-negative real number $p$, if $f$ is not minimal then we can reduce one of the labels to produce a ranking $\tilde{f}$ with $||\tilde{f}|{|}_p<||f|{|}_p$.

Note that observation 1 does not hold if $p=0$ or $p=\mathrm{\infty }$.

We note here that a graph may have different $l_p$-optimal rankings depending on the value of $p$, even when $p$ is restricted to $1<p<\mathrm{\infty }$, as illustrated by the example shown in Figures 1–2. Figure 1 shows a ranking $f$ that is $l_3$ optimal but not $l_2$ optimal, while Figure 2 shows a ranking $g$ of the same graph that is $l_2$ optimal but not $l_3$ optimal. Since $f(v)=g(v)$ for all $v\in V$ except for the vertex of degree $3$ and vertices $u$ and $w$ with $g(u)=7$ and $g(w)=8$, we can compute that $\parallel g{\parallel }_3^3–\parallel f{\parallel }_3^3=81>0$, but $\parallel f{\parallel }_2^2–\parallel g{\parallel }_2^2=7>0$.

1.3. Organization of This Paper

In Sections 2 and 3, we show any $l_p$-optimal ranking on a path or cycle where $p>0$ is also max optimal, but that the converse does not hold. In Section 4 we show that on a complete multipartite graph a ranking is $l_p$ optimal if and only if it is max optimal. Throughout Sections 2 – 4 we assume $0<p<\mathrm{\infty }$ unless otherwise stated. Finally, in Section 5, we show that if $p=0$, then $l_p$ optimality does not imply max optimality in paths and cycles, but that the result for complete multipartite graphs holds with the added assumption of minimality. We conclude with some open questions in Section 6.

2. Paths

Let $P_n$ denote a path on $n$ vertices, $v_1,v_2,\dots ,v_n$. We can construct a ranking $f$ for $P_n$ in a greedy fashion by starting with $v_1$, and defining $f(v_i)$ to be the lowest label possible without violating the definition of ranking, producing the standard ranking of a path as shown in Figure 3.

Bodlaender et al. [2] showed that ${\chi }_r(P_n)=\lfloor {\log }_{2}n\rfloor +1$ and that the standard ranking $f$ is a max optimal ranking on $P_n$. Note that the standard ranking $f$ on $P_n$ can also be defined by letting $f(v_i)=r+1$ where $r$ is the highest power of 2 that divides $i$.

In this section, we show that any $l_p$-optimal ranking on $P_n$ is also a max optimal ranking. Throughout the section, given a ranking $f$ on $G=P_n$, we use the notation $f^{\mathrm{♭}}$ to refer to the reduction ranking on $G_S^{\mathrm{♭}}$ where $S=S_1(f)$. Similarly, given a ranking $f$ on a path $P_{\lfloor n/2\rfloor }$, we use the notation $f^{\mathrm{♯}}$ to refer to the expansion ranking on $P_n$ formed by adding 1 to all existing labels, inserting a vertex labeled $1$ between each consecutive pair of vertices in $P_{\lfloor n/2\rfloor }$ and to the front of the path, and, if $n$ is odd, adding one more vertex labeled $1$ to the end of the path.

From Lemma 4, we get the following corollary.

Given a path $P_n$, let ${\mathcal{S}}_{j;n}$ denote the set of vertices with label $j$ under the standard ranking on $P_n$.

Figure 4 illustrates that the converse of Theorem 4 does not hold, which we now state formally.

3. Cycles

In [16], Bruoth and Horňák showed the following.

The standard ranking $f$ on the cycle $C_n$ is as follows. Starting with any vertex, label the first $n-1$ vertices $v_1,v_2,\dots ,v_{n-1}$ greedily in a clockwise direction. Thus, the first $n-1$ vertices are labeled as the standard ranking on $P_{n-1}$. Then the final vertex $v_n$ is labeled $f(v_n)={\chi }_r(P_{n-1})+1$. It is well known that the standard ranking $f$ on a cycle $C_n$ is a max optimal ranking.

Throughout this section, given a ranking $f$ on $G=C_n$, we use $f^{\mathrm{♭}}$ to denote the reduction ranking on $G_S^{\mathrm{♭}}$ where $S=S_1(f)$. Given a ranking $g$ on $C_{\lceil n/2\rceil }$, we use $g^{\mathrm{♯}}$ to denote the expansion ranking on $C_n$ obtained as follows: add $1$ to all labels, then insert $\lfloor n/2\rfloor$ vertices labeled $1$, one between each consecutive pair of vertices in $C_{\lceil n/2\rceil }$. If $n$ is odd, there will be one pair of consecutive vertices in $C_{\lceil n/2\rceil }$ that do not receive a new vertex between them. For consistency, we omit the new vertex just before the vertex with highest label in $C_{\lceil n/2\rceil }$.

Using similar arguments to the proof of Lemma 3, and applying Lemma 2, we get the following lemma.

The converse of Theorem 6 does not hold, as we demonstrate with the following proposition.

4. Graphs for which Max Optimality Implies $l_p$ Optimality

We have shown that for paths and cycles, $l_p$ optimality implies max optimality, but that max optimality does not necessarily imply $l_p$ optimality. We now show that for any complete multipartite graph $K_{m_1,m_2,\dots ,m_r}$ with partite sets of order $m_1\ge m_2\ge \cdots \ge m_r$, the set of $l_p$-optimal rankings and the set of max optimal rankings are the same.

By noting the a complete graph is a complete multipartite graph $K_{m_1,m_2,\dots m_r}$ with $m_1=m_2=\cdots m_r=1$, we get the following immediate corollary.

5. The Special Case of $p=0$

Given a sequence of numbers, the $l_0$ “norm” is defined as the number of non-zero terms in the sequence. For a graph $G$ with ranking $f$, $$||f|{|}_0=\left|\{v\in V(G)\mid f(v)>0\}\right|.$$ The quotation marks indicate that the map fails to satisfy the requirement of homogeneity. Depending on the application [17-20] it is referred to as the zero, counting or Hamming “norm.”

In this section, we use labels $0$ through $k-1$ instead of $1$ through $k$, because starting with $1$ leads to $||f|{|}_0=|V(G)|$ for every ranking $f$ on $G$. We do this on the standard rankings on paths and cycles as well, subtracting $1$ from each label in the standard ranking. For reductions and expansions, we remove or add vertices with label $0$ instead of $1$.

The arank number of a graph $G$, denoted ${\psi }_r(G)$, is given by ${\psi }_r(G)=max\{||f|{|}_{\mathrm{\infty }}\}$ over any minimal ranking $f$ on $G$.

The following theorem shows that neither Theorem 4 nor its converse applies if $p=0$.

Neither Theorem 6 nor its converse applies to the case $p=0$, as shown by the following theorem.

Figure 10 shows a minimal $l_0$-optimal ranking on $C_{14}$ that is not max optimal. Figure 11 shows the standard ranking on $C_{14}$, which is max optimal.

Finally, we show that unlike paths and cycles, complete multipartite graphs have the same property with regard to $l_0$ optimality as with $l_p$ optimality, as long as we require minimality of the $l_0$-optimal ranking.

6. Conclusion and Open Problems

For paths and cycles, we have shown that $l_p$ optimality of a ranking implies max optimality for all $p>0$. For $p=0$, we have shown that this does not hold. We have also shown that max optimality does not imply $l_p$ optimality for these graphs. For complete multipartite graphs, however, we showed that the set of $l_p$-optimal rankings is the same as the set of max optimal rankings, including in the case $p=0$ if we restrict $l_0$-optimal rankings to be minimal.

In [1], we constructed graphs — including trees — whose $l_p$-optimal rankings and max optimal rankings are disjoint. The construction included a cut vertex whose removal resulted in a graph with three components. One question to investigate is whether any graph that has $l_p$-optimal rankings and max optimal rankings disjoint must have a cut vertex. Another potential problem is to consider the analog of an arank number ${\psi }_r(G)$ of a graph $G$ under a norm different from the max norm. For example, on a graph $G$, among all minimal rankings $f$, what is the largest possible $l_1$ norm, or in other words, what is $\underset{f}{max}\sum _{i=1}^{|V(G)|}f(v)$? Finally, can we characterize graphs that have $l_p$ optimality and max optimality equivalent, as with the complete multipartite graph?

Conflict of Interest

The authors declare no conflict of interest.