Bipartite graphs are not universal fixers |
| |
Authors: | RG Gibson |
| |
Institution: | Department of Mathematics, Simon Fraser University, 8888 University Drive, Burnaby, BC, Canada V5A 1S6 |
| |
Abstract: | For any permutation π of the vertex set of a graph G, the graph πG is obtained from two copies G′ and G″ of G by joining u∈V(G′) and v∈V(G″) if and only if v=π(u). Denote the domination number of G by γ(G). For all permutations π of V(G), γ(G)≤γ(πG)≤2γ(G). If γ(πG)=γ(G) for all π, then G 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: | Domination Prisms of graphs Universal fixers Bipartite graphs |
本文献已被 ScienceDirect 等数据库收录! |
|