Electronic Journal of Graph Theory and Applications

On the connectivity of k-distance graphs

Omid Khormali

Department of Mathematical Sciences, University of Montana, Missoula, MT 59812, USA

omid.khormali@umontana.edu

For any \(k \in \mathbb{N}\), the k-distance graph \(D^kG\) has the same vertex set of G, and two vertices of \(D^kG\) are adjacent if they are exactly distance k apart in the original graph G. In this paper, we consider the connectivity of \(D^kG\) and state the conditions for graph G and integer k such that the graph \(D^kG\) is connected.

Keywords: distance, radius, diameter, power graph Mathematics Subject Classification: 05C12, 05C15

DOI:10.5614/ejgta.2017.5.1.9

1. introduction

We only consider the simple graphs G=(V,E) which are finite and undirected throughout this paper. Let G be a graph and k be a positive integer. The k-power of G, denoted by \(G^k\), is the graph with the vertex set \(V(G^k)=V(G)\) and the edge set \(E(G^k)=\{xy|1\leq d(x,y)\leq k\}\) where d(x,y) is the distance between two vertices of \(x,y\in V(G)\) on the shortest path between them [1]. The k-subdivision of a graph G, denoted by \(G^{\frac{1}{k}}\), is constructed by replacing each edge xy of G with path of length k. The vertices of G in \(G^{\frac{1}{k}}\) are as the main vertices of G. The union of graphs \(G_1\) and \(G_2\) with disjoint point sets \(V_1\) and \(V_2\) and edge sets \(E_1\) and \(E_2\) is the graph \(G = G_1 \cup G_2\) with \(V = V_1 \cup V_2\) and \(E = E_1 \cup E_2\) [5]. We refer the reader to [2-4 and 6-8] for more details. Let G = (V, E) be a graph and \(k \in \mathbb{N}\). The k-distance graph \(D^kG\) is a graph with the vertex set of \(V(D^kG) = V(G)\) and the edge set \(E(D^kG) = \{xy|d(x,y) = k\}\). Note that the k-power graph \(G^k\) is the union graph \(\bigcup_{1\leq i\leq k}(D^iG)\) and also if diam(G) is the diameter of a graph which is \(\max_{x\in V(G)}\{\max_{y\in V(G)}d(x,y)\}\), complete graph on |V(G)| vertices is \(\bigcup_{i=1}^{diam(G)}D^iG\). Now the

Received: 16 April 2016, Revised: 7 February 2017, Accepted: 19 February 2017.

following question arises naturally.

Question. What happens to the connectivity of k-distance graph?

We consider the connectivity of \(D^kG\) for acyclic and cyclic graphs when k is even and odd integers, separately. The notation rad(G) is \(\min_{x \in V(G)} \{\max_{y \in V(G)} d(x,y)\}\) which is the radius of G, and we use (a,b) = d with the same meaning as GCD(a,b) = d for two integers a and b. First, we consider the connectivity of the k-distance graph of acyclic graphs.

2. The connectivity of \(D^kG\) for acyclic graphs

For connectivity of \(D^kG\) where G is an acyclic graph and k is an even integer, we have the following theorem.

Theorem 2.1. Let G be an acyclic graph and \(k \in \mathbb{N}\) be an even integer. Therefore, \(D^kG\) is disconnected.

Proof. Let k be an even integer. It is clear that \(k \leq rad(G)\), because if k > rad(G), \(D^kG\) is disconnected. Take an arbitrary vertex, \(v \in V(G)\). Consider the rooted tree with root v. Suppose the root v is in step zero, the vertices in distance 1 are in step 1, ..., and vertices in distance e(v) which is the \(\max_{u \in V(G)} d(v, u)\) are in step e(v). Now consider the vertices in even and odd steps. The vertices in even steps are not in even distance with the vertices in odd steps. Hence, the vertices in even steps cannot be connected to the vertices in odd steps in \(D^kG\). Then \(D^kG\) is disconnected.

Now, we consider the connectivity of the k-distance graph of acyclic graphs when k is an odd integer.

