Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650314 | Discrete Mathematics | 2008 | 7 Pages |
Abstract
For any permutation ππ of the vertex set of a graph GG, the graph πGπG is obtained from two copies G′G′ and G″G″ of GG by joining u∈V(G′)u∈V(G′) and v∈V(G″)v∈V(G″) if and only if v=π(u)v=π(u). Denote the domination number of GG by γ(G)γ(G). For all permutations ππ of V(G)V(G), γ(G)≤γ(πG)≤2γ(G)γ(G)≤γ(πG)≤2γ(G). If γ(πG)=γ(G)γ(πG)=γ(G) for all ππ, then GG is called a universal fixer. We prove that graphs without 5-cycles are not universal fixers, from which it follows that bipartite graphs are not universal fixers.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
R.G. Gibson,