# The Connected Detour Numbers of Special Classes of Connected Graphs

Authors: Ahmed M. Ali; Ali A. Ali
Journal: Journal of Mathematics
 (2019)

---

## Abstract

Simple finite connected graphsG=V,E of p≥2 vertices are considered in this paper. A connected detour set of G is defined as a subset S⊆V such that the induced subgraph GS is connected and every vertex of G lies on a u−v detour for some u,v∈S. The connected detour number cdnG of a graph G is the minimum order of the connected detour sets of G. In this paper, we determined cdnG for three special classes of graphs G, namely, unicyclic graphs, bicyclic graphs, and cog-graphs for Cp, Kp, and Km,n.


---

## Body

## 1. Introduction

For basic definitions of the concepts of graphs we refer to [1–4], and for detour distance and related terminologies in graphs, we refer to [5–7]. Let G=V,E be a connected simple graph of p vertices and q edges. We assume that p is finite and pG≥2. For u,v∈VG the length of a maximum u−v path is called detour distance Du,v. A u−v path of length Du,v is called u−v detour. For vertex v∈V the detour eccentricity eDv is defined by(1)eDv=maxDu,v:u∈V.Thedetour radius radDG and the detour diameter diamDG (or DG) of G are defined as(2)radDG=mineDv:v∈V,diamDG=maxeDv:v∈V.A vertexw∈VG is said to lie on a u−v detour Q if w is a vertex of VQ including u and v. A detour set (denoted d.s.) is a subset S of VG such that every vertex v of G lies on an x−y detour of some x,y∈S. The detour number dnG of G is defined by(3)dnG=minS:Sis a d.s. ofG.Adetour basis of G is a d.s. of G of order dnG.IfS is a detour set of G and the induced subgraph GS is connected, then S is called connected detour set (denoted c.d.s.) of G. The connected detour number of G denoted as cdnG is defined as(4)cdnG=minS:Sis a c.d.s. ofG.Aconnected detour basis of G is a c.d.s. of order cdnG (see [8, 9]).A simple connectedp,q graph G with p≥3 is called unicyclic graph iff p=q. The graph G is called bicyclic iff q=p+1.The concept of connected detour number was introduced and studied by Santhakumaran and Athisayanathan in [9]. They determined cdn for some special graphs such as Kp, Cp, Km,n, trees, and Hamilton graph. There are many research papers on connected detour number and edge detour graphs (see [10–14]). Moreover, the concept of connected detour number and other related concepts have interesting applications in the channel assignment problem in radio technologies. This motivated us to determine connected detour number for other classes of graphs. Therefore, in this paper we determine the connected detour numbers for unicyclic graphs and bicyclic graphs. Moreover, the class of graphs called cog-graphs Gc will be explained and determined the cndGc if G is a complete graph, tree, cycle graph, and complete bipartite graph.


## 2. The Connected Detour Number of Unicyclic Graphs

