# On Vertex Covering Transversal Domination Number of Regular Graphs

Authors: R. Vasanthi; K. Subramanian
Journal: The Scientific World Journal
 (2016)

---

## Abstract

A simple graphG=(V,E) is said to be r-regular if each vertex of G is of degree r. The vertex covering transversal domination number γvct(G) is the minimum cardinality among all vertex covering transversal dominating sets of G. In this paper, we analyse this parameter on different kinds of regular graphs especially for Qn and H3,n. Also we provide an upper bound for γvct of a connected cubic graph of order n≥8. Then we try to provide a more stronger relationship between γ and γvct.


---

## Body

## 1. Introduction

Hamid [1] introduced independent transversal domination in graphs. It was defined using maximum independent set in a graph. Vasanthi and Subramanian [2] introduced vertex covering transversal domination in graphs using minimum vertex covering set in a graph. The vertex covering transversal domination number of some standard graphs such as Kn, Km,n, Pn, Cn, and Wn and trees is dealt with in paper [2]. Bounds of γvct are also established through various parameters in [2]. Lam et al. [3] worked on independent domination number of regular graphs. In this paper, we investigate our parameter γvct for regular graphs. Also we try to provide a more stronger relationship between γ and γvct.A simple graphG=(V,E) is said to be r-regular if each vertex of G is of degree r. A set I⊆V of vertices in G is called anindependent set if no two vertices in I are adjacent. Also I is said to be amaximum independent set if there is no other independent set I′ such that I′>I. The cardinality of a maximum independent set is called theindependence number and is denoted by β0(G). A set C⊆V of vertices in G is called avertex covering set (or simplycovering set) if every edge of G is incident to at least one vertex in C. Also C is said to be aminimum vertex covering set if there is no other vertex covering set C′ such that C′<C. The cardinality of a minimum vertex covering set is called thevertex covering number and is denoted by α0(G). A set D⊆V of vertices in the graph G is called adominating set if every vertex in V-D is adjacent to a vertex in D. A dominating set which intersects every minimum vertex covering set in G is called avertex covering transversal dominating set. The minimum cardinality of a vertex covering transversal dominating set is calledvertex covering transversal domination number of G and is denoted by γvct(G).The parameterindependent domination numberi(G) was introduced by Cockanye and Hedetniemi in [4]. Theindependent domination numberi(G) is the minimum cardinality among all independent dominating sets of G. An independent set is dominating if and only if it is maximal. So i(G) is the minimum cardinality of a maximal independent set in G. In paper [3], the following theorem which gives the upper bound for independent domination number of a connected cubic graph has been proved.Theorem 1.
IfG is a connected cubic graph of order n where n≥8, then i(G)≤2n/5.


## 2. Notations

We use the following notations throughout the paper:α0-set to denote minimum vertex covering set,β0-set to denote maximum independent set,γ-set to denote a dominating set of minimum cardinality,γvct-set to denote a vertex covering transversal dominating set of minimum cardinality,γ(G) to denote domination number of G,γvct(G) to denote vertex covering transversal domination number of G,i(G) to denote independent domination number of G,O(G) to denote the order of G,degG(u) to denote the degree of a vertex u in G.


## 3.γvct for Regular Graphs

