You're viewing this item in the new Europeana website. View this item in the original Europeana.

An upper bound for domination number of 5-regular graphs

Let $G=(V, E)$ be a simple graph. A subset $S\subseteq V$ is a dominating set of $G$, if for any vertex $u\in V-S$, there exists a vertex $v\in S$ such that $uv\in E$. The domination number, denoted by $\gamma (G)$, is the minimum cardinality of a dominating set. In this paper we will prove that if $G$ is a 5-regular graph, then $\gamma (G)\le {5\over 14}n$.