LetG be a connected graph of order p≥3 and C the unique cycle in G, and let C be of length l≥3. It is clear that C has no chords, and every vertex of G, which is not on C, is either a cut-vertex or an end-vertex. We shall determine the connected detour number of such graphs in terms of l and p. Let n be the number of vertices of C that are not cut-vertices. Denote TG=v∈VG:vis either a cut−vertex or an end−vertex and T¯G=VG−TG. Then, n=T¯GandTG=p−n.Ifl=p, then G=Cp so cdnG=2. If p>l, then G contains at least one cyclic cut-vertex. If n=0, that is every vertex of C is a cut-vertex, then by Theorem 1.4 [Ref. 2] cdnG=p. From now on, we assume p>l.Proposition 1.
LetG be a connected unicyclic graph of order p≥4, and with l−cycle, l=3. Then, cdnG=p−1 iff n=1or2.Proof.
Ifn=1, then G contains exactly one vertex which is not a cut-vertex. It is clear that there is a detour joining the other two vertices of the triangle and v lies on it. Thus, cdnG=p−1. If n=2, let u1 and u2 be cycle vertices which are not cut-vertices. Clearly, there is no path in G between two vertices of TG that contains u1 or u2 (see Figure 1). Thus, every c.d.b. B of G must contain either u1 or u2. Therefore, cdnG≥p−1. If u3 is the third vertex of the triangle and u1∈B, then u2 lies on the u1−u3 detour. Therefore, cdnG≤p−1. Hence, cdnG=p−1.
To prove the converse, letcdnG=p−1, and BG is a c.d.b. of G, then BG contains two vertices of the 3−cycle, one of them is a cut-vertex ∵p≥4. Thus, in view of Theorem 1.4 [9], the 3−cycle has one or two vertices in T¯G, that is, n=1 or 2. Hence, the proof is completed.Figure 1Theorem 1.
LetG be a connected unicyclic graph of order p≥5 and with l−cycle, l≥4. Then, cdnG=p−1 iff the induced subgraph GTG consists of exactly n components.Proof.
Letm be the number of components of GTG. Let m=n, then since for every c.d.b., BG and GBG are connected, every connected component of GTG contains at least one cycle cut-vertex, and GTG⊂GBG, then GBG contains at least n−1 vertices from T¯G. Therefore, BG=p−n+n−1=p−1.
Conversely, letcdnG=p−1, and BG is a c.d.b. of G. Since GBG is connected and GTG consists of m components and GTG⊂GBG, then GBG contains at least m−1 vertices from T¯G. Because BG is a connected detour set of minimum order, then BG contains exactly m−1 vertices from T¯G. Thus,(5)cdnG=BG=TG+m−1.
From the hypothesis(6)cdnG=p−1=T¯G+TG−1=TG+n−1.
Therefore,m=n.
Hence, the proof of the theorem is completed.Example 1.
For the unicyclic graphG in Figure 2, we have m=n=4, so cdnG=p−1.
Now, we have the following result for the connected detour number of the unicyclic graph with exactly one cycle cut-vertex.Figure 2Proposition 2.
LetG be a connected unicyclic graph of order p≥4 and with exactly one cycle cut-vertex, say v, then cdnG=p−l+2, where l is the length of the unique cycle C of G.Proof.
Letu be a vertex of C adjacent to v. Then, there is a u−v detour consisting of all the vertices of C.
Thus,TG∪u is a c.d.s. of order TG+1=p−l−1+1=p−l+2.
It is clear that there are nox−y detour containing vertices of T¯G for every pair x,y∈TG. Therefore, TG∪u is a connected detour basis of G, and hence cdnG=p−l+2.
For connected unicyclic graphs having more than one cycle cut-vertex, we need the following definition.Definition 1.
LetG be a connected unicyclic graph of order p≥4 and with at least two cycle cut-vertices, and let C be the unique cycle of length l≥4. Moreover, let m be the number of components of the induced subgraph GTG. These components divide the cycle vertices which are not cut-vertices into m nonempty subsets A1,A2,…,Am, in successive order around C, as illustrated in Figure 3.Figure 3
Unicyclic graph illustrating Def. 1.Example 2.
Consider the unicyclic graphG shown in Figure 3. The set of cycle vertices which are not cut-vertices is WG=w1,w2,…,wn. It is clear that n=11, m=4, and l=18. The set WG is partitioned into A1=w1,w2, A2=w3,w4,w5,w6,w7, A3=w8, and A4=w9,w10,w11.
The c.d.n. for unicyclic graphs having more than one cut-vertex is determined by the following theorem.Theorem 2.
LetG be a connected unicyclic graph of order p≥5 and with at least two cycle cut-vertices, and the induced subgraph GTG consists of m components. Then, cdnG=p−α if and only if(7)α=maxAi:i=1,2,…,m.Proof.
Letα be as defined in (7) for the graph G, and let S be a c.d.b. for G. By Theorem 1.4 of Ref [9], S contains the set TG. Since the induced subgraph GS is connected, then S must contain all the vertices of at least m−1 subsets from A1,A2,…,Am. Since S is of minimum order, then S does not contain the subset from A1,A2,…,Am that has maximum order, say Ar. It is clear that there are two vertices x,y∈TG∪∪i≠rAi which are adjacent on C; hence, there is an x−y detour containing all the vertices of C. Therefore, S=TG∪∪i≠rAi.
Thus,cdnG=S=TG+∑i=1mAi−Ar=p−Ar=p−α.
To prove the converse, letcdnG=p−β and let S′ be a c.d.b. of G. If β is not equal to maxAi:1≤i≤m, then either S′ is not of minimum order or the induced subgraph GS′ is disconnected, contradicting the definition of connected detour basis.
Thus,β=maxAi:1≤i≤m, and hence the proof of the theorem is completed.Remark 1.
Clearlyα=1, iff m=n. Thus, Theorem 1 follows from Theorem 2.


## 3. The Connected Detour Numbers of Connected Bicyclic Graphs