Definition 2.1. Let \(P = P_n\) be a path such that \(n \ge 3k - 3\) and R be a labeling of the vertices of path P with natural numbers \(\{1, 2, \ldots, n\}\) from one vertex of degree I to another. The label of vertex x is indicated with r(x). Suppose [i] where \(0 \le i \le k - 1\) are the congruence classes module k on n. \(P_h^j\) where \(0 \le h, j \le n\) and h is the number of vertices deleted from first of P and j is the number of vertices deleted from end of P.

The graph \(T_q(n,k)\) is \(P\cup S_q\) where \(q\in\{\{\overbrace{1,1,\ldots,1}\},\{\overbrace{1,1,\ldots,1,2}\},\ldots,\{\overbrace{\frac{k-1}{2}},\frac{k-1}{2}\}\}\) and \(S_q\in\{\{\text{the set of }k-1\text{ distinct edges }e=uv\text{ such that }u\in V(P_{k-1}^{k-1})\text{ and }r(u)\text{ is in different }[i]\},\{\text{the set of }k-1\text{ distinct edges }e=uv\text{ and a path }P_3=P_{uv}\text{ such that }u\in V(P_{k-1}^{k-1})\text{ and }r(u)\text{ is in different }[i]\},\ldots,\{\text{ the set of 2 distinct paths }P_{\frac{k-1}{2}}=P_{uv}\text{ such that }u\in V(P_{k-1}^{k-1})\text{ and }r(u)\text{ is in different }[i]\}\}.\) We have \(|V(T_q(n,k))|=n+k-1\). See the Figure 1.

Figure 1. The graph \(T_{\{1,1,1,1\}}(27,5)\).

Lemma 2.1. The graph \(D^kT_q(n,k)\) is connected.

Proof. Consider the path \(P_n\) in \(T_q(n,k)\). \(D^kP_n\) is disconnected and has k components such that the vertices which are in a component have labels from a congruence class modulo k, [i] where \(0 \le i \le k-1\). The vertices of \(T_q(n,k) \setminus P_n\) which are k-1 vertices connect two components of \(D^kP_n\) in \(D^kT_q(n,k)\) and any two vertices of \(T_q(n,k) \setminus P_n\) have at most one common connected component such that all components are connected. Therefore, \(D^kT_q(n,k)\) is connected. For example, see the Figure 1.

Lemma 2.2. \(T_q(3k-3,k)\) is the graph with minimum number of vertices such that their k-distance is connected.

Proof. Due to Lemma 2.1, \(D^kT_q(3k-3,k)\) is connected. Therefore, we prove that \(T_q(3k-3,k)\) is the graph with minimum number of vertices such that \(D^kT_q(3k-3,k)\) is connected. Suppose \(T_q(3k-3,k)\) is not the graph with minimum number of vertices such that \(D^kT_q(3k-3,k)\) is connected. Therefore suppose G be an acyclic graph which has one vertex less than \(T_q(3k-3,k)\) and \(D^kG\) is connected. Then, if this vertex belongs to \(V(S)\setminus V(P_{k-1}^{n-k+1})\), then one of components of \(D^kP_{3k-3}\) is not connected to other k-1 components and therefore \(D^kG\) is not connected. If that vertex belongs to \(V(P_{3k-3})\), then one of vertices of \(V(S)\setminus V(P_{k-1}^{n-k+1})\) connected to only one vertex of \(V(P_{3k-3})\) and therefore again G is disconnected. Hence, the desire result is concluded.

Theorem 2.2. Let G be an acyclic graph and \(k \leq rad(G)\). The graph \(D^kG\) is connected iff k is an odd integer and G contains the subgraph \(T_a(n,k)\) where \(n \geq 3k-3\).

Proof. Suppose G is an acyclic graph. If k is an odd integer and G has the subgraph \(T_q(n,k)\), then the subgraph \(D^kT_q(3k-3,k)\) of \(D^kG\) is connected. We define the set \(Q_i=\{v\in V(G\setminus A)\}\)