Here, we provide the vertex covering transversal domination number of some standard regular graphs such as complete graphs, complete bipartite regular graphs, cycles, and hypercubeQn. We also establish γvct for certain family of regular graphs defined in [3].Example 2.
K
n is a (n-1)-regular graph and γvct(Kn)=2 for n≥2.Example 3.
C
n is a 2-regular graph of order n≥3 and (1)γvctCn=2ifn=3,43ifn=5n3otherwise.Example 4.
K
n
,
n is a complete bipartite n-regular graph and γvct(Kn,n)=2.The following theorem provides the vertex covering transversal domination number ofn-dimensional cube or hypercube Qn defined in [5].Theorem 5.
IfQn is a hypercube containing 2n vertices which is n-regular, then(2)γvctQn=2ifn=22n-2ifn≥3.Proof.
Then-dimensional cube or hypercube Qn contains 2n vertices and is n-regular. Each vertex in Qn is represented by a n-tuple with 0’s and 1’s. Two vertices in Qn are adjacent if and only if the n-tuples differ in exactly one position. Also any v∈Qn is the n-tuple binary number and its complement vc is also an n-tuple binary number obtained by replacing 0 by 1 and 1 by 0 in v. The weight of a 0,1 vertex is the number of 1’s occurring in it. There are exactly 2n-1 vertices of odd weight and 2n-1 vertices of even weight. Each edge of Qn consists of a vertex of even weight and a vertex of odd weight. The vertices of even weight form an independent set and so do the vertices of odd weight. Therefore Qn is bipartite with bipartitions S1 and S2 where S1 is the set of all n-tuples of even weight and S2 is the set of all n-tuples of odd weight with S1=S2=2n-1.
AlsoS1 and S2 are the only β0-sets of Qn. Since they are complements of each other, S1 and S2 are the only α0-sets of Qn.
Forn=2, Q2 is as shown in Figure 1. Obviously, S1=00,11 and S2=10,01 are α0-sets of Q2. Then D=00,10 is a γvct-set of Q2 and so γvct(Q2) = 2.
Now supposen≥3.
Forn=3, Q3 is the hypercube on 8 vertices which is 3-regular and is represented as in Figure 1. The only two α0- sets of Q3 are S1=000,011,110,101 and S2=001,010,100,111. Then γvct(Q3)=2 since every two-element set of the form v,vc where v∈S1 and vc∈S2 is a γvct-set.
Ifn=4, the hypercube Q4 contains 24 vertices and is 4-regular as shown in Figure 2. Q4 is bipartite with bipartitions S1=0000,0011,0110,1100,0101,1010,1001,1111 and S2=0001,0010,0100,1000,0111,1110,1011,1101. Also S1 and S2 are the only α0-sets of Q4.
LetD=0000,1111,0001,1110. Then D is a dominating set of Q4. Clearly it intersects both S1 and S2. Therefore D is a vertex covering transversal dominating set and so γvct(Q4)=4. Hence it remains to show that D is of minimum cardinality.
Suppose there exists a vertex covering transversal dominating setD′ of cardinality less than 4. It must have at least 2 vertices as it intersects both S1 and S2. Suppose D′=3. Since each vertex is of degree 4, all the three vertices in D′ may dominate at most 12 vertices. But there are 16 vertices in Q4 and so D′ do not dominate at least 1 vertex. This is a contradiction to the assumption that D′ is a vertex covering transversal dominating set.
Also any set containing two mutually complementary vertices fromS1, say, 1100, 0011, and the other two mutually complementary vertices from S2, say, 1000, 0111, form a γvct-set. Thus S=v1,v1c,v2,v2c where v1,v1c∈S1 and v2,v2c∈S2 is a γvct-set of Q4.
Ifn=5, the hypercube Q5 contains 25 = 32 vertices and the bipartition S1 contains 24 vertices and S2 contains 24 vertices. Let S=v1,v1c,v2,v2c,v3,v3c,v4,v4c where v1,v2,v3,v4∈S1 and v1c,v2c,v3c,v4c∈S2. Then S is a γ-set which intersects both S1 and S2. Hence γvct(Q5) = 23.
Thus in general,S=v1,v1c,v2,v2c,…,v2n-3-1,v2n-3-1c,v2n-3,v2n-3c is a γvct-set of Qn. In particular, if n is odd, v1,v2,…,v2n-3∈S1 and v1c,v2c,…,v2n-3c∈S2. If n is even, v1,v1c,v2,v2c,…,v2n-4,v2n-4c∈S1 and v2n-4+1,v2n-4+1c,…,v2n-3,v2n-3c∈S2. Hence γvct(Qn)=2n-2.Figure 1Figure 2Theorem 6.
IfG is a connected regular graph of degree n-2 and O(G)=n, then γvct(G)=2.Proof.
Choose any vertexu∈V(G). Then degG(u)=n-2; that is, u is adjacent to n-2 vertices in G. Then there remains exactly one vertex, say, v, which is not adjacent to u. Therefore S=u,v is an independent set of G. Also v is adjacent to n-2 vertices in G except u. Hence no other vertex may be included in S. Therefore S is a maximum independent set of G.
Now letw∈V-S. Then w is adjacent to both u and v. Since u dominates every vertex in G except v, and w dominates n-2 vertices including v, it is obvious that D=u,w is a dominating set which intersects every minimum vertex covering set of G. Also D is of minimum cardinality in G. Hence γvct(G)=2.
It is noted thatv,w is also a γvct-set.Remark 7.
In the above theorem,n should be even. For otherwise, if n is odd, then n-2 is odd which is impossible as the number of vertices of odd degree in a graph is even.Lemma 8.
Given positive integersp≥2 and q≥3, let G(p,q) be the family of graphs such that V=⋃i=1p‍(Xi∪Yi∪Zi) and E=E1∪E2∪E3∪E4 with Xi=xi1,xi2,…,xiq-1, Yi=yi1,yi2,…,yiq, Zi=zi1,zi2,…,ziq,E1=⋃i=1p‍xikyil;1≤k≤q-1,1≤l≤q,E2=⋃i=1p‍yikzik;1≤k≤q,E3=⋃i=1p‍zikzil;1≤k,l≤q,k≠l-zi1ziq,E4=ziqzi+11;1≤i≤p-1∪zpqz11.Then(i)
V(G)=p(3q-1),(ii)
G(p,q) is connected and q-regular,(iii)
γvct(G(p,q))=4p.Proof.
G
(
p
,
q
) contains p subgraphs which we shall call blocks each containing 3q-1 vertices and isomorphic to each other. By the edge set E4, we observe that they are connected to each other.
Thus (i) and (ii) are obvious.
Forq=4, two connected blocks of G(p,4) each consisting of 11 vertices are as shown in Figure 3.
NowI=⋃i=1p‍Yi is a maximum independent set of G(p,q). Then its complement S=V-I=⋃i=1p‍(Xi∪Zi) is a minimum vertex covering set of G(p,q).
AlsoIj=⋃i=1p‍(Yi-yij)∪zij and Jj=⋃i=1p‍(Xi)∪zij, 1≤j≤q are maximum independent sets in G(p,q). Let Sj and Tj be the complement of each Ij and Jj. Then Sj=⋃i=1p‍((Xi∪Zi)-zij∪yij) and Tj=⋃i=1p‍((Yi∪Zi)-zij), 1≤j≤q are minimum vertex covering sets in G(p,q). Now the subgraph Gi induced by Xi∪Yi in each block is a complete bipartite graph Kq-1,q.
Sinceγvct(Km,n)=2 if m,n>1, we have γvct(Kq-1,q)=2. Also each xij,yik for 1≤j≤q-1 and 1≤k≤q is a vertex covering transversal dominating set of Gi. Then xij,yik,zi1,ziq, 1≤j≤q-1 and 1≤k≤q, is a dominating set for each block. Therefore Djk=⋃i=1p‍{xij,yik,zi1,ziq}, 1≤j≤q-1 and 1≤k≤q, is a γ-set which intersects the only α0-sets S, Sj and Tj of G(p,q) for each j.
Henceγvct(G(p,q))=4p.Figure 3Theorem 9.
Ifq≥3, then there exists a connected q-regular graph with γvct(G)≥⌈4n/3q⌉ where n is the order of G.Proof.
LetG=G(p,q) be defined as in Lemma 8. Then γvct(G)/n=4/3q-1≥4/3q. Thus γvct(G)≥4n/3q.Lemma 10.
Given positive integersp≥1 and q≥2, let G∗(p,q) be the graph (V,E) with V=U∪[⋃i=12p+1‍(Vi∪Wi)] and E=E1∪E2∪E3∪E4 with U=u1,u2,…,u2p+1, Vi=vi1,vi2,…,viq+2p, Wi=wi1,wi2,…,wiq+2p-1,E1=ujuk;1≤j<k≤2p+1,E2=⋃i=12p+1‍uivik;1≤k≤q,E3=⋃i=12p+1‍{vi(q+2k-1)vi(q+2k);1≤k≤p},E4=⋃i=12p+1‍vikwil;1≤k≤q+2p,1≤l≤q+2p-1.Then(i)
V(G)=2(2p+1)(q+2p),(ii)
G∗(p,q) is connected and (q+2p)-regular,(iii)
γvct(G∗(p,q))=2(2p+1).Proof.
(i) and (ii) are obvious. Ifp=1 and q=2, the graph G∗(1,2) is as shown in Figure 4.
It is clear that eachIj=[⋃i=12p+1‍(Wi)]∪uj, j=1 to 2p+1, is a maximum independent set in G∗(p,q). Therefore its complement Jj=V-Ij=[⋃i=12p+1‍(Vi)]∪[U-uj], j=1 to 2p+1, is an α0 set in G∗(p,q). Further J1,J2,…,J2p and J2p+1 are the only α0-sets of G∗(p,q). Now each Sjk=⋃i=12p+1‍vik,wij, j=1 to q+2p-1, k=1 to q is a dominating set intersecting J1,J2,…,J2p and J2p+1 and also of minimum cardinality 2(2p+1).
Henceγvct(G∗(p,q))=2(2p+1).Figure 4Theorem 11.
For everyr≥4, there exists a connected r-regular graph G of order n such that γvct(G)=n/r.Proof.
LetG=G∗(p,q) be defined as in Lemma 10. Then G is a connected r-regular graph with r=q+2p. Also γvct(G)/n=1/q+2p.
Thusγvct(G)=n/r.Remark 12.
Theorems9 and 11 hold good if γvct is replaced by γ.


