首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 uV(G) and vV(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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号