IJPAM: Volume 50, No. 4 (2009)

ON THE DOMINATION NUMBER OF KNÖDEL GRAPH $W_{3,n}$

Fu Xueliang$^1$, Xirong Xu$^2$, Yang Yuansheng$^3$, Xue Feng$^4$
$^{1,2,3,4}$Department of Computer Science
Dalian University of Technology
Dalian, 116024, P.R. CHINA
$^2$e-mail: xirongxu@dlut.edu.cn
$^3$e-mail: yangys@dlut.edu.cn


Abstract.Let $G=(V(G),E(G))$ be a graph. A set $S \subseteq V(G) $ is a dominating set if every vertex of $V(G)-S$ is adjacent to some vertices in $S$. The domination number $\gamma(G)$ of $G$ is the minimum cardinality of a dominating set of $G$. In this paper, we study the domination number of Knödel graph $W_{3,n}$ and prove that for $n\geq 8$

\begin{displaymath}\begin{array}{llll} \gamma(W(3,n))=2\lfloor\frac{n}{8}\rfloo... ...2, & n=4,6\ $mod$\ 8.\\ \end{array} \right . \end{array}\end{displaymath}



Received: November 10, 2008

AMS Subject Classification: 05C35

Key Words and Phrases: dominating set, Knödel graph, domination number

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2009
Volume: 50
Issue: 4