## 4.γvct for Regular Cubic Graphs

In this section, we provide the vertex covering transversal domination number of some regular cubic graphs especially Harary graphH3,n defined in [6]. We also obtain an upper bound for the vertex covering transversal domination number of a connected cubic graph.Example 13.
Consider the triangular prism graphY3 shown in Figure 5. It is a regular cubic graph.Figure 5Y
3 has 6 vertices and 9 edges. Assume that the graph Y3 is labelled as shown in the diagram. It is clear that uimod⁡3,vi+1mod⁡3 and uimod⁡3,vi+2mod⁡3 for i=0,1,2 are β0-sets of Y3. Then their complements Ci=ui+1mod⁡3,ui+2mod⁡3,vimod⁡3,vi+2mod⁡3 and Si=ui+1mod⁡3,ui+2mod⁡3,vimod⁡3,vi+1mod⁡3 for i=0,1,2 are α0-sets of Y3. Now each Di=uimod⁡3,vimod⁡3, i=0,1,2 is a γ-set for Y3. Clearly it intersects each Ci and Si. Therefore γvct(Y3)=2.Example 14.
Consider Peterson graph which is cubic regular shown in Figure6.Figure 6Assuming that the graphG is labelled as shown in Figure 6, it is obvious that Ii=vimod⁡5,vi+3mod⁡5,ui+1mod⁡5,ui+2mod⁡5, i=0,1,2,3,4 are β0-sets of G. Then their complements Ci=vi+1mod⁡5,vi+2mod⁡5,vi+4mod⁡5,uimod⁡5,ui+3mod⁡5, ui+4mod⁡5, i=0,1,2,3,4 are α0-sets of G. Now Si=vimod⁡5,ui+2mod⁡5,ui+3mod⁡5 are γ-sets intersecting each Ci. Hence γvct(G)=3.Note thatSi=vimod⁡5,vi+3mod⁡5,ui+4mod⁡5 are also γvct-sets in G.Theorem 15.
IfH3,n is a Harary graph with n≥6, then γvct(H3,n)=⌊n+1/3⌋.Proof.
H
3
,
n is a 3-regular graph and so n is even. By the definition of H3,n, every vertex vi∈H3,n is adjacent to the vertices vi+1, vi-1, and vi+k where n=2k.
LetV(H3,n)=v0,v1,v2,…,vn-1. The graphs H3,10 and H3,12 are shown in Figure 7.
Case  1. Suppose n=2k where k is odd.
ThenC1=v0,v2,v4,…,vn-2 and C2=v1,v3,v5,…,vn-1 are the only α0-sets of H3,n.
Subcase  1. Let n≡0 (mod⁡3).
ThenS=v0,v3,v6,…,vn-3 is a γ-set which intersects C1 and C2 and S=n/3.
Subcase  2. Suppose n≡1 (mod⁡3).
ThenS=v0,v3,v6,…,vn-4 is a γ-set which intersects C1 and C2 and S=n-1/3.
Subcase  3. Suppose n≡2 (mod⁡3).
ThenS=v0,v3,v6,…,vn-2 is a γ-set which intersects C1 and C2 with S=n+1/3.
Thus in all the subcases of Case  1,γvct(H3,n)=⌊n+1/3⌋.
Case  2. Suppose n=2k where k is even.
ThenIi={vimod⁡n,vi+2mod⁡n,…,vi+k-2mod⁡n, vi+k+1mod⁡n,vi+k+3mod⁡n,…,vi+n-5mod⁡n, vi+n-3mod⁡n} is a β0-set for each i=0,1,2,…,n-1.
ThereforeCi={vi+1mod⁡n,vi+3mod⁡n,…,vi+k-1mod⁡n, vi+kmod⁡n,vi+k+2mod⁡n,…,vi+n-4mod⁡n, vi+n-2mod⁡n, vi+n-1mod⁡n is an α0-set for each i=0,1,2,…,n-1.
Subcase  1. Let n≡0 (mod⁡3).
ThenSi=vimod⁡n,vi+3mod⁡n,vi+6mod⁡n,…, vi+n-3mod⁡n is a γ-set which intersects each Ci for i=0,1,2,…,n-1.
Subcase  2. Let n≡1 (mod⁡3).
ThenSi=vimod⁡n,vi+3mod⁡n,vi+6mod⁡n,…, vi+n-4mod⁡n is a γ-set which intersects each Ci for i=0,1,2,…,n-1.
Subcase  3. Let n≡2 (mod⁡3).
ThenSi=vimod⁡n,vi+3mod⁡n,vi+6mod⁡n,…, vi+n-2mod⁡n is a γ-set which intersects each Ci for i=0,1,2,…,n-1.
Theγvct-sets mentioned in all the subcases of Case  2 are also of cardinality ⌊n+1/3⌋.
Thusγvct(H3,n)=⌊n+1/3⌋.Figure 7Remark 16.
In most of the graphs considered by us, it is observed thatγvct=γ.Theorem 17.
IfG is a connected cubic graph of order n with n≥8, then γvct(G)≤⌈2n/5⌉.Proof.
LetI be an independent dominating set of cardinality i(G). Then I is a maximal independent set of minimum cardinality. Since I is independent, no two vertices of I are adjacent in G. Let J=V-I. Then the vertices in I are adjacent only to the vertices in J.
Case  1. Suppose I itself is a β0-set. Then J is an α0-set. Let S=I∪v where v∈J. Then S is a vertex covering transversal dominating set of G. Therefore γvct(G)≤i(G)+1. Hence γvct(G)≤2n/5+1 (by Theorem 1 proved in [3]).
Case  2. Suppose I is not a β0-set. But I is a maximal independent dominating set of minimum cardinality. We claim that I intersects every α0-set of G.
Suppose thatI does not intersect an α0-set C of G. Then I⊂V-C where V-C is a β0-set of G. This is a contradiction to the maximality of I.
HenceI itself is a vertex covering transversal dominating set of G. Therefore γvct(G)≤2n/5.
Thus Cases  1 and 2 imply thatγvct(G)≤⌈2n/5⌉.


## 5. Relation betweenγ(G) and γvct(G)

In this section, we prove a more stronger relationship betweenγ and γvct than that proved in [2]. In view of the results and theorems dealt with in the previous sections, we try to characterize graphs for which γ=γvct and γ<γvct.Theorem 18.
IfG is a simple connected graph, then γvct(G)≤γ(G)+1.Proof.
LetD be a minimum dominating set. If D=V(G), then obviously γvct(G)=γ(G). If not, then D⊂V(G) and V(G)-D≠ϕ. Let u∈V(G)-D. Then u is dominated by some vertex v in D. Let S=D∪u. Since uv is an edge in G, either u or v is included in every minimum vertex covering set of G. This implies that S intersects every minimum vertex covering set in G. Hence γvct(G)≤γ(G)+1.Theorem 19.
LetG be a simple connected graph. If there exists a γ-set which is not independent, then γvct(G)=γ(G).Proof.
LetD be a minimum dominating set which is not an independent set of G. Then at least two vertices, say, u, v in D, are adjacent to each other. Therefore uv is an edge in G and hence either u or v lies in every minimum vertex covering set of G. So D intersects every α0-set of G. Therefore D itself is a γvct-set. Hence γvct(G)=γ(G).Remark 20.
The converse is not true. Ifγvct(G)=γ(G), then there may exist a γ-set which is independent also. For example, consider C6, the cycle on 6 vertices as shown in Figure 8.
Obviouslyv1,v3,v5 and v2,v4,v6 are the only α0-sets of C6. Also v1,v4 is a γ-set which is independent. Further, it is a γvct-set as it intersects both the α0-sets of C6. Thus there exists a γ-set which is independent in C6 even though γvct(C6)=γ(C6).Figure 8Remark 21.
Now, the obvious question is “Ifγvct(G)=γ(G), is every γ-set of G a γvct-set?” The answer is “not always.” The γ-sets and γvct-sets in the graphs Q2 and Y3 discussed in the previous sections are the best examples for it. So it is noted that this happens if there exists a γ-set which is also a βo-set. It obviously produces the result that “If γvct(G)=γ(G)=βo(G), then there exists at least one γ-set in G which is not a γvct-set.” The next general question is that “What happens if all the γ-sets of G are β0-sets?”. The following theorem provides the answer to it.Theorem 22.
LetG be a simple connected graph. If every γ-set of G is a β0-set, then γvct(G)=γ(G)+1.Proof.
Since everyγ-set D of G is a β0-set, choose a vertex v in its complement. This is possible since D≠V(G) as D is a β0-set of a connected graph G. Obviously D is not a γvct-set as it does not intersect the α0-set V(G)-D. Let S=D∪v. We claim that S intersects every α0-set of G. Suppose that S∩C=Φ for some α0-set C in G. Then S⊆I where I=V(G)-C is a β0-set. This implies that β0(G)+1≤β0(G) which is a contradiction. Hence S intersects every α0-set of G. Also S is a γvct-set of G as it contains exactly one vertex more than that of the γ-set D. Thus γvct(G)=γ(G)+1.Remark 23.
It is easy to conclude that even thoughγvct=γ, there are graphs in which γ-sets do not become γvct-sets. This implies that the collection of γvct-sets in such graphs is contained in the collection of γ-sets. So this may lead to consider γvct-sets in the graphs for which γvct=γ when we are in a situation to select a minimum number of γ-sets in such graphs. This approach may affect a new variation in domination theory.



---

*Source: 1029024-2016-03-29.xml*