Ap,q graph is bicyclic if and only if q=p+1. Thus, if G is a connected bicyclic graph, then G contains either three cycles having some edges in common or contains exactly two cycles having no edges in common. The connected detour number for a block bicyclic graph is determined by the following result.Proposition 3.
LetG be a 2-connected bicyclic graph of order p≥5 as shown in Figure 4. Then,(i)cdnG=2, iffm=n≥1andk≥1.(ii)cdnG=3, ifm,n,k≥1and they are different.Figure 4
Bicyclic graph for the proof of Proposition 3.Proof.
(i) Ifm=n, then there are two x−w1 detours, namely,x,v1,v2,…,vn,y,wk,wk−1,…,w2,w1 and x,u1,u2,…,um,y,wk,wk−1,…,w2,w1. It is clear that each vertex of G lies on one of the two x−w1 detours. Thus, x,w1 is a c.d.b. of G, so cndG=2.Conversely, ifm≠n, say m>n and k≠m,n, then G does not contain adjacent vertices u,v such that u,v is a detour set. Hence, the proof of Part (i) is completed.(ii)
Ifm,n,andk are different, say m>n>k, then it is clear that w1,x,v1 is a connected detour set of G. So, cdnG≤3. In view of Part (i), cdnG≥3. Thus, cdnG=3. Hence, the proof of the proposition is completed.Remark 2.
IfG is a 2-connected bicyclic graph of order p≥4 with a cycle C and with exactly one chord, that is, an edge joining nonadjacent vertices of C, then cdnG=2.
This section is divided into two subsections according to the types of the bicyclic graphs.


### 3.1. The Connected Detour Numbers of Bicyclic Graphs of Three Cycles

Now assume thatG is a connected bicyclic graph of order p≥9 with one or more cut-vertices and with three cycles, that is, three x−y paths which are internally vertex disjoints denoted by Q1,Q2, and Q3 as shown in Figure 5. We assume without loss of generality that m≥n≥k≥1. Let T¯ be the set of all cycle vertices which are not cut-vertices in G, and let T=VG−T¯.Figure 5
Bicyclic graphG.We shall determine the connected detour number for three kinds of bicyclic graphs of three cycles.Case 1.
Assume that eachQi, 1≤i≤3, contains at least one cut-vertex other than x and y. Moreover, let T′ be the set of all cycle cut-vertices in G. Then, we have the following proposition which determines the c.d.b. of such kind of bicyclic graph G.Proposition 4.
LetG be a connected bicyclic graph of three cycles and with one or more cut-vertices on each Qi, i=1,2,3, other than x and y as explained above and shown in Figure 5. Then,(8)cdnG=T+S,where S is a subset of T¯ of minimum order such that the induced subgraph GT′∪S is connected.Proof.
SinceT′⊂T and G is connected, then the induced subgraph GT∪S is connected. Because each Qi, 1≤i≤3, contains a vertex of T, then T∪S contains x or y and each Qi contains two adjacent vertices from T∪S. Therefore, every vertex of the x−y paths lies on an u−v detour for some u,v∈T∪S. Thus, T∪S is a c.d.s. of G. Moreover, from the minimalist of S we deduce that T∪S is a c.d.b. of G. Therefore, cdnG=T+S. Hence, the proof is completed.
The following example illustrates Proposition 3.2.Example 3.
Consider the bicyclic graphG shown in Figure 6.
It is clear thatpG=32 and S=u1,u2,v1,v3,w1,w2:(9)T=VG−u1,u2,u5,u6,u7,v1,v3,v5,v6,w1,w2,w4,w5,y.
Thus,T=pG−14=32−14=18(10)∴cdnG=18+6=24.Figure 6
GraphG for Example 3.Case 2.
Assume thatG contains exactly one x−y path that does not contain cut-vertices, other than x and y. So we have three possibilities for such bicyclic graph G:(i)
LetQ1 and Q3 each contains at least one internal cut-vertex, and Q2 does not contain an internal cut-vertex. Then, G−v1,v2,…,vn=H1,3 is a unicyclic graph. By Theorem 2, cdnH1,3=pH1,3−α1,3, in which α1,3 is defined in Definition 1 for the graph H1,3. We can easily verify that if B1,3 is a c.d.b. of H1,3, then it is a c.d.b. of G because m≥n≥k. Therefore,(11)cdnG=pG−n−α1,3.(ii)
LetQ2 and Q3 each contains at least one internal cut-vertex and Q1 does not contain an internal cut-vertex. Then, G−u1,u2,…,um=H2,3 is a unicyclic graph. By Theorem 2, cdnH2,3=pH2,3−α2,3, where α2,3 is the number defined in Definition 1 for the unicyclic graph H2,3. Thus, as in (i),(12)cdnG=pG−m−α2,3.(iii)
LetQ1 and Q2 each contains at least one internal cut-vertex, and Q3 does not contain an internal cut-vertices. Then, G−w1,w2,…,wk=H1,2 is a unicyclic graph. By Theorem 2, cdnH1,2=pH1,2−α1,2, where the number α1,2 is explained in Definition 1. If k=n, then every c.d.b. of H1,2 is a c.d.b. of G. Therefore,(13a)cdnG=pG−k−α1,2.
Ifk<n, then any c.d.b. B1,2 of H1,2 is not c.d.s. of G because each vertex wii=1,2,…,k of Q3 does not lie on a u-v detour for every pair of vertices u,v∈B1,2. But it is clear that either x∈B1,2 or y∈B1,2. Thus, if x∈B1,2 then B1,2∪w1 is a c.d.b. of G; and if y∈B1,2 then B1,2∪wk is a c.d.b. of G. Therefore,(13b)cdnG=pH1,2−α1,2+1=pG−k+α1,2−1.
The following example illustrates formulas (11)–(13b).Example 4.
Consider the graphsGi, 1≤i≤4, as shown in Figure 7.
It is easy to verify that:(14)pG1=20,α1,3=6,n=5⟹cdnG1=20−6−5=9,pG2=24,α2,3=3,m=7⟹cdnG2=24−3−7=14,pG3=25,α1,2=6,k=5=n⟹cdnG3=25−6−5=14,pG4=23,α1,2=6,k=3<5=n⟹cdnG4=23−3−6+1=15.Figure 7
Graphs of Example 4.
(a)
(b)
(c)
(d)Case 3.
Assume that the connected bicyclic graphG consists of two x−y paths, and each path does not contain cut-vertices but only one x−y path contains internal cut-vertices.
IfQ1 contains at least two internal cut-vertices, and Q2 and Q3 have no cut-vertices, n=k, then Q1∪Q2 is a unicyclic graph, denoted H1,2′. It is clear that(15)cdnG=cdnH1,2′=pH1,2′−α1,2′,where α1,2′ is given for H1,2′ as defined in Definition 1. Thus,(16)cdnG=pG−n−α1,2′.
Similar results we have ifQi i=2,3 has at least two internal cut-vertices and the other x−y paths have no cut-vertices. Therefore,(17)cdnG=pG−m−α2,3′,fori=2andm=k,cdnG=pG−n−α1,3′,fori=3andm=n,where α2,3′ is for the unicyclic graph H2,3′ and α1,3′ is for H1,3′.Remark 3.
If the bicyclic graphG depicted in Figure 5 has exactly one cycle cut-vertex which is a vertex of the x−y path Qi 1≤i≤3 including x and y, and the other two x−y paths have equal lengths, then(18)cdnG=1+T.
From now on, we assume thatm>n>k≥1 (see Figure 5). If Q1 contains internal cut-vertices and Q2 and Q3 contain no cut-vertices, then we may assume that the distance from x to the first cut-vertex along the x−y path Q1 is not more than the distance from y to the last cut-vertex along Q1. Let H1,3″ be the unicyclic graph constructed from Q1∪Q3∪w1,z, where w1z is an end-edge incident to vertex w1of Q3. It is clear H1,3″ contains vertices x and w1 in addition to vertices from Q1, and so(19)cdnG=cdnH1,3″−1=pH1,3″−α1,3″−1=pG+1−α1,3″−1−n.
Therefore,(20a)cdnG=pG−n−α1,3″.
If the distance fromy to the last cut-vertex along Q1 is less than the distance from x to the first cut-vertex along Q1, then we have the unicyclic graph H1,3‴=Q1∪Q3∪wkz. Hence,(20b)cdnG=pG−n−α1,3‴,where α1,3‴ is the number defined for H1,3‴ (Definition 1).
We have results similar to (20a) and (20b) for the cases where Qi i=2,3 has internal cut-vertices, the other two x−y paths have no internal cut-vertices and m>n>k≥1. Namely, cdnG=pG−m−α2,3″ or cdnG=pG−m−α2,3‴ for i=2 or 3 and the unicyclic graphs H2,3″ or H2,3‴.Remark 4.
If the vertexx or the vertex y is the only cycle cut-vertex of the bicyclic graph G shown in Figure 5 and m>n>k≥1, then (21)cdnG=2+T.


