| Title:
|
On domination number of 4-regular graphs (English) |
| Author:
|
Liu, Hailong |
| Author:
|
Sun, Liang |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
54 |
| Issue:
|
4 |
| Year:
|
2004 |
| Pages:
|
889-898 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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$. (English) |
| Keyword:
|
regular graph |
| Keyword:
|
dominating set |
| Keyword:
|
domination number |
| MSC:
|
05C69 |
| idZBL:
|
Zbl 1080.05524 |
| idMR:
|
MR2100002 |
| . |
| Date available:
|
2009-09-24T11:18:39Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127938 |
| . |
| Reference:
|
[1] T. W. Haynes, S. T. Hedetniemi and P. J. Slater: Fundamentals of Domination in Graphs.Marcel Dekker, 1998. MR 1605684 |
| Reference:
|
[2] W. McGuaig and B. Shepherd: Domination in graphs with minimum degree two.J. Graph Theory 13 (1989), 749–762. MR 1025896 |
| Reference:
|
[3] O. Ore: Theory of Graphs.Amer. Math. Soc. Colloq. Publ. (AMS, Providence, RI) 38 (1962). Zbl 0105.35401, MR 0150753 |
| Reference:
|
[4] B. Reed: Paths, stars, and the number three.Comb. Prob. Comp. 5 (1996), 277–295. Zbl 0857.05052, MR 1411088, 10.1017/S0963548300002042 |
| . |
