Abstract | ||
---|---|---|
Let γ ( G ) be the domination number of a graph G and let G □ H denote the Cartesian product of graphs G and H . We prove that γ(X) = (Π m k = 1 n k ) (2m + 1) , where X = C 1 □ C 2 □ … □ C m and all n k = ¦C k ¦, 1 ⩽ k ⩽ m , are multiples of 2 m + 1. The methods we use to prove this result immediately lead to an algorithm for finding minimum dominating sets of the considered graphs. Furthermore the domination numbers of products of two cycles are determined exactly if one factor is equal to C 3 , C 4 or C 5 , respectively. |
Year | DOI | Venue |
---|---|---|
1995 | 10.1016/0166-218X(93)E0167-W | Discrete Applied Mathematics |
Keywords | Field | DocType |
dominating cartesian product,domination number | Graph theory,Discrete mathematics,Graph,Combinatorics,Dominating set,Cartesian product,Cartesian product of graphs,Graph product,Domination analysis,Mathematics | Journal |
Volume | Issue | ISSN |
59 | 2 | Discrete Applied Mathematics |
Citations | PageRank | References |
18 | 3.56 | 3 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Sandi Klavžar | 1 | 738 | 84.46 |
N Seifter | 2 | 137 | 26.49 |