### 3.2. The Connected Detour Numbers of Bicyclic Graphs of Two Cycles

LetG be a bicyclic graph containing exactly two cycles C1 and C2, either having one vertex in common or there is a path joining a vertex of C1 to a vertex of C2. Thus, G is considered to consist of two unicyclic graphs G1 and G2 having exactly one vertex v in common.LetGi′i=1,2 be a uncyclic graph obtained from Gi by adding to it an end-edge vwi. The connected detour number of G is determined by the following theorem.Theorem 3.
LetG be a connected bicyclic graph of order p≥5 and consist of two edge-disjoint unicyclic graphs G1 and G2 having one vertex v in common. Then, cdnG=p−α1−α2, in which αii=1,2 is the number defined in Definition 1 for the unicyclic graph Gi′.Proof.
LetB be a c.d.b. of G, then B contains v. Moreover, let Bi be the subset of B consisting of the vertices of Gii=1,2. It is clear that each vertex of Gi lies on u−v detour for some pair u,v∈Bi. Therefore, Bi is a c.d.s. of Gii=1,2, that is because the connectedness of the induced subgraph GB implies that GiBi is connected. Since B is of minimum order, then Bi∪wi is a c.d.b. of Gi′i=1,2. Conversely, it is clear that if Bi′i=1,2 is a c.d.b. of Gi′, then B1′∪B2′−v,w1,w2 is a c.d.b. of G. By Theorem 2, cdnGi′=Bi′=pi′−αi′i=1,2, in which pi is the order of Gi′. Therefore, cdnG=p1′+p2′−α1+α2+3. Since p1′+p2′=p+3, then cdnG=p−α1+α2.


