Loading...
Please wait, while we are loading the content...
Similar Documents
Nordhaus-Gaddum Bounds for k-Domination in Graphs Noah Prince
| Content Provider | Semantic Scholar |
|---|---|
| Author | Prince, Noah |
| Copyright Year | 2007 |
| Abstract | A k-dominating set of a graph G is a set S of vertices of G such that every vertex outside of S has k neighbors in S. The k-domination number of G, written γk(G), is the size of the smallest k-dominating set in G. In this paper, we derive sharp upper and lower bounds on γk(G) + γk(G) and γk(G)γk(G), where G is the complement of G. We use the results for k = 2 to prove a conjecture of Alon, Balogh, Bollobás, and Szabó on game domination numbers. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.mathcs.emory.edu/~rg/prince.pdf |
| Alternate Webpage(s) | http://staff.imsa.edu/~nprince/researchfiles/NGkDom.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
