Domination in 4-regular Knödel graphs

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. For an even integer n ≥ 2 and 1 ≤ Δ ≤ ⌊log2n⌋, a Knödel graph WΔ, n is a Δ-regular bipartite graph of even order n, with vertices (i, j), for i = 1, 2 and 0 ≤ j ≤ n/2 − 1, where for every j, 0 ≤ j ≤ n/2 − 1, there is an edge between vertex (1, j) and every vertex (2, (j+2k − 1) mod (n/2)), for k = 0, 1, ⋯, Δ − 1. In this paper, we determine the domination number in 4-regular Knödel graphs W4,n.

Keywords

• knödel graph
• domination number
• pigoenhole principal
• 05c69
• 05c30