Mynhardt–Roux path and cycle non-realisation conjecture for irredundance graphs

From papers

For a graph GG, an IR\operatorname{IR}-graph is a graph realised as the slide graph of the irredundance sets of GG. Let PnP_n and CnC_n denote the path and cycle on nn vertices.

Mynhardt–Roux's conjecture. For every n3n\geq3, PnP_n is not an IR\operatorname{IR}-graph, and for every n5n\geq5, CnC_n is not an IR\operatorname{IR}-graph.

This conjecture concerns which graphs can arise from slide reconfiguration of irredundance sets. The cited work had already established several non-realisation results, including stars, certain short paths and cycles, and some smallest irredundance trees; the assertions for all paths and cycles in the stated ranges remain open in the supplied context.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

C. M. Mynhardt and S. Nasserasr, “Reconfiguration of Colourings and Dominating Sets in Graphs: a Survey”, arXiv:2003.05956 (2020).

Additional references

2 papers in this index state this conjecture (2018–2020). The statement above is taken from the most recent of them; the others are arXiv:1812.03382.

Solutions 0

No solutions have been posted yet.