19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

The Universal Fixer Conjecture

Presented by Dr. Kieka MYNHARDT
Type: Oral presentation
Track: Domination, Independence and Coloring of Product Graphs


For a graph G=(V,E) and a permutation π of V, the prism of G with respect to π is the graph πG obtained from two copies G′ and G" of G by joining u∈V′ and v∈V" if and only if v=π(u). If π is the identity, then πG=G×K₂, the cartesian product of G and K₂. The graph G×K₂ is often referred to as the prism of G and πG is called a generalized prism of G. A universal fixer is a graph whose domination number is equal to that of all its generalized prisms. The edgeless graphs are universal fixers. No other universal fixers have been discovered, and it has been conjectured that if G has an edge, then G is not a universal fixer. This conjecture, known as the "Universal fixer conjecture", is known to be true for (amongst others) claw-free graphs, bipartite graphs, regular graph and graphs with domination number at most 3. I shall survey known results on this conjecture and the methods used to obtain them.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors