Total domination in cubic Knodel graphs

Nader Jafari Rad | D. Mojdeh | S. Mousavi | E. Nazari

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=169865
Date :  2021/12/08
Publish in :    Communications in Combinatorics and Optimization

Link :  http://comb-opt.azaruniv.ac.ir/article_14133.html
Keywords : Knodel graph, domination number, total domination number, Pigeonhole Principle

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 n≥2 and 1≤Δ≤⌊log2n⌋, a Knodel graph WΔ,n is a Δ-regular bipartite graph of even order n, with vertices (i,j), for i=1,2 and 0≤j≤n2−1, where for every j, 0≤j≤n2−1, there is an edge between vertex (1,j) and every vertex (2,(j+2k−1) mod n2), for k=0,1,…,Δ−1. In this paper, we determine the total domination number in 3-regular Knodel graphs W3,n.