## 3.1. The Connected Detour Numbers of Bicyclic Graphs of Three Cycles

Now assume thatG is a connected bicyclic graph of order p≥9 with one or more cut-vertices and with three cycles, that is, three x−y paths which are internally vertex disjoints denoted by Q1,Q2, and Q3 as shown in Figure 5. We assume without loss of generality that m≥n≥k≥1. Let T¯ be the set of all cycle vertices which are not cut-vertices in G, and let T=VG−T¯.Figure 5
Bicyclic graphG.We shall determine the connected detour number for three kinds of bicyclic graphs of three cycles.Case 1.
Assume that eachQi, 1≤i≤3, contains at least one cut-vertex other than x and y. Moreover, let T′ be the set of all cycle cut-vertices in G. Then, we have the following proposition which determines the c.d.b. of such kind of bicyclic graph G.Proposition 4.
LetG be a connected bicyclic graph of three cycles and with one or more cut-vertices on each Qi, i=1,2,3, other than x and y as explained above and shown in Figure 5. Then,(8)cdnG=T+S,where S is a subset of T¯ of minimum order such that the induced subgraph GT′∪S is connected.Proof.
SinceT′⊂T and G is connected, then the induced subgraph GT∪S is connected. Because each Qi, 1≤i≤3, contains a vertex of T, then T∪S contains x or y and each Qi contains two adjacent vertices from T∪S. Therefore, every vertex of the x−y paths lies on an u−v detour for some u,v∈T∪S. Thus, T∪S is a c.d.s. of G. Moreover, from the minimalist of S we deduce that T∪S is a c.d.b. of G. Therefore, cdnG=T+S. Hence, the proof is completed.
The following example illustrates Proposition 3.2.Example 3.
Consider the bicyclic graphG shown in Figure 6.
It is clear thatpG=32 and S=u1,u2,v1,v3,w1,w2:(9)T=VG−u1,u2,u5,u6,u7,v1,v3,v5,v6,w1,w2,w4,w5,y.
Thus,T=pG−14=32−14=18(10)∴cdnG=18+6=24.Figure 6
GraphG for Example 3.Case 2.
Assume thatG contains exactly one x−y path that does not contain cut-vertices, other than x and y. So we have three possibilities for such bicyclic graph G:(i)
LetQ1 and Q3 each contains at least one internal cut-vertex, and Q2 does not contain an internal cut-vertex. Then, G−v1,v2,…,vn=H1,3 is a unicyclic graph. By Theorem 2, cdnH1,3=pH1,3−α1,3, in which α1,3 is defined in Definition 1 for the graph H1,3. We can easily verify that if B1,3 is a c.d.b. of H1,3, then it is a c.d.b. of G because m≥n≥k. Therefore,(11)cdnG=pG−n−α1,3.(ii)
LetQ2 and Q3 each contains at least one internal cut-vertex and Q1 does not contain an internal cut-vertex. Then, G−u1,u2,…,um=H2,3 is a unicyclic graph. By Theorem 2, cdnH2,3=pH2,3−α2,3, where α2,3 is the number defined in Definition 1 for the unicyclic graph H2,3. Thus, as in (i),(12)cdnG=pG−m−α2,3.(iii)
LetQ1 and Q2 each contains at least one internal cut-vertex, and Q3 does not contain an internal cut-vertices. Then, G−w1,w2,…,wk=H1,2 is a unicyclic graph. By Theorem 2, cdnH1,2=pH1,2−α1,2, where the number α1,2 is explained in Definition 1. If k=n, then every c.d.b. of H1,2 is a c.d.b. of G. Therefore,(13a)cdnG=pG−k−α1,2.
Ifk<n, then any c.d.b. B1,2 of H1,2 is not c.d.s. of G because each vertex wii=1,2,…,k of Q3 does not lie on a u-v detour for every pair of vertices u,v∈B1,2. But it is clear that either x∈B1,2 or y∈B1,2. Thus, if x∈B1,2 then B1,2∪w1 is a c.d.b. of G; and if y∈B1,2 then B1,2∪wk is a c.d.b. of G. Therefore,(13b)cdnG=pH1,2−α1,2+1=pG−k+α1,2−1.
The following example illustrates formulas (11)–(13b).Example 4.
Consider the graphsGi, 1≤i≤4, as shown in Figure 7.
It is easy to verify that:(14)pG1=20,α1,3=6,n=5⟹cdnG1=20−6−5=9,pG2=24,α2,3=3,m=7⟹cdnG2=24−3−7=14,pG3=25,α1,2=6,k=5=n⟹cdnG3=25−6−5=14,pG4=23,α1,2=6,k=3<5=n⟹cdnG4=23−3−6+1=15.Figure 7
Graphs of Example 4.
(a)
(b)
(c)
(d)Case 3.
Assume that the connected bicyclic graphG consists of two x−y paths, and each path does not contain cut-vertices but only one x−y path contains internal cut-vertices.
IfQ1 contains at least two internal cut-vertices, and Q2 and Q3 have no cut-vertices, n=k, then Q1∪Q2 is a unicyclic graph, denoted H1,2′. It is clear that(15)cdnG=cdnH1,2′=pH1,2′−α1,2′,where α1,2′ is given for H1,2′ as defined in Definition 1. Thus,(16)cdnG=pG−n−α1,2′.
Similar results we have ifQi i=2,3 has at least two internal cut-vertices and the other x−y paths have no cut-vertices. Therefore,(17)cdnG=pG−m−α2,3′,fori=2andm=k,cdnG=pG−n−α1,3′,fori=3andm=n,where α2,3′ is for the unicyclic graph H2,3′ and α1,3′ is for H1,3′.Remark 3.
If the bicyclic graphG depicted in Figure 5 has exactly one cycle cut-vertex which is a vertex of the x−y path Qi 1≤i≤3 including x and y, and the other two x−y paths have equal lengths, then(18)cdnG=1+T.
From now on, we assume thatm>n>k≥1 (see Figure 5). If Q1 contains internal cut-vertices and Q2 and Q3 contain no cut-vertices, then we may assume that the distance from x to the first cut-vertex along the x−y path Q1 is not more than the distance from y to the last cut-vertex along Q1. Let H1,3″ be the unicyclic graph constructed from Q1∪Q3∪w1,z, where w1z is an end-edge incident to vertex w1of Q3. It is clear H1,3″ contains vertices x and w1 in addition to vertices from Q1, and so(19)cdnG=cdnH1,3″−1=pH1,3″−α1,3″−1=pG+1−α1,3″−1−n.
Therefore,(20a)cdnG=pG−n−α1,3″.
If the distance fromy to the last cut-vertex along Q1 is less than the distance from x to the first cut-vertex along Q1, then we have the unicyclic graph H1,3‴=Q1∪Q3∪wkz. Hence,(20b)cdnG=pG−n−α1,3‴,where α1,3‴ is the number defined for H1,3‴ (Definition 1).
We have results similar to (20a) and (20b) for the cases where Qi i=2,3 has internal cut-vertices, the other two x−y paths have no internal cut-vertices and m>n>k≥1. Namely, cdnG=pG−m−α2,3″ or cdnG=pG−m−α2,3‴ for i=2 or 3 and the unicyclic graphs H2,3″ or H2,3‴.Remark 4.
If the vertexx or the vertex y is the only cycle cut-vertex of the bicyclic graph G shown in Figure 5 and m>n>k≥1, then (21)cdnG=2+T.


