Tree t-Spanners of a Graph: Minimizing Maximum Distances Efficiently

Abstract

A tree t-spanner of a graph G is a spanning subtree T in which the distance between any two adjacent vertices of G is at most t. The smallest t for which G has a tree t-spanner is the tree stretch index. The problem of determining the tree stretch index has been studied by: establishing lower and upper bounds, based, for instance, on the girth value and on the minimum diameter spanning tree problem, respectively; and presenting some classes for which t is a tight value. Moreover, in 1995, the computational complexities of determining whether $t = 2$ or $t \ge 4$ were settled to be polynomially time solvable and NP-complete, respectively, while deciding if $t = 3$ still remains an open problem.

With respect to the computational complexity aspect of this problem, we present an inconsistence on the sufficient condition of tree 2-spanner admissible graphs. Moreover, while dealing with operations in graphs, we provide optimum tree t-spanners for 2 cycle-power graphs and for prism graphs, which are obtained from 2 cycle-power graphs after removing a perfect matching. Specifically, the stretch indexes for both classes are far from their girth’s natural lower bounds, and surprisingly, the parameter does not change after such a matching removal. We also present efficient strategies to obtain optimum tree t-spanners considering threshold graphs, split graphs, and generalized octahedral graphs. With this last result in addition to vertices addition operations and the tree decomposition of a cograph, we are able to present the stretch index for cographs.

This work was partially supported by the Brazilian agencies CAPES, CNPq and FAPERJ.

1 Introduction

The problems of obtaining subgraphs with special restrictions have been considered in several papers, with many motivations and applications in different fields, as message routing, computational geometry, and phylogenetic analysis [1,2,3]. In addition to the inherent difficulty of these problems, another challenge arises when we look for a spanning tree with constraints on the vertices’ distances.

A tree t-spanner of a graph G is defined as a spanning subtree T of G in which the distance between every pair of vertices is at most t times their distance in G or, equivalently, as the subtree T in which the distance between two adjacent vertices of G is at most t (cf. [4]). If a graph has a tree t-spanner, then it is called a tree t-spanner admissible graph. The parameter t of a tree t-spanner is called the tree stretch factor, and the smallest t for which a graph G is tree t-spanner admissible is called the tree stretch index of G, denoted by $\sigma _T(G)$.

Note that the problem of determining the tree stretch index of G, called the minimum stretch spanning tree problem (MSST), is one of the interesting min-max problems, which are studied not only in graphs, but in several other combinatorial problems, in such a way that bounds, algorithms and computational complexity studies are widely developed [5, 6].

An intriguing aspect comes when we want to determine if a graph is tree 3-spanner admissible. In terms of the computational complexity, this task is still the greatest breakthrough we aim to solve, since deciding if $\sigma _T(G) \ge 4$ is NP-complete, whereas for $\sigma _T(G)=2$ it is polynomially time solvable [4]. There are also some classes for which this problem was settled to be -complete, as planar and chordal graphs [7, 8], or classes for which the stretch index was proved to be bounded by specific values, as split and cographs (cf. [9]). Hence, it is also a great challenge to determine the stretch index even restricted to graph classes. Still in the computational complexity approach, in this work, we can observe that Cai and Corneil’s characterization for tree 2-spanner admissible graphs [4], which deals with triconnected components of a graph, is not consistent with the usual definition of k-connected graphs, considering, for instance, complete graphs. In this sense, we present infinite families of split graphs that do not admit tree 2-spanners, but satisfy their sufficient condition, considering either, the convention for $K_n$ graphs connectivity (see [10, 11]) or that the connectivity concept does not apply to complete graphs (see [12]).

Studying bounds is an ordinary kind of approach for MSST. A natural lower bound arises when we consider the girth g(G) of a graph G, i.e. the length of its minimum cycle. We have that, if G is a tree t-spanner admissible, then $t\ge g(G) -1$. Regarding this bound, it is possible to observe some optimum tree t-spanners for some families or classes, for instance complete graphs, cycle graphs, wheel graphs, or complete k-partite graphs, for $k\ge 2$. However, establishing lower bounds is challenging in general, and so it remains when we deal with the MSST problem restricted to graph classes, since the results on it often present tree t-admissible graphs (cf. [4]). Another kind of approach considers variant problems, for instance the minimum diameter spanning tree. In this problem, the solution tree minimizes the maximum distances between all pairs of vertices, which is polynomially time solvable, and the solution parameter is an upper bound for the MSST problem [13].

We focus on obtaining the stretch index for some graph classes and, although there are already known upper bounds for some of them, in this work we present minimum $t = \sigma _T(G)$ values considering these classes. We also present the stretch index for 2 cycle-power graphs, which is far from the girth’s natural lower bound. Furthermore, we are also interested in the stretch index after vertices/edges operations, particularly for generalized octahedral graphs (complete graphs after removing a perfect matching), generalized octahedral graphs after non-universal vertices additions, and for prism graphs (2 cycle-power graphs after removing a perfect matching). Surprisingly, in this last case, the matching removal does not modify the stretch index of 2 cycle-power graphs.

This paper is organized as follows: In Sect. 2, we present basic definitions, considerations about Cai and Corneil’s characterization for tree 2-spanner admissible graphs, and previous results. In Sect. 3, we present optimum tree t-spanner for some graph classes, such as 2 cycle-power graphs, prism graphs, generalized octahedral graphs, threshold graphs and their minimal superclasses, split graphs and cographs; In Sect. 4, we present final remarks by considering further investigation on other classes and their properties.

2 Preliminaries

Given a graph $G=(V,E)$, $d_G(x,y)$ denotes the distance between x and y in G and $d_G(v)$, the degree of v in G. We say that a non-edge of a spanning tree T is an edge of $G\setminus T$. A p-path is a path of length p.

A tree t-spanner of a graph G is a spanning subtree T of G in which the distance between every pair of vertices is at most t times their distance in G. Cai and Corneil proved that this problem is equivalent to the one that considers only adjacent vertices of G [4]. Moreover, they showed what follows.

Theorem 1

A spanning tree T is a tree t-spanner of G if and only if for every edge $xy \in E(G)\backslash E(T)$ we have $d_T(x,y)\le t$.

The minimum stretch spanning tree of G (MSST) is an optimization problem of finding a tree t-spanner of G with minimum t. In this case, we say that $\sigma _T(G) = t$, and $\sigma _T(G)$ is called the stretch index of G. Upper bounds for $\sigma _T(G)$ can be obtained considering, for instance, the minimum diameter spanning tree, whose smallest parameter is $D_T(G)$, and some other problems [4, 14]. In opposite, a natural lower bound can be obtained accordingly to the girth of G, i.e., the length of its minimum induced cycle. Therefore, Theorem 2 states the range of the stretch index of a given graph G.

Theorem 2

[4, 13]. Given g(G) the girth of G, we have that $g(G) - 1 \le \sigma _T(G) \le D_T(G)$.

Consider, for instance, a tree $(n-1)$-spanner of the cycle graph $C_n$, i.e. a path $P_n$, and a tree 2-spanner of the complete graph $K_n$, i.e. a star $S_{n-1}$. Both spanning trees are optimum, and their associated stretch factors are tight with respect to Theorem 2.

On Cai and Corneil Tree 2-Spanner Characterization. Cai and Corneil [4] proposed a characterization to decide if $\sigma _T(G) =2$, formulated as follows: a nonseparable graph G has a 2-spanner if and only if G contains a spanning tree T such that for each triconnected component H of G, $T\cap H$ is a spanning star of H.

Indeed, the statement above gives a necessary condition for a graph having a 2-spanner. However, we show in Fig. 1 a nonseparable graph G and a spanning tree T of G such that the intersection of T with the unique triconnected component of G ($H=K_4$) is a spanning star of H, but there is no tree 2-spanner for the split graph in Fig. 1, as a consequence of Proposition 3. Observe that, since the connectivity of a complete graph with n vertices is $n-1$ [10, 11], a $K_4$ is triconnected and, once this is the unique triconnected component of G, $H = K_4$. Thus, in order that G is tree 2-spanner admissible it must exist a spanning tree T of G such that $T \cap H$ is a star. Figure 1(b) exhibits such a tree. This example can be generalized, for instance, to a graph obtained from a $K_{2k}$ adding k vertices adjacent to two vertices of $K_{2k}$ with no common adjacent vertex. k-sun (see [15]) are also an example of split graphs that satisfy the sufficient condition mentioned above, and thus would be tree 2-spanner admissible graphs, but, accordingly to Proposition 3, they do not admit a tree 2-spanner.

Thus, the Cai and Corneil’s sufficient condition for tree 2-spanner admissible graphs is not consistent with the usual definition of the connectivity for complete graphs. Even if we consider that the connectivity concept does not apply for such graphs, the condition does not hold in these families of examples.

Fig. 1.

(a) A split graph G with only one triconnected component $H = K_4$. (b) A spanning tree T of G such that $T\cap H$ is a spanning star of H, but G is not a tree 2-spanner admissible graph (see Proposition 3, since there is no vertex of the set $\{1,2,3,4\}$ adjacent to both vertices 5 and 6, then the stretch index of G is equal to 3).

3 Stretch Index for Graph Classes

Next we consider some related graph classes, for which we are able to obtain optimum tree t-spanners even when, in some cases, the lower bound of Theorem 2 is far from the stretch index we obtain. Moreover, seeing whether and how vertices/edges operations affect the stretch index is another goal of this section.

3.1 Cycle-Power Graphs

Any graph is a tree $(n-1)$-spanner admissible, but, in general, such a bound is far from the stretch index. However, for cycle graphs, $n-1$ is a tight value, since it reaches the lower bound of Theorem 2. Next, we present classes with extremal bounds, in such a way that $\sigma _T(G)$ is large and far from the lower bound given by Theorem 2.

A cycle-power graph [16], $C_{n}^{k}$, is obtained from a $C_n$ by adding edges between two vertices with distance at most k in $C_n$. We call external edges the edges of the external cycle $C_n$, and internal edges the added edges. Since $g(C_{n}^{k})=3$, then $\sigma _T(C_{n}^{k})\ge 2$. We restrict ourselves to $k=2$ and show an optimum tree $\lfloor \frac{n}{2}\rfloor$-spanner.

Given a graph $G = C_n^2$, we define an $\ell$-come-go path with respect to a pair of vertices $u_i, u_{i+j}$, for $j \in \{1, 2\}$, by a path of length $\ell$ from $u_i$ to $u_{i+j}$, for $\ell \in \{2, \cdots , n-1\}$, following one of two directions, either: clockwise/counterclockwise direction; or counterclockwise/clockwise direction. When we are not interested in the length, we suppress such a value and refer an $\ell$-come-go path by a come-go path.

A spot edge of a come-go path is an external edge that either: changes the way of the path, i.e. from clockwise to counterclockwise or from counterclockwise to clockwise; or immediately precedes an internal edge that changes the way of the path. Figure 2 illustrates the two 7-come-go paths with respect to $u_1$ and $u_2$.

Fig. 2.

Bold edges belong to 7-come-go paths with respect to $u_1$ and $u_2$, such that: (a) path using the counterclockwise/clockwise direction, where $u_7u_8$ is the spot edge; (b) path using the clockwise/counterclockwise direction, where $u_5u_6$ is the spot edge.

Lemma 1

Given a graph $G = C_n^2$ and a come-go path P with respect to $u_i u_{i+j}$, for $j\in \{1, 2\}$, then P contains a unique spot edge.

Proof

Once P is a come-go path, P must contain a spot edge. Suppose there are more than one of such edges. Following the path P from $u_i$ to $u_{i+j}$, consider $u_f u_{f+1}$ as the first reachable spot edge of P. After reaching the last spot edge of P, the unique way to achieve $u_{i+j}$ is by crossing again $u_f$ or $u_{f+1}$, once it is not possible to bypass two consecutive vertices of the external cycle. Since $u_f$ and $u_{f+1}$ already belong to P, then there is a cycle in the come-go path P.    $\square$

A path between $u_i, u_{i+j}$, for $j \in \{1, 2\}$, of length greater than 2 which is not a come-go is called a turn around path, which is depicted in Fig. 3(a). If $j=1$, then the length of a turn around path is at least $\lfloor \frac{n}{2} \rfloor$. If $j=2$, then the length is at least $\lfloor \frac{n}{2} \rfloor$ for n odd, and at least $\frac{n}{2} -1$ for n even. Note that, when $j=2$, we have between $u_i$ and $u_{i+j}$ either a turn around path or the 2-path $u_iu_{i+1}u_{i+2}$.

Fig. 3.

(a) Bold edges belong to a turn around path with respect to $u_1$ and $u_2$. (b) An example of vertices $u_x$ and $u_y$.

For any non-edge of a spanning tree T of a graph G, there is a path which is either: a come-go path, or a turn around path, or the 2-path $u_iu_{i+1}u_{i+2}$, for the non-edge $u_iu_{i+2}$.

Proposition 1

Given an $\ell$-come-go path with respect to $u_i$ and $u_{i+j}$, for $j\in \{1,2\}$, if $j=1$, then there is a unique external edge, otherwise there are exactly two external edge.

Proof

Considering $j=1$, since the spot edge is external, let us suppose that there is at least one more external edge $u_fu_{f+1}$, for $i +1< f < \ell$ in an $\ell$-come-go path P. In this case, following the path from $u_i$ to $u_{i+1}$, at least one of $u_f$ and $u_{f+1}$ will be reached, and after crossing the spot edge, it is necessary to reach $u_f$ or $u_{f+1}$ again, which implies that P is not a path. Similarly, considering $j=2$, the unique external edges are $u_iu_{i+1}$ and the spot edge.    $\square$

Lemma 2

Given a graph $G = C_n^2$ and an $\ell$-come-go path P, with respect to $u_i u_{i+j}$, for $j\in \{1,2\}$, then P is the unique $\ell$-come-go path with respect to $u_i u_{i+j}$ following the same direction of P.

Proof

Suppose there are at least two $\ell$-come-go paths $P_1$ and $P_2$ following, w.l.g., the counterclockwise/clockwise direction with respect to $u_i u_{i+j}$, for $j\in \{1,2\}$. In this case, there is a non-edge in $P_1$ which is external edge of $P_2$, and then it is a spot edge of $P_2$, by Proposition 1. Hence, the length of $P_2$ is distinct of $\ell$.    $\square$

Lemma 3

For any spanning tree T of $G=C_n^2$, there is at least a non-edge $u_i u_{i+j}$, for $j\in \{1, 2\}$, such that the unique path between $u_i$ and $u_{i+j}$ in T is a turn around path.

Proof

Suppose the path between any pair of vertices of a non-edge of T is not a turn around path. Hence, if the non-edge is external, then the path is a come-go path. If the non-edge is internal, then the path between them is either a 2-path, or it is a come-go path.

Since T must contain an external non-edge, let $u_iu_{i+1}$ be such an external non-edge of T and thus, by hypothesis, there is a come-go path $P_1$ between $u_i$ and $u_{i+1}$, in which $u_f\, u_{f+1}$ is the spot edge. The paths between all pairs of vertices in $P_1$ consisting of non-edges in T are induced paths of $P_1$, hence, let us analyze the neighbors of $u_f$ and $u_{f+1}$ outside $P_1$.

If there is a vertex of G outside of $P_1$, at least one of the vertices $u_{f}$ and $u_{f+1}$ has a neighbor outside $P_1$ consisting of a non-edge in T, because if there were all edges from $u_{f}$ and $u_{f+1}$ to their neighbors outside $P_1$, it would have in T the cycle $u_f \,u_{f+1}\, u_{y}, u_f$, for $u_y \in \{N(u_f) \backslash P_1, \ N(u_{f+1})\backslash P_1\}$. Let $u_xu_y$ be a non-edge of T, for $x\in \{f, f+1\}$, Fig. 3(b).

If $u_xu_y$ is an internal non-edge, then we have two options of a path between $u_x$ and $u_y$ in T:

• i. by the 2-path $u_x u_{x+1} u_y$. In this case, go to a non-edge where one of the vertices belongs to the 2-path. This non-edge belongs to: a 2-path, and in this case, we go to a non-edge and the analysis continues; a come-go path with respect to its extremities, and in this case, as it was done with $P_1$, go to its spot edge and continue the analysis; or $u_{x+1}u_y$ is the spot edge of a come-go path, $P_2$, following the opposite direction of $P_1$, with respect to vertices that do not belong to $P_1$, nor to the 2-path, either. Hence, go to the extremity vertices of $P_2$ and analyze a non-edge whose vertices are an extremity vertex of $P_2$ and a vertex that does not belong to $P_2$ nor to $P_1$;

• ii. by a come-go path with respect to $u_x u_y$, which we call $P_3$. Note that $P_3$ must have the same direction of $P_1$, otherwise, we would visit vertices already in $P_1$, implying in a cycle. Hence, go to the spot edge of $P_3$ and consider it similarly as done considering $P_1$.

If $u_xu_y$ is an external non-edge, then $u_x$ and $u_y$ must be connected by come-go path in T. In this case, proceed as in the previous case ii.

Note that the procedures considered in i and ii. must be finished when we reach either the vertex $u_{i-1}$ (whenever $P_1$ follows anticlockwise/clockwise direction), or the vertex $u_{i+j+1}$, for $j\in \{1, 2\}$ (whenever $P_1$ follows clockwise/anticlockwise direction). Let $u_w$ be the last visited vertex, which is neighbor of $u_i$ or $u_{i+j}$. In T, we have three possible paths between $u_w$ and $u_i$ or $u_{i+j}$: there is an edge; there is a come and go path; there is a 2-path. For any of such cases, we have created a cycle, because, by $P_1$, there is a path between $u_i$ and $u_{i+j}$, which does not include $u_w$. Therefore, there is path, distinct of $P_1$, starting from either $u_i$ or $u_{i+j}$ passing through $u_w$. Thus, there is a turn around path between $u_i$ and $u_{i+j}$.    $\square$

Lemma 4

For any cycle-power graph $C_{n}^{2}$, $\sigma _T(C_{n}^{2}) \ge \lfloor \frac{n}{2}\rfloor$.

Proof

Since there is at least a turn around path in any spanning tree T of $G=C_{n}^{2}$ (Lemma 3), and if n is odd, then there is a non-edge in T whose corresponding vertices’ distance is at least $\lfloor \frac{n}{2}\rfloor$. Therefore, $\sigma _T(C_{n}^{2}) \ge \lfloor \frac{n}{2}\rfloor$, for n odd.

Since when n is even, a turn around path has length at least: $\frac{n}{2}-1$, for an internal non-edge $u_i \ u_{i+2}$; or $\frac{n}{2}$, for an external non-edge. Hence, it remains to analyze the former case. Note that G contains two disjoint internal cycles $I_1$ and $I_2$, each one of length $\frac{n}{2}$. Consider that $u_i$ and $u_{i+2}$ belong to $I_1$ and the distance between them in T is $\frac{n}{2}-1$. Since the unique turn around path of length $\frac{n}{2}-1$ between $u_i$ and $u_{i+2}$ in G includes each edge of the cycle $I_1$, all internal edges of $I_1$ must belong to T, except $u_i\ u_{i+2}$. On the other hand, at least one of $u_i\ u_{i+1}$ and $u_{i+1}\ u_{i+2}$ must be non-edge of T. Otherwise, if both edges belong to T, then there would be the 2-path $u_i\,u_{i+1}\,u_{i+2}$ in T, contradicting the assumption of the path between $u_i\, u_{i+2}$ is turn around.

• 1. If $u_i\ u_{i+1}$ is non-edge of T and $u_{i+1}\ u_{i+2}$ is edge of T (which is similar to the case of $u_i\,u_{i+1}$ being edge of T and $u_{i+1}\ u_{i+2}$ non-edge of T), then the path between $u_{i}$ and $u_{i+1}$ has length at least $\frac{n}{2}$ considering the path between $u_i$ and $u_{i+2}$, and the edge $u_{i+2}\ u_{i+1}$. Otherwise, if there is a distinct path P between $u_{i}$ and $u_{i+1}$, we would have another path between $u_{i}$ and $u_{i+2}$, say $P \cup \{u_{i+1}u_{i+2}\}$.

• 2. If $u_i\ u_{i+1}$ and $u_{i+1}\ u_{i+2}$ are both non-edges of T, then at least one of the edges $u_{i-1}\ u_{i+1}$ and $u_{i+1}\ u_{i+3}$ must belong to T, otherwise $u_{i+1}$ would be isolated of T. Hence, we analyze the two cases:

  • $u_{i-1}\ u_{i+1}$ is an edge of T and $u_{i+1}\ u_{i+3}$ is a non-edge of T. In this case, note that the path between $u_{i+1}$ and $u_{i+2}$ must be a turn around, because $u_{i+1}\ u_{i+2}$ and $u_{i+1}\ u_{i+3}$ are non-edges of T, Fig. 4(a). Since $u_{i+1}\ u_{i+2}$ is an external non-edge of T, then, the distance between $u_{i+1}$ and $u_{i+2}$ is at least $\frac{n}{2}$.

  • $u_{i-1}\ u_{i+1}$ and $u_{i+1}\ u_{i+3}$ are edges of T. Let us consider the distance between $u_{i+1}$ and $u_{i+2}$ in T. If it is given by a turn around path, then its length is at least $\frac{n}{2}$. Otherwise, it is an come-go path $P^1$. If $P^1$ follows the clockwise/anticlockwise direction, then the edge $u_{i}\ u_{i+2}$ must exist in T, but it contradicts the hypothesis. Hence, $P^1$ follows the anticlockwise/clockwise direction. Similarly, the path between $u_i$ and $u_{i+1}$ is a turn around path, implying that the distance between $u_i$ and $u_{i+1}$ is at least $\frac{n}{2}$, or it is a come-go path $P^2$ following the clockwise/anticlockwise direction. In this case, we have that:

    • if there is any path in T between the spot edges of the two come-go paths without passing through $u_{i+1}$, then we have created a cycle, since $u_{i+1}$ belongs to the two come-go paths just settled;

    • Suppose there is no path in T between the spot edges of the two come-go paths without passing through $u_{i+1}$, and let P be the path composed by external edges in G that links the $P^1$ spot edge to the $P^2$ spot edge following the anticlockwise direction, Fig. 4(b). Note that P has at least one edge, because, otherwise, T would have a cycle. Clearly, there is an edge in P which is a non-edge in T. Thus, there is a path of length at least $\frac{n}{2}$.

Hence, we have that there is a pair of neighbors in G whose distance is at least $\lfloor \frac{n}{2}\rfloor$ in T.    $\square$

Fig. 4.

(a) Turn around path between $u_{i+1},u_{i+2}$ in T. Note that $u_i u_{i+2}$, $u_{i+1} u_{i+2}$ and $u_{i+1} u_{i+3}$ are non-edges of T. (b) Bold edges compose two come-go paths $P^1$ and $P^2$, where the bold external edges are their spot edges. The path P is inside the dotted diagram.

Lemma 5

For any cycle-power graph $C_{n}^{2}$, $\sigma _T(C_{n}^{2}) \le \lfloor \frac{n}{2}\rfloor$.

Proof

We obtain a spanning tree T of $C_{n}^{2}$ with vertex set $\{u_1,\ u_2,\ \ldots , u_{n}\}$ as follows: add to T the vertex $u_1$ and its neighbors $u_2,\ u_3,\ u_{n}$ and $u_{n-1}$. Now, follow the direction in which the next vertex is $u_2$, set $i=3$, and: (i) take the vertex $u_{i}$; (ii) Add to T the vertices adjacent to $u_{i}$ which are not in T yet, following the same direction as established initially, i.e., $u_4,\ u_5$ in the first step. Increment $i+1$ and return to step (i) until reaching the last vertices not in T yet. It is easy to see that, between two adjacent vertices of $C_{n}^{2}$, the distance between them in T is either $1, \ 2, \ 3$ or $\frac{n}{2}$. Hence, $\sigma _T(C_{n}^{2}) \le \lfloor \frac{n}{2}\rfloor$.     $\square$

Figure 5 depicts a tree $\lfloor \frac{n}{2}\rfloor$-spanner for $C_{10}^2$.

Fig. 5.

Bold edges form the tree $\lfloor \frac{n}{2}\rfloor$-spanner T for $C_{10}^2$. There are: three turn around paths in T, with respect to the internal non-edges $u_7u_9$ and $u_8u_{10}$, and the external non-edge $u_8u_9$; a 2-path between the internal non-edge $u_2u_{10}$; 3-come-go paths with respect to the internal non-edges $u_2u_4, u_4u_6, u_6u_8$ and $u_8u_{10}$; and 2-come-go paths with respect to the external non-edges $u_2u_3, u_4u_5, u_6u_7$ and $u_9u_{10}$.

Theorem 3 follows from Lemmas 4 and 5.

Theorem 3

For any cycle-power $C_{n}^{2}$ with $n>5$, $\sigma _T(C_{n}^{2}) = \lfloor \frac{n}{2}\rfloor$.

3.2 Stretch Index After Edges Removal

For several graph classes, we are able to determine the stretch index. But obtaining the stretch index after we consider operations on the vertex/edge sets regarding those classes is a challenge. In this section, we are particularly interested on a perfect matching removal considering 2 cycle-power and complete graphs, which are prism and generalized octahedral graphs, respectively. With this last result, in Sect. 3.3 we obtain the stretch index for cographs.

Removing a Perfect Matching of Cycle-Power Graphs. Considering 2 cycle-power graphs of even order after removing a perfect matching M with respect to external edges, one can note that a $C_{2p}^2 \backslash M$ is the prism graph with bases $C_p$. Lemma 6 presents a lower bound which is far from its girth’s lower bound. Moreover, in Lemma 7 we prove that the stretch index is not affected by a perfect matching removal, differently from what happens with the complete graph and the octahedral graph, as proved in Theorem 5.

As in 2 cycle-power graphs, in prism graphs, we also have come-go and turn around paths.

Lemma 6

Given $G = C_{2p}^2 \backslash M$, a cycle-power graph $C_{2p}^2$ after removing a perfect matching M with respect to the external edges, we have that $\sigma _T(G) \ge \frac{n}{2}$.

Proof

Considering any tree t-spanner of G, we analyze two cases: all external edges belong to T; and there is at least an external non-edge in T.

