1. On domination number of 4-regular graphs
- Creator:
- Liu, Hailong and Sun, Liang
- Format:
- bez média and svazek
- Type:
- model:article and TEXT
- Subject:
- regular graph, dominating set, and domination number
- Language:
- English
- Description:
- Let $G$ be a simple graph. A subset $S \subseteq V$ is a dominating set of $G$, if for any vertex $v \in V~- S$ there exists a vertex $u \in S$ such that $uv \in E (G)$. The domination number, denoted by $\gamma (G)$, is the minimum cardinality of a dominating set. In this paper we prove that if $G$ is a 4-regular graph with order $n$, then $\gamma (G) \le \frac{4}{11}n$.
- Rights:
- http://creativecommons.org/publicdomain/mark/1.0/ and policy:public