Tq(n, k))|∃x ∈ V (Tq(n, k)), d(x, v) = i} where i = 1, . . . , max ^x∈^V (Tq(n,k)) v∈V (G\Tq(n,k)) {d(x, v)}. According to the fact that n ≥ 3k − 3 in Tq(n, k), we can add the vertices of G \ Tq(n, k) which are in Q¹ to some vertices of Tq(n, k) which are in distance k. And we can add the elements of V (G \ Tq(n, k)) \ Q² to some elements of V (Tq(n, k)) ∪ Q¹ which are in distance k. And so on. Therefore, we can connect all vertices of G in D^kG and hence D^kG is connected. Now, suppose D^kG is connected. If k is an even integer then due to Theorem 2.1, D^kG is disconnected. Therefore, k must be an odd integer. Consider the longest path in G and name it Pn. Use the labeling R for its vertices. If we consider D^kPⁿ where n ≥ 3k −3, it has k components. For connecting these k components, we need to at least k−1 vertices to connect these components and each vertex must be connected at least two components. Each component contains the vertices of P n−k+1 k−1 that their labels belong to a congruence class module k. Then this structure with a path Pⁿ with new k − 1 edges gives a Tq(n, k). Hence G has the subgraph Tq(n, k).

3. The connectivity of D^kG of the cyclic graphs

Firstly, we consider the cyclic graphs and an even integer k.

Lemma 3.1. Let G be a cyclic graph and k be an even integer. If G has no odd cycle, then D^kG is disconnected.

Proof. Suppose G is a cyclic graph, k is an even integer and let G has not odd cycle. Suppose D^kG is connected. Take a vertex arbitrary and call it v. Consider the graph G as a rooted graph with root v. Suppose the root v is in step zero, the vertices in distance 1 are in step 1, . . . , and vertices in distance e(v) which is the maxu∈^V (G) d(v, u) are in e(v) step. The remaining edges of G are between odd and even steps since G has no odd cycle. Then the possible connected vertices of v in D^kG are among the vertices in even steps since k is the even integer. Also if we take any other vertex in the even step as a root, then the parity of steps of vertices do not change. Then the vertices in even steps can be connected together in D^kG and also the vertices in odd steps can be connected in D^kG. Therefore, D^kG is disconnected.

Now, consider the cyclic graph G with odd cycle and even integer k. We find the structure such that the k− distance graph of an odd cycle with diameter less than k is connected.

Definition 3.1. Let k be an even integer and i ∈ {2, 3, . . . , k − 1}. The graph Hi,k is C2i+1 S D where D is one of the sets of paths with at least 2 and at most i + 1 paths such that:

• 2i − 1 − |D| 6 m 6 2i + 3 − |D|, where m is the number of the vertices of paths which connected to the vertices of cycle in k−distance graph. Name the set of these vertices A.
• If |D| is odd and (2i + 1, |D|) 6= 1, the distances between consecutive paths must not all be equal.

The paths D connected to cycle C2i+1 from one of their endpoints. In general, the number of vertices on paths of D are as follows:

By moving clockwise (counterclockwise), each path, P, of D has [(k − i − 1)+ the number of vertices on cycle before P between P and its neighbor path on C2i+1 ] vertices such that second part of summation is the number of elements of A in each path.

The inequality for m comes from that the required vertices for connecting the components of D^kC2i+1 are different in the different positions of connected paths to cycle C2i+1 in Hi,k. Also, the general case for the number of vertices on paths are mentioned by moving clockwise or counterclockwise because there are some situations which we can connect the components of D^kC2i+1 as well as vertices on paths with the same number of paths with lower number of vertices. But the value of m is again satisfied in the mentioned inequality.

Figure 2. A graph H4,⁶ and its 6-distance graph.

The following graph is not connected.

Figure 3. The distances between consecutive paths are equal and k = 6.

Lemma 3.2. If C³ is the only odd cycle in cyclic graph G and 4 6 k is an even integer then D^kG is disconnected.

Proof. If k = 2, there is a graph G such that D²G is connected. See the Figure 4.

Figure 4. A cycle C³ and k = 2.

Let 4 ≤ k. For connecting the vertices of C³ in D^kG, at least two paths P^k must be added to its two vertices. If G consists of only cycle C³ and paths Pk, it is clear that D^kG disconnected because the internal vertices of paths P^k cannot be connected to vertices of C3. Therefore, those vertices can be connected if there are some edges (paths) between vertices of C³ and paths P^k or between vertices of distinct paths. In this case, G has the odd cycle larger than C3. Therefore the result can be concluded.

