Abstract | ||
---|---|---|
The queen's graph Q n has the squares of the n × n chessboard as its vertices; two squares are adjacent if they are in the same row, column, or diagonal. Let γ ( Q n ) and i ( Q n ) be the minimum sizes of a dominating set and an independent dominating set of Q n , respectively. We show that if n≡1 ( mod 4) and D is a d-element dominating set of Q n of a particular, commonly used kind, then for all k, γ(Q k )⩽(d+3)k/(n+2)+ O (1) . If also D is independent, then for all k, i(Q k )⩽(d+6)k/(n+2)+ O (1) . Other similar bounds are derived. Keywords Dominating set Queen domination Queen's graph |
Year | DOI | Venue |
---|---|---|
2002 | 10.1016/S0012-365X(00)00467-2 | Discrete Mathematics |
Keywords | Field | DocType |
domination number,upper bound,dominating set | Diagonal,Graph theory,Discrete mathematics,Graph,Combinatorics,Dominating set,Vertex (geometry),Upper and lower bounds,Domination analysis,Mathematics | Journal |
Volume | Issue | ISSN |
242 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
7 | 0.90 | 1 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
William D. Weakley | 1 | 56 | 10.40 |