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: [email protected]
$^3$e-mail: [email protected]


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