Lemma 3.3. Let k > 4 be an even integer. We have:

• 1. The graph with the minimum number of vertices, such that it contains an odd cycle C2n+1 where n > k, (2n + 1, k) = 1 and its k−distance graph is connected, is the cycle C2n+1.
• 2. The graph with the minimum number of vertices, such that it contains an odd cycle C = C2i+1

where \(i \in \{2, 3, ..., k-1\}\) and its k-distance graph, is: I. if i is odd:

• When k = i + 1, the graph \(H_{i,k}\) has the minimum number of vertices when m = 2i 1 |D|.
• When k = i + 3, the graph \(H_{i,k}\) has the minimum number of vertices when D has 3 paths and m = 2i 4.
• When \(k \leq i + 5\), the graph \(H_{i,k}\) has the minimum number of vertices when D has 2.

II. if i is even:

• When k = i + 2, the graph \(H_{i,k}\) has the minimum number of vertices when D has 3 paths and m = 2i 4.
• When \(k \leq i + 4\) the graph \(H_{i,k}\) has the minimum number of vertices when D has 2.

Proof. According to Definition 3.1 and the relation between k and diameter of cycle \(C_{2i+1}\), the graphs \(H_{i,k}\) are the subgraph of any graphs which their k-distance graphs are connected. Otherwise there exists a components of cycle \(C_{2i+1}\) that it is not connected to other components because of the structure of \(H_{i,k}\). Hence, due to k among \(H_{i,k}\)'s, the results can be concluded according to the graphs with minimum number of vertices.

Definition 3.2. Let k be an even integer and C be an odd cycle such that (length(C), k) = d and \(diam(c) \ge k\). The graph T'(n, k) where n = diam(C) is the graph \(C \cup B\) where B is one of the elements of set A (each element of A is a set of paths). The set A is \(\{\{P_2, P_2, \dots, P_2\}, \{P_2, \dots, P_2, P_3\}, \dots, \{P_{\lfloor \frac{d}{2} \rfloor + 1}, P_{\lceil \frac{d}{2} \rceil}\}\}\). By considering a labeling of vertices of C by integers, each component of \(D^kC\) has the vertices with labels from one of the congruence classes module d on length(C). So, the paths in B are connected to the vertices of cycle C in the different congruence class from one of their endpoints.