## 3.2. The Connected Detour Numbers of Bicyclic Graphs of Two Cycles

LetG be a bicyclic graph containing exactly two cycles C1 and C2, either having one vertex in common or there is a path joining a vertex of C1 to a vertex of C2. Thus, G is considered to consist of two unicyclic graphs G1 and G2 having exactly one vertex v in common.LetGi′i=1,2 be a uncyclic graph obtained from Gi by adding to it an end-edge vwi. The connected detour number of G is determined by the following theorem.Theorem 3.
LetG be a connected bicyclic graph of order p≥5 and consist of two edge-disjoint unicyclic graphs G1 and G2 having one vertex v in common. Then, cdnG=p−α1−α2, in which αii=1,2 is the number defined in Definition 1 for the unicyclic graph Gi′.Proof.
LetB be a c.d.b. of G, then B contains v. Moreover, let Bi be the subset of B consisting of the vertices of Gii=1,2. It is clear that each vertex of Gi lies on u−v detour for some pair u,v∈Bi. Therefore, Bi is a c.d.s. of Gii=1,2, that is because the connectedness of the induced subgraph GB implies that GiBi is connected. Since B is of minimum order, then Bi∪wi is a c.d.b. of Gi′i=1,2. Conversely, it is clear that if Bi′i=1,2 is a c.d.b. of Gi′, then B1′∪B2′−v,w1,w2 is a c.d.b. of G. By Theorem 2, cdnGi′=Bi′=pi′−αi′i=1,2, in which pi is the order of Gi′. Therefore, cdnG=p1′+p2′−α1+α2+3. Since p1′+p2′=p+3, then cdnG=p−α1+α2.


