Abstract
Let G be a graph and Ḡ be the complement of G. The complementary prism GḠ of G is the graph formed from the disjoint union of G and Ḡ by adding the edges of a perfect matching between the corresponding vertices of G and Ḡ. For example, if G is a 5-cycle, then GḠ is the Petersen graph. In this paper we consider domination and total domination numbers of complementary prisms. For any graph G, max {γ(G), γ(Ḡ)} ≤ γ (Ḡ)and max {γt(G), γt(Ḡ)} ≤ γt (Gγ), where γ(G) and γt(G) denote the domination and total domination numbers of G, respectively. Among other results, we characterize the graphs G attaining these lower bounds.
Original language | English |
---|---|
Pages (from-to) | 23-37 |
Number of pages | 15 |
Journal | Journal of Combinatorial Optimization |
Volume | 18 |
Issue number | 1 |
DOIs | |
Publication status | Published - Jul 2009 |
Externally published | Yes |
Keywords
- Cartesian product
- Complementary prism
- Domination
- Total domination
ASJC Scopus subject areas
- Computer Science Applications
- Discrete Mathematics and Combinatorics
- Control and Optimization
- Computational Theory and Mathematics
- Applied Mathematics