1 Introduction↩︎

A graph’s diameter is an upper limit on the distance between vertices in a graph. Totally disjoint paths are non-interacting ways to traverse parts of a graph. This paper puts these two notions together, exploring problems involving totally disjoint diametral paths in graphs. Such paths model scenarios where one needs multiple long-haul routes across a network that share no infrastructure whatsoever, not even endpoints, so that each route is a fully independent worst-case traversal. This is natural in fault-tolerant routing and redundant backbone design, where the diameter captures the critical (longest) communication delay and total disjointedness guarantees that no single vertex failure can disrupt more than one such critical route.

A simple graph \(G=(V,E)\) is a set of vertices \(V\) and a set of edges \(E\), such that each edge \((u, v)\) in \(E\) connects a distinct pair of vertices (i.e., neighbors) \(u\) and \(v\) in \(V\). The degree of a vertex is the number of neighbors the vertex has. A path of length \(k\) in a simple graph G is a sequence of distinct vertices \((v_0, v_2, \ldots, v_k)\), where \((v_i, v_{i+1})\) is an edge in \(E\) for \(0 \leq i < k\); the path connects \(v_0\) and \(v_k\). A path of length \(k\) contains \(k\) edges and \(k+1\) vertices. A graph \(G\) is connected, if between every pair of vertices in \(V\) there exists a path connecting them. In this paper, every graph \(G\) is a simple, connected graph.

The distance between a pair of vertices in \(G\) is the length of a shortest path connecting the two vertices. The diameter of a graph \(G\) is the greatest distance between any pair of vertices in \(G\). Pairs of vertices having distance equal to the diameter are called diametral pairs; a shortest path between a diametral pair is called a diametral path. There can be more than one diametral pair in a graph and, between each such pair, there can be more than one diametral path.