• 1. All external edges belong to T: In this case, between two consecutive external edges $u_i \ u_{i+1}$ and $u_{i+2} \ u_{i+3}$ it is not possible to exist both internal edges $u_i \ u_{i+2}$ and $u_{i+1} \ u_{i+3}$ in T, otherwise the $C_4$, $u_i, \ u_{i+1}, \ u_{i+3}, \ u_{i+2}, \ u_i$, would belong to T. Next, we analyze two possible subcases: $u_{i} \ u_{i+2}$ and $u_{i+1} \ u_{i+3}$ are both non-edges of T; only one of such edges belongs to T.

  • 1.1. $u_i \ u_{i+2}$ and $u_{i+1} \ u_{i+3}$ are both non-edges of T: Considering the edge $u_{i+4} \ u_{i+5}$, it must exist in T either $u_{i+2} \ u_{i+4}$, or $u_{i+3} \ u_{i+5}$, because otherwise, the edge $u_{i+2} \ u_{i+3}$ would be isolated in T.

    Consider, w.l.g., $u_{i+2} \ u_{i+4}$ is in T (and so, $u_{i+3} \ u_{i+5}$ is a non-edge). Although a turn around for an internal non-edge is at least $\frac{n}{2} -1$, the distance between $u_{i+1}$ and $u_{i+3}$ is at least $\frac{n}{2}+1$ by a turn around path with respect such an internal non-edge. Note that the length of the turn around path between $u_{i+1}$ and $u_{i+3}$ is equal to $\frac{n}{2} -1$ only when all edges of $I_1\backslash \{u_{i+1} u_{i+3}\}$ are in T, where $I_1$ is the internal cycle of G that contains vertices $u_{i+1}$, $u_{i+3}$ and $u_{i+5}$. However, $u_{i+3} \ u_{i+5}$ is a non-edge in T, which implies in a exchange of $u_{i+3} \ u_{i+5}$ by the path $u_{i+5},u_{i+4},u_{i+2},u_{i+3}$ in T. Hence, the length of the turn around path is at least $\frac{n}{2}+1$ after the edges’ exchange.

  • 1.2. Suppose, w.l.g., $u_i \ u_{i+2}$ is an edge of T and $u_{i+1} \ u_{i+3}$ is a non-edge of T. Now, we prove that in T it must exist a pair of non-edges $u_j \ u_{j+2}$ and $u_{j+1} \ u_{j+3}$ for some j, similarly to Case 1.1. Assume that one of such edges is in T and belongs to the internal cycle $I_2$ of G. Hence, we create a path starting by the edge $u_i \ u_{i+2}$, and after that we choose one of the two ways of reaching the external edge $u_{i+4} \ u_{i+5}$, by $u_{i+2}\ u_{i+4}$ or $u_{i+3}\ u_{i+5}$. If $u_{i+2} \ u_{i+4}$ is an edge of T, then we are making a path through $I_2$, otherwise, the path is $u_i, \ u_{i+2}, \ u_{i+3}, \ u_{i+5}$. Therefore, it is always possible to reach two consecutive external edges by using $I_1$ or $I_2$ edges. So, if there is not a pair of non-edges similar to Case 1.1, we can continue this path through external edges of $I_1$ and $I_2$, creating then a cycle. Once it is necessary to have non-edges of Case 1.1, then we have the existence of vertices with distance at least $\frac{n}{2}+1$ in T.

• 2. There is at least an external non-edge in T: Suppose $u_i \ u_{i+1}$ is a non-edge of T. If the path between $u_i$ and $u_{i+1}$ in T is a turn around, then its length is at least $\frac{n}{2}+1$, because $u_i$ belongs to $I_2$ and $u_{i+1}$ belongs to $I_1$. Hence, assume that the path in T between $u_i$ and $u_{i+1}$ is a come-go.

  Note that we have at least one non-edge of $I_1$ and of $I_2$ in T, and similarly to Lemma 3 and Case 1.2 above, there is a turn around path between the corresponding vertices of an internal non-edge of $I_1$ and $I_2$.

  So, each turn around has length at least $\frac{n}{2}-1$, and such a path with respect to an internal non-edge in T is unique in G. Moreover, in T, a turn around with respect to a non-edge of $I_2$ (or $I_1$) has length $\frac{n}{2}-1$ or any greater value with the same parity, because the path between such vertices does not go through all edges of the corresponding internal cycle, and then we must move to the other internal cycle and return, increasing the path in at least two edges.

  Hence, in order to keep in T the distances equal to $\frac{n}{2}-1$ between the vertices of non-edges $e^2$ of $I_2$ and $e^1$ of $I_1$, all other edges of both internal cycles of G must belong to T. Let $P^2$ be the path $I_2 \backslash e^2$ and $P^1$ be the path $I_1 \backslash e^1$.

  Now, $P^1$ must be linked to $P^2$. The unique way to do that is by using only one external edge, otherwise, there would be a cycle in T by at least two ways to go through $P^2$ to $P^1$, each one using a distinct external edge. Therefore, in T, there is only one external edge of G.

  Since there is a come-go path between $u_i,\ u_{i+1}$, as well between all other $\frac{n}{2}-2$ external non-edges, all come-go paths between corresponding vertices of external non-edges must be composed by the same spot edge, say, the external edge we have used to link $P^1$ and $P^2$.

  Furthermore, the unique way to exist only come-go paths between corresponding vertices of external non-edges in T is by considering $u_{k-1} u_{k+1}$ and $u_{k-2} u_k$ internal non-edges of T. Otherwise, if the non-edges of T were $u_j u_{j+2}$ and $u_{j+2s+1} \ u_{j+2s+3}$, there would be a turn around path with respect to the external edges $u_j \ u_{j+1}$ and $u_{j+2s+1}\ u_{j+2s+2}$.

  In this way, we have that the distances between the vertices of the non-edge $u_{k-1}$ and $u_k$, and between the vertices of the non-edge $u_{k+1}$ and $u_{k+2}$ are $\frac{n}{2}-x$ and $\frac{n}{2}+x$, respectively, according to the place we have chosen the spot edge. Therefore, when $x=0$, we have that $\sigma _T(G)\ge \frac{n}{2}$.    $\square$

Accordingly to the arguments of Lemma 6, we are able to build a tree $\frac{n}{2}$-spanner as follows.

