Edgeless graphs are the only universal fixers.

DOI10.1007/S10587-014-0136-3MaRDI QIDQ5496701zbMATH OpenOpenAlexFDO

Authors Kirsti Wash

Publication date 27 January 2015

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

Full work available at URL https://arxiv.org/abs/1308.5466, http://hdl.handle.net/10338.dmlcz/144062

zbMATH Keywords

prismdomination numberuniversal fixer

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 5556299 (Why is no real title available?)
• Bipartite graphs are not universal fixers
• Claw-free graphs are not universal fixers
• On dominating the Cartesian product of a graph and K₂
• Regular 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)