In this paper, a pair of paths in a graph is totally disjoint if the two paths have no vertex in common, including their end vertices. A set of paths of a connected graph is a set of totally disjoint paths if every pair of paths in the set is totally disjoint. We denote by \(k\)-TDDP the problem of deciding if a given graph \(G\) has a set of totally disjoint diametral paths of size \(k\). The maximum size of a set of totally disjoint diametral paths in \(G\) is denoted by \(\#TDDP(G)\).

Interest in disjoint paths in graphs has a long history [1], [2], with applications to routing and commodity flows. This research primarily has focused primarily on edge-disjoint paths or vertex-disjoint paths that share the same end vertices. This line of research is mainly related to the well-known Menger’s Theorem and its variants [3]. Here, unlike those studies, we focus on sets of paths having no vertices in common, including their end vertices. Requiring distinct end vertices changes the problem fundamentally: rather than measuring the connectivity between a fixed pair (as in Menger-type results), we ask how many fully independent diametral routes a network can simultaneously support. This quantity can be viewed as a measure of a network’s redundant "long-distance capacity" at its critical scale. A much-studied \(k\) disjoint paths problem involves finding pairwise vertex disjoint paths between \(k\) specified pairs of vertices within a given graph or deciding that they do not exist (see [4] and [5] for a survey on the topic). There are versions of the \(k\) disjoint paths problem where the paths between the given pairs of vertices are required to be of shortest length (for instance in [6] and [7]) or not (for instance, [8]). These problems are at the heart of several recent studies ([9], [10]) due to their connections with both combinatorial optimization problems and the theory of graph minors [8]. A well-studied version is the shortest \(k\) disjoint paths problem where one looks for \(k\) vertex disjoint shortest paths between \(k\) given pairs of vertices such that their total distance is minimized. The decision version of this problem is NP-hard even under several restrictions; see [11] and the references therein for a recent summary of the extensive literature on the related results. As noted, these problems have applications in multi-commodity flows and VLSI design.

In this paper, we first address the complexity of \(k\)-TDDP in arbitrary graphs in Section 2. We prove that deciding if an arbitrary graph contains a set of at least \(k\) totally disjoint diametral paths is NP-complete. This places \(k\)-TDDP among the disjoint-path problems that remain intractable in general, motivating the search for tractable structured classes that follows. In Section 3, we consider several graph classes for which one can readily determine the maximum size of a set of totally disjoint diametral paths, including efficient algorithms for 2-paths (a subclass of maximal outerplanar graphs) and threshold graphs, and establish a bound for proper interval graphs. Finally, we consider the related extremal graph problem in Section 4. Given parameters \(d\) and \(k\), we describe classes of graphs with diameter \(d\) having \(k\) totally disjoint diametral paths with the minimum possible number of edges.

2 Complexity of \(k\)-TDDP↩︎

Let \(k\)-TDDP be the problem of deciding if a given graph \(G\) admits at least \(k\) totally disjoint diametral paths. This problem is related to the k disjoint shortest paths problem, denoted by \(k\)-DSP: Given a graph \(G\) and \(k\) pairs of distinct vertices \((s_0, t_0), (s_1, t_1), \ldots, (s_{k-1}, t_{k-1})\), determine if there exist \(k\) pairwise vertex disjoint shortest paths \(p_i\) between \(s_i\) and \(t_i\) for each \(i, 0 \leq i \leq k-1\) [7]. This problem is known to be \(NP\)-complete when \(k\) is part of the input, even for planar graphs [7]. We will use this result to show that \(k\)-TDDP is NP-complete.

Developing efficient algorithms for \(k\)-DSP for fixed \(k\) (in particular for \(k=2\)) is an active research area [9], [10]. In a recent result, considering shortest paths where \(k\) is fixed, Lochet [12] presents an algorithm with a running time \(n^{O(k^{5^k})}\) that decides whether there exist \(k\) disjoint shortest paths between \(k\) given pairs of vertices; this was subsequently improved to \(n^{O(k!\,k)}\) by Bentert et al.[13]. This result implies a polynomial time algorithm for \(k\)-TDDP when \(k\) is fixed by considering all sets of diametral pairs of size \(k\), of which there are only polynomially many. Our \(NP\)-hardness result for \(k\)-TDDP holds when \(k\) is part of the input, while for every fixed \(k\) the enumeration above yields a polynomial time algorithm. We note that Lochet [12] (see also Bentert et al. [13]) also showed that \(k\)-DSP is W[1]-hard parameterized by \(k\), so for \(k\)-DSP the dependence of the exponent on \(k\) presumably cannot be removed. Whether \(k\)-TDDP is likewise W[1]-hard parameterized by \(k\) is open.

A related problem is the vertex disjoint paths problem, where mutually vertex disjoint, not necessarily shortest, paths between \(k\) given pairs of distinct vertices must be found. This problem is known to be NP-complete [14], and remains NP-complete on split graphs Heggernes2015finding?. In [8], Robertson and Seymour state that if \(k\) is fixed, then given a graph \(G\) and \(k\) pairs of vertices of \(G\), one can decide if there are \(k\) mutually vertex disjoint paths in \(G\) joining the given pairs in time \(O(n^3)\) where \(n\) is the number of vertices in \(G\). In Heggernes2015finding?, Heggernes et al. show that this problem admits a kernel with \(O(k^2)\) vertices when restricted to split graphs.

We establish the NP-completeness of \(k\)-TDDP in general (connected) graphs using a reduction from \(k\)-DSP. The reduction transforms an instance \(G\) of \(k\)-DSP by adding new vertices attached to the vertex pairs \((s_i,t_i)\) for each \(i\) with paths whose lengths are carefully chosen with respect to the diameter of \(G\). Then we show that there are \(k\) disjoint shortest paths in \(G\) between the given pairs \((s_i,t_i)\) for each \(i\) if and only if there are \(k\) totally disjoint diametral paths in the newly constructed graph. We note that even though the input graph is planar, our transformation does not preserve planarity; thus we obtain the NP-completeness of \(k\)-TDDP for general graphs, but not for planar graphs using the result in [7].

3 Maximum Number of Totally Disjoint Diametral Paths in Certain Graph Classes↩︎

In this section, we investigate several classes of graphs for which we can determine or bound the maximum size of a set of totally disjoint diametral paths, \(\#TDDP(G)\). As a first example, we consider tree graphs. A \(tree\) \(T_n\) is a connected acyclic graph on \(n\) vertices having \(n-1\) edges.

3.1 Parameterized Graphs↩︎

Here we consider classes of graphs that have a fixed size and structure given values of one or more integer parameters. Cycle \(C_n\) can be described as a set of distinct vertices \(v_0, v_1, v_2, \ldots, v_{n-1}\) with edges \((v_i, v_{i+1})\) for \(0 \leq i < n-1\), plus edge \((v_{n-1}, v_0)\). We define \(EC_n\), for odd \(n\), to be \(C_n\) enhanced by two edges and a new vertex \(u\) with edges \((v_{\lfloor n/2 \rfloor}, u)\) and \((u, v_{\lceil n/2 \rceil +1})\). See Figure 2 for \(EC_7\). A \(CC_{2n}\), for \(n>1\), has \(2n\) vertices \(v_0, v_1, \ldots, v_{2n-1}\) with edges \((v_i, v_{i+1})\) for \(0 \leq i<2n-1\), edge \((v_{2n-1}, v_0)\), and chordal edges \((v_i, v_{i+n})\) for \(i<n\). All vertices look the same in a \(CC_{2n}\), as it is a symmetric graph. See Figure 2 for \(CC_{22}\). The Rectangular Grid Graph \(RGG_{mn}\) is the graph whose vertices correspond to the points in the plane with integer coordinates, where \(x\)-coordinates are in the range \(1, ..., n\), and \(y\)-coordinates are in the range \(1, ..., m\); we designate the vertices as \(v_{x,y}\). Two vertices are connected by an edge whenever the corresponding points are at distance \(1\) in the plane. Finally, the complete bipartite graph \(B_{m,n}\) consists of two sets of vertices of sizes \(m\) and \(n\), where every vertex of each set has an edge connecting it to every vertex in the other set, with no edges between vertices in the same set.

*$\#TDDP(B_{m,n}) = \lfloor (m+n)/3 \rfloor$, for $m<2n$.*

Once $m$ is large enough, three totally disjoint diametral paths can
be realized in a $CC_{2m}$ by taking consecutive diametral paths
around the cycle. As an example, see Figure [-@fig:fig:CC22] for
$m=11$ (22 vertices) where the diameter is $\lceil m/2 \rceil = 6$.
The number of vertices included in a diametral path is $7$; thus,
$\#TDDP(CC_{22}) = 3$. Given the number of vertices in a diametral
path, there can never be more than three disjoint paths.

Therefore, $\#TDDP(CC_{2m}) = 2$, for $2<m<6$ and $7$;
$\#TDDP(CC_{2m}) = 3$, for $m\geq6$, except $7$.

Therefore, in a $B_{m,n}$ where $m\geq n$,

$\#TDDP(B_{m,n}) = n$, when $m\geq 2n$

$\#TDDP(B_{m,n}) = \lfloor (m+n)/3 \rfloor$, when $m<2n$.

Observing that \(\#TDDP\) is at most the number of vertices divided by one plus the diameter, the following upper bound on \(\#TDDP\) applies to all graphs.

The hypercube of dimension \(n\), denoted by \(Q_n\), has its vertex set representing distinct binary strings of length \(n\). Each vertex shares an edge with \(n\) other vertices, which are those that differ in one bit value.

We have the following exact values of \(\#TDDP(Q_n)\) for small \(n\leq 6\) where the optimality follows from the upper bound in Corollary 1. We observe that this upper bound is tight for \(n\leq 6\) except \(n=4\). Finding an efficient way to determine \(\#TDDP(Q_n)\) for larger \(n\) or proving that the bound given above is tight for all \(n\) other than \(4\) are open problems.

• \(\#TDDP(Q_2)=1\), as \((00, 01, 11)\) uses 3 vertices.

• \(\#TDDP(Q_3)=2\), as (101, 001, 011, 010) and (000, 100, 110, 111) use all eight vertices in the two diametral paths.

• \(\#TDDP(Q_4) =2\) with (0000, 1000, 1100, 1110, 1111) and (0100, 0101, 0001, 1001, 1011) consists of two totally disjoint diametral paths. By an exhaustive search, we find that there are no sets of three totally disjoint diametral paths in \(Q_4\).

• \(\#TDDP(Q_5)=5\) with the following five totally disjoint diametral paths: (00000, 00001, 00011, 00111, 01111, 11111); (00010, 00110, 00100, 00101, 01101, 11101); (01000, 01001, 01011, 11011, 10011, 10111); (01010, 11010, 10010, 10000, 10100, 10101);(01110, 01100, 11100, 11000, 11001, 10001)

• \(\#TDDP(Q_6)=9\) with the following nine totally disjoint diametral paths:
  (000100, 000000, 000010, 010010, 110010, 111010, 111011);
  (010000, 010100, 110100, 110101, 110111, 111111, 101111);
  (010101, 010001, 000001, 000011, 001011, 101011, 101010);
  (011001, 011000, 011100, 011110, 010110, 000110, 100110);
  (011011, 011010, 001010, 001110, 101110, 101100, 100100);
  (100010, 100011, 110011, 010011, 010111, 011111, 011101);
  (110000, 100000, 101000, 001000, 001100, 001101, 001111);
  (110110, 111110, 111100, 111101, 101101, 101001, 001001);
  (111000, 111001, 110001, 100001, 100101, 100111, 000111)

3.2 2-path Graphs↩︎

We show that we can efficiently determine \(\#TDDP\) for a subclass of maximal outerplanar graphs, called 2-paths. A graph is outerplanar if it can be drawn on the plane so that no edges are crossing, and all its vertices lie on the exterior face. A maximal outerplanar graph (MOP) is an outerplanar graph such that adding a new edge would destroy outerplanarity. A maximal outerplanar graph can be seen as a fully triangulated cycle. A MOP \(M\) can be constructed by starting from a triangle graph where all edges are exterior edges (i.e., lie on the exterior face) and successively adding a new vertex connected by edges to the two end vertices of an exterior edge \(e\). The newly added edges become exterior edges and the edge \(e\) becomes an interior edge. In a MOP, each interior edge \(e\) separates the MOP into two MOP subgraphs, each one including \(e\) as an exterior edge.

The class of 2-paths is a subclass of MOPs having only two vertices of degree 2. A 2-path can be constructed as follows. Start from a MOP on \(4\) vertices, which is uniquely defined as a 4-cycle with a diagonal chord; let the two vertices of degree 2 be called \(v_l\) and \(v_r\), respectively. Without loss of generality, we will consider a 2-path to be constructed from left to right, always replacing the right degree 2 vertex \(v_r\) of the graph. Add a new vertex \(u\) connected to \(v_r\) and one of its neighbors \(w\). The new vertex \(u\) replaces \(v_r\) as the rightmost degree 2 vertex.

Let \(G\) be a 2-path and consider its left to right construction order. After a fifth vertex is added to \(G\), there remains one vertex of degree 3 that is adjacent to \(v_l\) that we denote by \(v’_l\). These two vertices will not be involved in later additions of vertices; \(v_l\) and \(v’_l\) are called the left vertices of the graph. Similarly, we define the right vertices \(v_r\) and \(v’_r\), where \(v’_r\) is the unique neighbor of \(v_r\) having degree \(3\) (see Figure 3).

A 2-path with diameter 2 is called a fan. The graph on the left in Figure 3 shows a fan with 6 vertices and having two totally disjoint diametral paths.

As we construct a 2-path that has diameter greater than \(2\), there comes a point when a new vertex \(v\) is connected to an edge \(e_b\) that has both end vertices at distance \(2\) from \(v_l\); the edge \(e_b\) becomes an interior edge as vertex \(v\), now \(v_r\) at distance \(3\) from \(v_l\), is added to the 2-path. We call edge \(e_b\) the barrier edge of \(G\) as it separates left and right parts of the graph. See the graph on the right in Figure 3, which depicts a 2-path \(G\) with diameter \(4\) where \(\#TDDP(G)=2\), and \(e_b\) is shown by a bold edge.

Therefore, we have the following corollary.

The graph on the left in Figure 4 shows that while \([v_l, v_r]\) is always a diametral pair, the two totally disjoint diametral paths (one in black, the other in white vertices) using exterior edges may be between the pairs \([v'_l, v_r]\) and \([v_l,v'_r]\). The graph on the right in Figure 4 shows a 2-path having diameter \(3\) with \(\#TDDP(G)=1\); in order for vertex \(v_r'\) to reach a left vertex, it an interior, “shortcut” edge must be used.

We can use the results of the two lemmas above to derive an efficient algorithm determining \(\#TDDP(G)\) for a 2-path \(G\).

We have described above an efficient algorithm to compute \(\#TDDP\) for the subclass of MOPs called 2-paths. The properties and complexity of determining totally disjoint diametral paths in MOPs and in the more general graph class of 2-trees (i.e., where a new vertex can be connected by two edges to the ends of any existing edge) remain open problems.

3.3 Threshold Graphs↩︎

Threshold graphs have structural properties that allow us to provide upper bounds on \(\#TDDP\) or to compute it exactly in special cases. A threshold graph is a subclass of split graphs that can be constructed by repeated applications of the following two operations: \((1)\) addition of a single isolated vertex; \((2)\) addition of a single dominating vertex, i.e., a single vertex that is connected to all other vertices of the (current) graph. Let \(D\) be the set of dominating vertices and \(I\) be the set of isolated (or independent) vertices; noting that the terms dominating and isolated refer to their property by the time they were added to the graph. Given a graph, it can be recognized whether it is a threshold graph or not in linear time. Moreover, if it is a threshold graph, we can determine in linear time the order in which vertices are added to construct it using the two operations described above [17].

We note that although the bound in Theorem 7 holds with equality for the graph in Figure 5, \(\#TDDP(G)\) can be arbitrarily less than the bound. Consider a connected threshold graph \(G\) constructed as \(k\) dominating vertices followed by \(k\) isolated vertices, ending with a single dominating vertex that connects the graph. While the upper bound indicated would be \(\lfloor (2k+1)/3 \rfloor\), we have \(\#TDDP(G) = 1\).

A connected threshold graph \(G\) has diameter \(2\) (Theorem 7), and every diametral path \((a,b,c)\) is a path on three vertices satisfying \(a<c<b\) with either Type I: \(\{a,c\}\in I\) and \(b\in D\); or Type II: \(\{a,b\}\in D\) and \(c\in I\). In both cases, the center \(b\) is a dominating vertex. Below, we describe a dynamic program that computes \(\#TDDP(G)\) for threshold graphs.

3.3.0.1 The dynamic program DP_threshold

We fix the construction order of \(G\) and label the vertices \(1,2,\dots,n\) accordingly, so that vertex \(t\) is the \(t\)-th vertex added; each vertex is of type \(D\) or \(I\) according to whether it was added as a dominating or an isolated vertex. We exploit the fact that for any vertex \(v\), all earlier vertices of a given type bear the same adjacency relation to \(v\), so the algorithm need only track how many unused vertices of each type precede the current one, not which.

We sweep the vertices in order \(1,\dots,n\), maintaining the state \((i,\,\delta,\,m)\), where, after processing the prefix \(\{1,\dots,t\}\):

• \(i\) = number of independent vertices in the prefix that are unused (not yet assigned to any chosen path);

• \(\delta\) = number of dominating vertices in the prefix that are unused;

• \(m\) = number of Type II paths whose endpoint \(a\in D\) and middle vertex \(c\in I\) have been chosen (with \(a<c\le t\)) but whose center \(b\in D\) (with \(b>c\)) is not yet placed — the pending Type II paths.

Let \(F_t(i,\delta,m)\) be the maximum number of completed diametral paths achievable over the prefix \(\{1,\dots,t\}\) ending in state \((i,\delta,m)\). The initial state is \(F_0(0,0,0)=0\), all others \(-\infty\). The transition from \(t\) to \(t+1\) depends on the type of vertex \(v=t+1\).

If \(v\in I\), one of:

• leave unused: \((i,\delta,m)\to(i{+}1,\delta,m)\), completed \(+0\);

• open a Type II (use \(v\) as a middle \(c\), pairing it with an unused earlier dominating vertex as the endpoint \(a\)): requires \(\delta\ge1\); \((i,\delta,m)\to(i,\delta{-}1,m{+}1)\), completed \(+0\);

If \(v\in D\), one of:

• leave unused: \((i,\delta,m)\to(i,\delta{+}1,m)\), completed \(+0\);

• use as a Type I center \(b\) (consuming two unused independent vertices, necessarily earlier than \(v\)): requires \(i\ge2\); \((i,\delta,m)\to(i{-}2,\delta,m)\), completed \(+1\);

• use as the center \(b\) completing a pending Type II: requires \(m\ge1\); \((i,\delta,m)\to(i,\delta,m{-}1)\), completed \(+1\);

Note that when a vertex \(v\) of type \(I\) is left unused, it remains in the unused pool \(i\) and may be consumed later by the center of a Type-I path. Similarly, when a vertex \(v\) of type \(D\) is left unused, it remains in the unused pool \(\delta\) and may be consumed later when an independent middle vertex opens a potential Type II path. The number of paths completed at each step are used to update \(F\).

At the end, any pending Type II paths cannot be completed and are discarded, yielding: \[\#TDDP(G) \;=\; \max_{i,\delta}\; F_n(i,\delta,0).\]

Below is how DP_threshold applies to the example in Figure 5.

3.4 Proper Interval Graphs↩︎

Proper interval graphs are a structured subclass on which diametral paths admit a clean description, yet computing \(\#TDDP\) appears to resist the disjoint-path techniques that succeed for the classes above. In this section, we describe the structure of diametral paths in proper interval graphs, give a tight upper bound on \(\#TDDP\), and explain the obstruction that leaves the exact computation open.

Interval graphs are the intersection graphs of overlapping intervals on the number line. It is well known that the maximal cliques of an interval graph can be linearly ordered so that every vertex is contained in a sequence of consecutive maximal cliques [18]. Proper interval graphs are the subclass admitting an interval representation in which no interval is totally contained within another; equivalently, the orderings of the intervals by left and by right endpoint coincide. Given a proper interval graph on \(n\) vertices, we number the vertices \(1\) to \(n\) in left to right order of their associated intervals, and use vertices and intervals interchangeably with their numbers. For a vertex \(v\), let \(\ell(v)\) and \(r(v)\) denote the smallest and largest indices of a maximal clique containing \(v\) in the linear ordering of maximal cliques; both are non-decreasing in the vertex number, and two vertices are adjacent if and only if their clique-index ranges overlap. We write \(D\) for the diameter of \(G\).

Figure 6 shows a proper interval graph with its interval representation and the linear ordering of its maximal cliques. The two paths \((1,4,8,11,13)\) and \((2,3,6,10,12)\) shown in bold are diametral and totally disjoint, so this graph has at least (and exactly) two totally disjoint diametral paths.

We first remark that a natural greedy algorithm does not compute \(\#TDDP\). The graph in Figure 7 has diameter \(3\). Starting from the left, a greedy algorithm that repeatedly extends a path by its highest-numbered available neighbor constructs \(p_1=(1,4,6,9)\); forced onto lower-numbered vertices to stay disjoint, the next path it builds is \(p_2=(2,3,5,7,8)\), which has length \(4\) and is therefore not diametral.

Next, we investigate the structure of the diametral paths and note that they are monotone in the vertex order.

The level structure of Lemma 3 might suggest assigning each vertex a single position and packing diametral paths through a layered network. This fails, because a vertex can occupy different positions on different diametral paths. In the graph of Figure 7 (diameter 3), the diametral path \((2,4,6,9)\) uses vertex 2 as its left endpoint, at position 0, while the diametral path \((1,2,5,8)\) uses the same vertex 2 as its second vertex, at position 1. No assignment of one fixed level per vertex is therefore consistent with all diametral paths.

This obstruction defeats the natural formulations. A maximum-flow model that splits each vertex and routes unit flow through layered copies miscounts, because a vertex’s level is not well defined. The difficulty is structurally distinct from the classical vertex-disjoint shortest path problem between fixed terminal pairs: here the endpoints range freely over all diametral pairs, and it is precisely this freedom that resists a layered packing.

Nonetheless, the level structure yields a tight upper bound. For \(0\le j\le D\), let \[\Lambda_j \;=\; \{\, v\in V : v \text{ is the j-th vertex of some diametral path}\,\}\] be the set of vertices that can occupy position \(j\).

The bound is constructive: a vertex \(v\) lies in \(\Lambda_j\) exactly when some diametral pair \((s,t)\) satisfies \(d(s,v)=j\) and \(d(v,t)=D-j\), which can be tested from the all-pairs distance matrix; hence \(\min_{0\le j\le D}|\Lambda_j|\) is computable in polynomial time.

This bound is the proper interval analogue of the centre bound for trees (Theorem 2) and the barrier-edge bound for \(2\)-paths (Corollary 2): in each case a position that every diametral path must traverse limits the number of disjoint such paths. The bound is not always attained, as the multi-position phenomenon of Figure 7 can force \(\#TDDP(G)\) strictly below \(\min_j|\Lambda_j|\). Whether \(\#TDDP\) can be computed in polynomial time on proper interval graphs remains open.

4 Extremal Graphs↩︎

In this section, we are interested in the construction of extremal graphs that answer the following question: for given \(k\) and \(d\), what is the minimum number of edges in a graph having \(k\) totally disjoint diametral paths of length \(d\)? This minimum number of edges is denoted by \(MinE(k,d)\). Graphs having \(k\) totally disjoint diametral paths of length \(d\) and having exactly \(MinE(k,d)\) edges are called extremal. We find \(MinE(k,d)\) for all \(k\geq 1\) and \(d\geq 1\), identifying extremal graphs for each parameter pair \(k\) and \(d\).

We first define a class of graphs, \(DDPG_{k,d}\), each having \(k\) totally disjoint diametral paths of length \(d\), for \(d \geq 4\). \(DDPG_{k,d}\) is defined to be \(k\) vertex disjoint paths of length \(d\), \(p_1, \ldots,p_k\), where each path \(p_i\) has vertices \(p_{i,0}, \ldots , p_{i,d}\), connected by edges in that order. Let \(h = \lfloor d/2\rfloor\) and \(h' =\lceil d/2 \rceil\). Each path \(p_i\), \(1 < i \leq k\), is connected to path \(p_1\) by two edges \((p_{1,h}, p_{i,(h-1)})\) and \((p_{1,h'}, p_{i,(h'+1)})\). Figure 8 and 9 show graphs \(DDPG_{3,4}\) and \(DDPG_{3,5}\), respectively.

There remain the problems for distances \(d<4\). For \(d=1\), a complete graph on \(2k\) vertices is necessary, as every vertex must be a neighbor of every other vertex if the graph is to have diameter \(1\). So, \(MinE(k,1) = 2k^2 - k\), for all \(k>0\).

For \(d=2\), consider a construction similar to \(DDPG_{k,d}\) given above, with \(k\) paths \(p_1, \ldots, p_k\) of length \(2\), connect the middle vertex of path \(p_1\), i.e., \(p_{1,1}\), to all three vertices in every other path \(p_i, 1 < i \leq k\). See Figure 10 for an example with \(k = 3\). Since it is similar in construction, we will call this class of graphs \(DDPG_{k,2}\). Each \(DDPG_{k,2}\) has diameter \(2\) and \(k\) totally disjoint diametral paths. The graph has \(5k - 3\) edges; \(3(k-1)\) edges to connect paths \(p_i\), \(1 < i \leq k\), to the path \(p_1\) and \(2k\) edges in the \(k\) disjoint diametral paths \(p_1, \ldots ,p_k\).

For \(k=3\), there are two interesting graph classes. First define class \(C_{k,3}\) to be \(k\) vertex disjoint paths of length \(3\), with the central two vertices of these paths connected into a complete graph \(K_{2k}\). Every vertex of degree \(1\) is at distance \(3\) from every other vertex of degree \(1\) and at most distance \(2\) from vertices of the \(K_2\); all other vertices are direct neighbors. These graphs are minimal, as removal of any edge disconnects the graph or results in a diametral pair at distance \(4\). A \(C_{k,3}\) has \(2k^2+k\) edges, i.e., \(2k^2 - k\) edges in the complete graph and \(2k\) edges connecting the \(2k\) degree \(1\) vertices to the vertices of the complete graph.

Next, consider the following graph class \(DDPG_{k,3}\), constructed similarly to the \(DDPG_{k,d}\) graphs for \(d>3\). Given \(k\) vertex disjoint paths \(p_1,\ldots , p_k\) of length \(3\), connect all vertices of paths \(p_i,\) for all \(2 \leq i \leq k\), to \(p_1\) by edges \((p_{1,1}, p_{i,0}), (p_{1,1}, p_{i,1}), (p_{1,2}, p_{i,2}), (p_{1,2}, p_{i,3})\), excluding edge \((p_{1,1}, p_{2,1})\). A \(DDPG_{k,3}\) has \(7k-5\) edges, i.e. \(3k\) edges in the \(k\) disjoint diametral paths and \(4(k-1)\) edges connecting other paths to path \(p_1\), less 1 by excluding edge \((p_{1,1}, p_{2,1})\). See Figure 11 showing \(DDPG_{3,3}\).

In all of the extremal graphs defined in this section, the vertex disjoint diametral paths partition the vertices of the graph into sets of size \(d+1\) for diameter \(d\).

5 Conclusion↩︎

In this paper, we introduce the study of totally disjoint diametral paths in connected graphs. First, we show that determining the maximum size of a set of totally disjoint diametral paths in an arbitrary graph is \(NP\)-complete. We explore the maximum sizes of sets of totally disjoint diametral paths in several classes of graphs, presenting efficient algorithms for 2-paths and threshold graphs, and structural bounds for proper interval graphs. Finally, we present classes of extremal graphs with \(k\) totally disjoint diametral paths of length \(d\) having the fewest possible number of edges.

The research reported here leaves several open problems. Determining \(\#TDDP(Q_n)\) for the hypercube of dimension \(n\geq 7\) is an open question. Finding other classes of graphs \(G\) for which \(\#TDDP(G)\) can be determined efficiently is also open for future work. In particular, determining whether \(\#TDDP\) can be computed in polynomial time for proper interval graphs, for (maximal) outerplanar graphs, or for graphs of bounded treewidth would be of interest. The work done here on 2-paths suggests an approach to solve the problem for outerplanar graphs.

References↩︎