Lemma 7

Given $G = C_{2p}^2 \backslash M$, a cycle-power graph $C_{2p}^2$ after removing a perfect matching with respect to the external edges M, we have that $\sigma _T(G) \le \frac{n}{2}$.

Proof

Consider $I_1$ and $I_2$ the internal cycles of G, in such a way that $I_1 = u_1, u_3, u_5, \ldots , u_{n-1}, u_1$, $I_2 = u_2, u_4, u_6, \ldots , u_n, u_2$ and $M =\{ \{u_2u_3\}, \{u_4u_5\}, \{u_6u_7\}, \ldots , \{u_nu_1\}\}$. We create the spanning tree T by the edge set $\{\{u_3u_5\}, \ \{u_5u_7\}, \ \ldots , \ \{u_{n-3}u_{n-1}\} \ \cup \{u_2u_4\}, \ \{u_4u_6\}, \ldots , \ \{u_{n-2}u_n\} \cup \{u_{\frac{n}{2}} u_{\frac{n}{2}+1}\}\}$. Note that the unique external edge of G in T is $\{u_{\frac{n}{2}} u_{\frac{n}{2}+1}\}$. The paths between the external non-edges of T have length at most $\frac{n}{2}$, which is equal to this value for the non-edges $u_1 \ u_2$ and $u_{n-1} \ u_n$. Furthermore, there are only two internal non-edges in T, which are $u_nu_2$ and $u_{n-1} u_1$, with distances equal to $\frac{n}{2}-1$, because all other edges of $I_2$ and $I_2$ belong to T.    $\square$

Theorem 4 follows from Lemmas 6 and 7.

Theorem 4

  Given $G = C_{2p}^2 \backslash M$, a cycle-power graph $C_{2p}^2$ after removing a perfect matching with respect to the external edges M, we have that $\sigma _T(G) = \frac{n}{2}$.

Generalized Octahedral Graphs. Generalized octahedral graphs figure in several well studied problems [17] because of their regularity and symmetry. A generalized octahedral graph, or simply octahedral graph $O_k$, is the $(2k-2)$-regular graph, which is exactly a complete graph $K_{2k}$ after removing a perfect matching. This class sounds interesting in here when we deal with cographs in Sect. 3.3, even considering $O_k$ after vertices addition, in Lemma 10.

Theorem 5

Given an octahedral graph $O_k$, then $\sigma _T(O_k) = 3$, for $k>2$.

Proof

Consider the vertex set $\{u_1, \ v_1, \ldots , \ u_k, \ v_k\}$ in such a way that $u_i$ and $v_i$ are not neighbors, but they are adjacent to all other vertices of $O_k$. A tree T can be built by first considering two stars, with centers in $u_1$ and $v_2$, such that $u_1$ is adjacent to all $u_i$’s and $v_2$ is adjacent to all $v_i$’s. Now, we add to T the edge $u_1v_2$. The distances in T of two vertices of $u_i$’s or of $v_i$’s are equal to 2, and from distinct side are equal to 3, hence $\sigma _T(O_k) \le 3$. In order to prove that $\sigma _T(O_k) = 3$, suppose we have an optimum tree spanner T for $O_k$ that can be partitioned into two rooted trees, $T_1$ and $T_2$, each one with more than two vertices, such that at least one of them is not a star. Suppose, w.l.g., that $T_1$ is not a star. Let $l \in T_1$ and c be two vertices of T such that $lc \notin E(O_k)$. If $c \in T_1$, then l and c are adjacent to each vertex of $T_2$. Since $T_1$ is linked to $T_2$, there is an edge with one extreme in $T_1$ and another in $T_2$. If l is such an extreme, then $d_T(c,v) \ge 3, \forall v \in T_2$. Otherwise, there is a vertex $v \in T_2$ such that $d_T(l,v) \ge 3$.    $\square$

3.3 Threshold Graphs and Their Superclasses

Next, we establish the stretch index for three classes whose graphs are tree 3-spanner admissible (cf. [4]).

Threshold Graphs. Threshold graphs [18] can be defined as the intersection of two very well studied classes: split graphs and cographs. Thus, threshold graphs are $\{2K_2, \ P_4, \ C_4\}$-free graphs. Moreover, G is a threshold graph if G can constructed from the empty graph by repeatedly adding either an isolated vertex or a universal vertex.

Since to obtain spanning trees we only consider connected graphs, the last vertex of a threshold graph construction must be universal. Hence, a tree can be built as a star whose center is such a universal vertex. Thus we can state the following proposition.

Proposition 2

If G is a threshold graph, then $\sigma _T(G)=~2$.

Split Graphs. As just mentioned, split graphs are a superclass of threshold graphs. Formally, a graph $G=(X,Y)$ is a split graph, also called a (1, 1)-graph, if and only if it can be partitioned into a clique X and a stable set Y. In terms of forbidden subgraphs, they are $\{2K_2, \ C_4, C_5\}$-free graphs.

Lemma 8

If G is a split graph, then $\sigma _T(G) \le 3$.

Proof

We obtain a spanning tree T for a split graph $G = (X,Y)$ as follows. Set any vertex x in X to be the center of a star which includes each other vertex of X. Next, for each vertex $y \in Y$, choose an edge incident to y, arbitrarily, and make y a pendant in T. It remains to show that the distance between two adjacent vertices v, w in G is at most 3 in T. (i) $v,w \in X$: since we have a star in T with respect to X, then $d(v,w)= 2$. (ii) $v \in X$, $w \in Y$: the worst case occurs when $d_G(w)\ge 2$ and v is a leaf of the star in T. In this case, $d(v,w) = 3$ by the path $vxx'w$, where $x'w$ belongs to T.    $\square$