Lemma 3.4. The graph \(D^kT'(n,k)\) is connected.

Proof. By Definition 3.2 and considering C as odd cycle, if the paths of B are connected to the different vertices of distinct congruence classes, then k-1 vertices connect all components of \(D^kC\). Then \(D^kT'(n,k)\) is connected.

It is clear by Lemma 3.4 that \(D^kC_{2n+1}\) is connected if k is even integer, (2n+1,k)=1 and \(n \geq k\).

Theorem 3.1. Let G be a cyclic graph and \(k \ge 4\) be an even integer. Then \(D^kG\) is connected iff G contains a subgraph T'(n,k) where n = diam(C) (C is the cycle in T'(n,k)), \(n \ge k\) and (2n+1,k)=1, or G contains a subgraph \(H_{i,k}\) where \(i \in \{2,3,\ldots,k-1\}\).

Proof. Suppose G is a cyclic graph and \(k \ge 4\) is an even integer.

(\(\Leftarrow\))Suppose G has a subgraph T'(n,k) where n=diam(C) (C is the cycle in T'(n,k)), \(n\geqslant k\) and (2n+1,k)=1, or G has a subgraph \(H_{i,k}\) where \(i\in\{2,3,\ldots,k-1\}\). According to \(D^kT'(n,k)\) and \(D^k(C_{2n+1}\cup D)\) which are connected and due to the procedure which is mentioned in proof of Theorem 2.2, \(D^kG\) is connected in both cases.

(\(\Rightarrow\)) Suppose \(D^kG\) is connected. Then due to Lemma 3.2, G has an odd cycle \(C_s\) where s>3. Therefore, if \(k\leq diam(C_s)\), then the components of \(D^kC_s\) are connected. Hence G contains a subgraph of \(T'(\lfloor \frac{s}{2} \rfloor, k)\) because one of the structures of \(T'(\lfloor \frac{s}{2} \rfloor, k)\) must exist for connecting the components of \(D^kC_s\). So the first part of our desire result is concluded. If \(k>diam(C_s)\), \(D^kC_s\) is disconnected. Due to Lemma 3.3, some paths must be added to \(C_s\) for connecting its components in k-distance graph. So we must have one of the structures of \(H(\lfloor \frac{s}{2} \rfloor, k)\) because one of those structures is required for connecting the components. This subgraph gives us the graph \(H_{i,k}\). Therefore the desired results are concluded.

Now, we consider the connectivity of the k-distance graph of cyclic graphs when k is an odd integer. The following lemma comes from the previous cases.

We define a graph T''(n,k) the same as the graph T'(n,k) with an odd integer k and a cycle C such that (length(C),k)=d and \(diam(c)\geq k\). In the same way of Lemma 3.6, the graph \(D^kT''(n,k)\) is connected.

• Lemma 3.5. Let G be a cyclic graph. If k is an odd integer, \(k \leq rad(G)\) and G contains the subgraph \(T_q(n,k)\) where \(n \geq 3k-3\) is the length of a path in G, then the graph \(D^kG\) is connected.
  • Let G be a cyclic graph and k be an odd integer. Suppose \(C_n\) is a cycle of G such that \(k \leq \lfloor \frac{n}{2} \rfloor\). So, if G contains a subgraph \(T''(\lfloor \frac{n}{2} \rfloor, k)\), then the graph \(D^kG\) is connected.

Proof. For the first part, we consider the spanning tree T of G which contains \(T_q(n,k)\). By Theorem 2.2, \(D^kT\) is connected. So, clearly, \(D^kG\) is connected.

The second part can be concluded by the connectivity of \(D^kT''(n,k)\). Since \(diam(c) \ge k\) in T''(n,k), we can add the remaining vertices of G to \(D^kT''(n,k)\) in \(D^kG\) step by step and we can add all of the remaining vertices. Hence, \(D^kG\) is connected.

Note that if G has an even cycle \(C_{2n}\) which k < n and (k, 2n) = 1 then the graph \(D^kG\) is connected and if G has an odd cycle \(C_{2n+1}\) which \(k \le n\) and (k, 2n+1) = 1 then, the graph \(D^kG\) is connected since (length(C), k) = 1.

Now, we find the structure such that the k- distance graph of a cycle with diameter less than k is connected.

Definition 3.3. Let k be an odd integer and \(i \in \{2, 3, ..., k-1\}\). The graph \(H'_{i,k}\) is \(C_{2i} \bigcup D'\) where D' is one of the sets of paths with at least 2 and at most 2i paths such that:

\(-2i-1 \le m \le 2i\), where m is the number of the vertices of paths which connected to the vertices of cycle in k-distance graph. Name the set of these vertices A.

- The distances between consecutive paths must not all be equal.

The paths D' connected to cycle \(C_{2i}\) from one of their endpoint. In general, the number of vertices on paths of D' are as follows:

By moving clockwise (counterclockwise), each path, P, of D' has [(k-i-1)+ the number of vertices on cycle before P between P and its neighbor path on \(C_{2i}\) ] vertices such that the second part of summation is the number of elements of A in each path.

For example see the following figure.

Figure 5. A graph \(H'_{4,5}\) and its 5-distance graph.

Definition 3.4. Let k be an odd integer and \(i \in \{2, 3, ..., k-1\}\). The graph \(H''_{i,k}\) is \(C_{2i+1} \bigcup D''\) where D'' is one of the sets of paths with at least 2 and at most i+2 paths such that:

\(-2i-1-|D''| \le m \le 2i+3-|D''|\), where m is the number of the vertices of paths which connected to the vertices of cycle in k-distance graph. Name the set of these vertices A.

- if |D''| is odd and \((2i + 1, |D''|) \neq 1\), the distances between consecutive paths must not all be equal.

The paths D'' connected to cycle \(C_{2i+1}\) from one of their endpoint. In general, the number of vertices on paths of D'' are as follows:

By moving clockwise (counterclockwise), each path, P, of D'' has [(k-i-1)+ the number of vertices on cycle before P between P and its neighbor path on \(C_{2i+1}\) ] vertices such that the second part of summation is the number of elements of A in each path.

For example see the following figure.

Figure 6. A graph \(H_{4,5}''\) and its 5-distance graph.

Lemma 3.6. The graphs \(D^k H'_{i,k}\) and \(D^k H''_{i,k}\) are connected.

Proof. Due to their definitions, the paths which are connected to cycle C play the role of the connectors of the components of \(D^kC\) in \(D^kH'_{i,k}\) and \(D^kH''_{i,k}\). Also the structure of connected paths (their number and the number of vertices on the paths) are such that not only all components are connected but also the vertices on paths are connected in \(D^kH'_{i,k}\) and \(D^kH''_{i,k}\). Then clearly \(D^kH'_{i,k}\) and \(D^kH''_{i,k}\) are connected because \(H'_{i,k}\) and \(H''_{i,k}\) constructed from cycle C and the paths. \(\Box\)

Theorem 3.2. Let G be a cyclic graph and \(k \ge 5\) be an odd integer. Then \(D^kG\) is connected iff G contains one of following subgraphs:

• \(T_q(n,k)\) where \(n \geqslant 3k-3\) is the length of a path in G
• \(H'_{i,k}\) which i < k
• \(H_{i,k}''\) which i < k
• T''(diam(C), k) where n = length(C) and \(k \leq diam(C)\).

Proof. (\(\Leftarrow\)) Suppose G has one of the mentioned subgraphs. According to Lemmas 3.5, 3.6 and Definitions 3.3, 3.4, the graph \(D^kG\) will be connected.

(\(\Rightarrow\)) Suppose \(D^kG\) is connected. Suppose G has no \(T_q(n,k)\) where \(n\geqslant 3k-3\) is the length of a path in G. Since G is cyclic graph, suppose G has cycle C such that \(k\le diam(C)\). Since \(D^kG\) is connected, the components of \(D^kC\) are connected in \(D^kG\). We know to connect the components of \(D^kC\), some paths must be connected to C. And since these paths are connected to C in the different situations (their number and connecting positions to C) such that they use the least number of vertices on paths to connecting, one copy of T''(diam(C), k) must exist in G such that \(D^kC\) is connected.

Now suppose G has not the cycle with diameter greater than or equal to k. So suppose G has a cycle C such that \(k \geq diam(C)\). Since \(D^kG\) is connected, the components of \(D^kC\) are connected in \(D^kG\). We know for connecting the components of \(D^kC\), some paths must be connected to C. And since these paths are connected to C in the different situations, one copy of \(H'_{diam(C),k}\) or

H⁰⁰ diam(C),k (due to C which is an even or odd cycle) must exist in G such that D^kC is connected.

Acknowledgement

We want to thank the referee for his or her valuable comments and suggestions that helped us to improve the quality of the present work.

References

• [1] G. Agnarsson and M.M. Halldorsson, Coloring powers of planar graphs, SIAM J. Discrete Math. 16 (4) (2003), 654–662.
• [2] C.N. Campos and C.P. DeMello, A result on the total colouring of powers of cycles, Elect. Notes Discrete Math. 18 (2004), 47–52.
• [3] G. Fertin, E. Godard and A. Raspaud, Acyclic and k-distance coloring of the grid, Inform. Process. Lett. 87 (2003), 51–58.
• [4] H. Hajiabolhassan, On colorings of graph powers, Discrete Math. 309 (2009), 4299–4305.
• [5] M.N. Iradmusa, On colorings of graph fractional powers, Discrete Math. 310 (2010), 1551– 1556.
• [6] D. Kral, Coloring powers of chordal graphs, SIAM J. Discrete Math. 18 (2005), 451–461.
• [7] F. Kramer and H. Kramer, A survey on the distance-colouring of graphs, Discrete Math. 308 (2008), 422–426.
• [8] D.B. West, Introduction to Graph theory, Prentice Hall. Upper Saddle River, Second Edition, 2002.