Total domination in cubic Knodel graphs

Document Type : Original paper

Authors

1 Departtment of Mathematics, University of Mazandaran

2 Shahrood University of Technology

3 Tafresh University

Abstract

A subset D of vertices of a graph G is a dominating set if for each u ∈ V (G) \ D, u is adjacent to some
vertex v ∈ D. The domination number, γ(G) of
G, is the minimum cardinality of a dominating set of G. A set
D ⊆ V (G) is a total dominating set if for each
u ∈ V (G)u is adjacent to some vertex v ∈ D. The
total domination numberγt (G) of G, is the
minimum cardinality of a total dominating set of G. For an even
integer $nge 2$ and $1\le Delta \le lfloorlog_2nrfloor$, a
Knodel graph $W_{Delta,n}$ is a $Delta$-regular
bipartite graph of even order n, with vertices (i,j), for
$i=1,2$ and $0le jle n/2-1$, where for every $j$, $0le jle
n/2-1$, there is an edge between vertex $(1, j)$ and every vertex
$(2,(j+2^k-1)$ mod (n/2)), for $k=0,1,cdots,Delta-1$. In this
paper, we determine the total domination number in $3$-regular
Knodel graphs $W_{3,n}$.

Keywords

Main Subjects