Now, we characterize split graphs whose stretch indexes are 2 or 3.

Proposition 3

Let $G=(X,Y)$ be a split graph which is not a tree. Thus, $\sigma _T(G)\!=\!2$ iff either: (i) $d_G(y) = 1, \forall \ y \in Y$, or (ii) $\exists \ x \in \bigcap _{y \in Y} N_G(y),\ x~\in ~X$ such that $d_G(y) \ge 2$.

Proof

If G satisfies (i) or (ii), then G contains a tree 2-spanner which can be constructed following Lemma 8, and, particularly in case (ii), consider any vertex x satisfying conditions required in (ii) to be center of the star. Conversely, by contradiction, since $\sigma _T(G) = 2$, for each pair of vertices in X there is in T either an edge or a $P_3$ centered in a vertex v of G. If $v \in X$, then the minimum stretch spanning subtree with respect to X is a star. Otherwise, $v \in Y$ and each vertex of the clique would be a leaf of the star centered in v. Once there are two vertices in Y with degree at least 2 without an adjacent vertex in common, in the first case, for any center of the star we have chosen regarding the clique’s vertices, there is a vertex of the stable set such that all its neighbors are leaves of the star, which implies $\sigma _T(G) \ge 3$. In the second case, $\sigma _T(G) \ge 3$ anyway, because, by hypothesis, there exist at least two more vertices in Y with degree at least 2, and they will be adjacent only to the leaves of the star centered in v.    $\square$

Figure 1 exhibits a split graph G with $\sigma _T(G) = 3$. Another example of split graphs that have stretch index equal to 3 are the k-sun. Such graphs do not satisfy conditions of Proposition 3 either.

Cograph. A cograph is a $P_4$-free graph. A trivial graph is a cograph, and any other can be obtained by disjoint union or join operations of cographs. We can represent the union and join operations of a cograph by a tree decomposition, called cotree [19].

Theorem 6

If G is a cograph, then $\sigma _T(G) \le 3$.

Proof

Since G must be connected, its cotree root’s label is 1, implying that any vertex of G represented as a leaf node of a root’s subtree is adjacent to all vertices of the other root’s subtrees. We build a spanning tree T of G as follows. Let f be a leaf node of the leftmost root’s subtree, $F_1$. Since f is adjacent to all vertices of the other root’s subtrees, set T as a star with center f and make f adjacent to each vertex of all root’s subtrees on $F_1$’s right. Let lf be an edge of the star just obtained. Once the vertex l in G is adjacent to all vertices of $F_1$, hence we add to T each edge corresponding to a neighbor of l in $F_1$, except to the edge lf. Therefore, $\sigma _T(G) \le 3$.    $\square$

Lemma 9

Given a graph G, let k be the number of its cotree root’s subtrees. If G does not contain a universal vertex, then G contains an octahedral $O_k$ as an induced subgraph.

Proof

Since G does not contain a universal vertex, then each root’s son of its cotree has label 0. Hence, in each subtree there are at least two leaves corresponding to non-adjacent vertices in G, but these two vertices are adjacent to all vertices of the other cotree root’s subtrees. So, the union of each two non-adjacent vertices per subtree induces an $O_k$ in G.    $\square$

If a cograph G contains a universal vertex and there exist $k'$ subtrees of the root with more than one leaf each, then there is an octahedral $O_{k'}$ as an induced subgraph of G. Moreover, if there were a universal vertex u with respect to $O_{k'}$, then $\sigma _T(O_{k'}\cup \{u\})=2$. However, such a vertex does not exist in a cograph without a universal vertex, because, in this case, all root’s subtrees have label 0, and considering two $O_{k'}$ non-adjacent vertices, it does not exist a vertex of a same subtree adjacent to both vertices, otherwise their lowest common ancestor would be 1.

Lemma 10

Let H be a cograph obtained from $O_k$ by non-isolated vertices addition. If there is not a universal vertex in H with respect to $O_k$, then $\sigma _T(H) = 3$.

Proof

Since $O_k$ is an induced subgraph of H, by construction H is a triconnected component. If $\sigma _T(H) = 2$, then the tree 2-spanner of H would be a star. However, it is not possible since H does not have a universal vertex.    $\square$

Since a cograph without universal vertex does not contain a universal vertex with respect to some octahedral, then we have that, for cographs, containing a universal vertex is also a necessary condition so that $\sigma _T(G) = 2$.

Theorem 7

Let G be a cograph. $\sigma _T(G) = 2$ iff G has a universal vertex.

Proof

If G contains a universal vertex, then $\sigma _T(G) = 2$. Let us prove the converse by contrapositive. If there is no universal vertex in G, then by Lemma 9 we have that G contains an octahedral $O_k$ as induced subgraph, and by Lemma 10 we have that the unique case for decreasing $\sigma _T$ from 3 to 2 is when there is a universal vertex with respect to $O_k$, but in a cograph with no universal vertex, there is no universal vertex with respect to an $O_k$.    $\square$

4 Concluding Remarks and Further Work

In this work, we present an inconsistence on a well known sufficient condition for tree 2-spanner admissible graphs. Moreover, we establish optimum tree t-spanners for some graph classes by considering their characteristics, decompositions and by vertex/edges operations. Following the strategies proposed in this work, we intend to obtain optimum tree t-spanners for generalized split graphs, say $(k,\ell )$-graphs, and also for graphs obtained by vertex/edges operations.