| Title:
|
An upper bound for domination number of 5-regular graphs (English) |
| Author:
|
Xing, Hua-Ming |
| Author:
|
Sun, Liang |
| Author:
|
Chen, Xue-Gang |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
56 |
| Issue:
|
3 |
| Year:
|
2006 |
| Pages:
|
1049-1061 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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$. (English) |
| Keyword:
|
domination number |
| Keyword:
|
5-regular graph |
| Keyword:
|
upper bounds |
| MSC:
|
05C69 |
| idZBL:
|
Zbl 1164.05425 |
| idMR:
|
MR2261676 |
| . |
| Date available:
|
2009-09-24T11:41:07Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/128129 |
| . |
| Reference:
|
[1] Y. Caro, Y. Roditty: On the vertex-independence number and star decomposition of graphs.Ars Combin. 20 (1985), 167–180. MR 0824858 |
| Reference:
|
[2] Y. Caro, Y. Roditty: A note on the $k$-domination number of a graph.Internat. J. Math. Sci. 13 (1990), 205–206. MR 1038667, 10.1155/S016117129000031X |
| Reference:
|
[3] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater: Fundamentals of domination in graphs.Marcel Dekker, New York, 1998. MR 1605684 |
| Reference:
|
[4] H. Liu, L. Sun: On domination number of 4-regular graphs.Czechoslovak Math. J. 54 (2004), 889–898. MR 2100002, 10.1007/s10587-004-6438-0 |
| Reference:
|
[5] W. McGuaig, B. Shepherd: Domination in graphs with minimum degree two.J. Graph Theory 13 (1989), 749–762. MR 1025896, 10.1002/jgt.3190130610 |
| Reference:
|
[6] O. Ore: Theory of Graphs. Amer. Math. Soc. Colloq. Publ. Vol. 38.Amer. Math. Soc., Providence, 1962. MR 0150753 |
| Reference:
|
[7] B. Reed: Paths, stars, and the number three.Comb. Prob. Comp. 5 (1996), 277–295. Zbl 0857.05052, MR 1411088, 10.1017/S0963548300002042 |
| Reference:
|
[8] H. Xing: The upper bounds on domination number of 6-regular graphs.Manuscript. |
| . |