## 4. The Connected Detour Numbers of Cog-Graphs

LetG be a connected p,q-graph, then Gc is the graph constructed from the graph G with q additional vertices u1,u2,…,uq corresponding to the edges e1,e2,…,eq of G and 2q additional edges obtained from joining ui to the two vertices of ei for all i=1,2,…,q. Such class of graphs are called cog-graphs of G. For example, let G be a star of order five, then Gc is cog-star of order nine shown in Figure 8.Figure 8
(a)
(b)Clearly ifG is p,q–graph then Gc is p+q,3q-graph. The proofs of the following elementary results are obvious.Proposition 5.
(1) The cog-graph
G
c
does not contain end-vertices.
(2)
If the graph
G has nend-vertices, thenGccontains exactlyq+nvertices of degree 2.
(3)
For every vertex
v
∈
V
G, degGcv=2degGv.
(4)
Letv∈VG, then v is a cut-vertex in Gc iff it is a cut-vertex in G.
LetVG=v1,v2,…,vp and VGc=VG∪u1,u2,…,uq. If x1,x2,…,xk−1,xk is an x1−xk detour in G, then x1,y1,x2,y2,…,xk−1,yk−1,xk is an x1−xk detour in Gc, in which yi∈U=u1,u2,…,uq for 1≤i≤k−1 and yi is the vertex that corresponds to edge xixi+1 of G. Therefore, DGcx,y=2DGx,y, ∀x,y∈VG.
Moreover, ifQ is an y−y′ detour in Gcy,y′∈U, (as shown in Figure 9), then(22)DGcy,y′=DGcy′,x=DGcy,x′=2DGx,x′.
Any way, ifS is a detour set of G, then S may not be a detour set of Gc. Also for some graphs G, cdnG≠cdnGc. For example, if G is an odd cycle graph Cp with exactly one chord, then cdnG=2 and cdnGc=3. But there are special graphs G such that cdnG=cdnGc, as given in the following proposition.Figure 9
x
,
x
′
∈
V
G.Proposition 6.
LetG be a connected graph. If G is a tree or a cycle graph, then(23)cdnG=cdnGc=2,if G is a cycle graph,pG,G is a tree.Proof.
It is obvious.
The following concepts were introduced by Santhakumaran and Athisayanathan in [12].Definition 2.
[12, 15] “Any edge e of G is said to lie on an x−y detour Q, if e is an edge of Q. A set S⊆VG is called an edge detour set of G if every edge of G lies on a detour joining a pair of vertices of S. The edge detour number dn1G of G is the minimum order of its edge detour set. Any edge detour set of order dn1G is called an edge detour basis of G. A graph which has an edge detour set is called a edge detour graph (denoted E.D. graph).”
There are graphs which are not E.D. graphs because they do not have edge detour sets [12]. For E.D. graphs we give the following definition.Definition 3.
LetS be an edge detour set (will be denoted e.d.s.) of an E.D. graph G. If GS is connected then S is called a connected edge detour set (denoted c.e.d.s.). The connected detour number cdn1G of G is defined by(24)cdn1G=minS:Sis c.e.d.s. ofG.
Any c.e.d.s. of ordercdn1G is called connected edge detour basis (denoted c.e.d.b.) of G.
It can easily be proved that ifG is an E.D. graph, then every c.e.d.s. of G contains all the end-vertices and all the cut-vertices of G. Thus, for every tree T, cdn1T=pT.
Now, we shall determine c.e.d.n. for some special classes of connected graphs.Proposition 7.
For every cycle graphCp with p≥3, cdn1Cp=3.Proof.
LetCp=v1,v2,…,vp,v1, then it is clear that every edge of Cp other than v1v2 lies on the v1−v2 detour. Moreover, the edge v1v2 lies on the v2−v3 detour. Thus, v1,v2,v3 is a c.e.d.b. of Cp, and hence cdn1Cp=3.Proposition 8.
LetKp be a complete graph of order p≥3, then for every pair u,v of vertices, every edge other than uv lies on a u−v detour of Kp.Proof.
One can easily check that the statement is true forp=3,4,and5. Now assume that the statement is true for p=r≥5, and consider Kr+2. Let x,y be any pair of vertices of Kr+2, and let Kr=Kr+2−x,y and VKr=v1,v2,…,vr−1,vr as shown in Figure 10.
By induction hypothesis for every pairvi,vj of vertices of Kr, every edge other than vivj of Kr lies on a vi−vj detour Q in Kr.
It is clear that the two edgesxvi, yvj or xvj,yvi with Q produce an x−y detour in Kr+2. This is true for all i,j=1,2,…,r,i≠j. Thus, every edge of Kr+2 other than xy lies on some x−y detour in Kr+2. Therefore, the proposition is true for Kr+2. Hence, by induction on p the proposition is true for Kp, p≥3.Figure 10
The graphKr+2,r≥5.Corollary 1.
For each complete graphKp with p≥3, cdn1Kp=3.Proof.
Letu,v,andw be any three vertices in Kp. By Proposition 8 every edge of Kp other than uv (resp., uw) lies on an u−v detour (resp., u−w detour). Thus, u,v,w is a c.e.d.s. of Kp. Clearly, cdn1Kp>2, and hence cdn1Kp=3.Corollary 2.
For every complete graphKp with p≥2, cdnKpc=2.Proof.
Letx,y be a pair of vertices of Kp, then by Proposition 8 every edge other than xy of Kp lies on an x−y detour in Kp. Thus, every vertex of Kpc other than u lies on an x−y detour in Kpc, in which vertex u corresponds to the edge xy in Kpc. Since vertex y is adjacent to u, then every vertex of Kpc lies on an x−u detour. Therefore, x,u is a c.d.b. of Kpc, and hence cdnKpc=2.Proposition 9.
LetKm,n, m,n≥2 be a complete bipartite graph, then for any pair of adjacent vertices u,v every edge other than uv lies on a u−v detour in Km,n.Proof.
One can easily check that the proposition holds forK2,2, K2,3, and K3,3. Now assume that it holds for Kr,s,r,s≥3, and consider Kr+1,s+1. Let xy be any edge of Kr+1,s+1, and let Kr,s=Kr+1,s+1−x,y as shown in Figure 11 in which its vertex set is X∪Y, X=x1,x2,…,xr, and Y=y1,y2,…,ys. By induction hypothesis, every edge of Kr,s other than xiyj1≤i≤r,1≤j≤s lies on xi−yj detour Q in Kr,s. Clearly, each xi−yj detour Q in Kr,s implies x−y detour Q′ (namely, x, yj−xi detour, and y) in Kr+1,s+1. Moreover, each edge of Kr,s with edges xyj and yxi lie on Q′. Since this holds for i=1,2,…,r and j=1,2,…,s, then every edge of Kr+1,s+1 (other than xy) lies on an x−y detour in Kr+1,s+1. Thus, by induction the proposition holds for every Km,n,m,n≥2.Figure 11
K
r
+
1
,
s
+
1
,
r
,
s
≥
3.Corollary 3.
For every complete bipartite graphKm,n,m,n≥2, then cdn1Km,n=3.Proof.
Consider the verticesx1,x2,andy1 of Km,n where x1x2∉EKm,n and x1y1,x2y1∈EKm,n. Then, by Proposition 9 every edge of Km,n (other than x1y1) lies on an x1−y1detour, and x1y1 lies on an x2−y1detour in Km,n. Therefore, x1,x2,y1 is a c.e.d.s. of Km,n, and hence cdn1Km,n=3.Corollary 4.
For every complete bipartite graphKm,n, m.n≥2, then cdnKm,nc=2.Proof.
Letxy be an edge of Km,n, then by Proposition 9 every edge other than xy lies on an x−y detour in Km,n. From the definition of cog-graphs, every vertex other than z lies on an x−y detour in Km,nc, where z is the vertex that corresponds to the edge xy in Km,nc. Adding the edge yz to every such x−y detour in Km,nc we obtain x−z detours, and hence every Km,nc lies on an x−z detour in Km,nc. Hence, cdnKm,nc=2.Proposition 10.
LetG be an E.D. graph of order p≥2, then cdnGc≤cdn1G.Proof.
LetB be a c.e.d.b. of G. If u,v∈B and uv is an edge of G, and w is the vertex in Gc that corresponds to the edge uv, then we interchange vertex v to vertex w in B. We repeat such interchange for every edge GB to get the set B′ of vertices in Gc. By Definitions 2 and 3, B′ is a c.d.s. of Gc, and B=B′. Thus, cdnGc≤B′=cdn1G.


## 5. Conclusions

The connected detour numbers for three classes of connected simple graphs are determined in this research paper. The three classes are unicyclic graphs, bicyclic graphs, and cog-graphs forCpc, Kpc, and Km,nc. We think that the methods used in proving the results in Section 3 can be used to determine the connected detour numbers for bridge graphs and chain graphs (defined in [16]) that are constructed from finite pairwise disjoint unicyclic graphs.It is shown thatcdnGc is related to cdn1G, and in view of Proposition 10 we suggest the following problem: characterize edge detour graphs G such that cdnGc=cdn1G.



---

*Source: 8272483-2019-11-03.xml*