Edgeless graphs are the only universal fixers.

DOI10.1007/S10587-014-0136-3zbMATH Open1349.05266arXiv1308.5466OpenAlexW2084507246MaRDI QIDQ5496701FDOQ5496701

Authors: Kirsti Wash 

Publication date: 27 January 2015

Published in: Czechoslovak Mathematical Journal (Search for Journal in Brave)

Abstract: Given two disjoint copies of a graph $G$, denoted $G^1$ and $G^2$, and a permutation $pi$ of $V(G)$, the graph $piG$ is constructed by joining $uinV(G^1)$ to $pi(u)inV(G^2)$ for all $uinV(G^1)$. $G$ is said to be a universal fixer if the domination number of $piG$ is equal to the domination number of $G$ for all $pi$ of $V(G)$. In 1999 it was conjectured that the only universal fixers are the edgeless graphs. Since then, a few partial results have been shown. In this paper, we prove the conjecture completely.

Full work available at URL: https://arxiv.org/abs/1308.5466

Recommendations

• Regular graphs are not universal fixers
• Bipartite graphs are not universal fixers
• A proof of the universal fixer conjecture
• Claw-free graphs are not universal fixers
• Convex universal fixers

zbMATH Keywords

prismdomination numberuniversal fixer

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• On dominating the Cartesian product of a graph and K₂
• Title not available (Why is that?)
• Regular graphs are not universal fixers
• Bipartite graphs are not universal fixers
• Claw-free graphs are not universal fixers

Cited In (9)

• Distance 2-domination in prisms of graphs
• Regular graphs are not universal fixers
• Bipartite graphs are not universal fixers
• Claw-free graphs are not universal fixers
• Convex universal fixers
• Couterexample to a conjecture on the structure of bipartite partionable graphs
• Graphs with \(C_3\)-free vertices are not universal fixers
• Convex and weakly convex domination in prism graphs
• A proof of the universal fixer conjecture

This page was built for publication: Edgeless graphs are the only universal fixers.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5496701)