Mycielskian symmetry-breaking conjecture

About 8 years old · traced to

Let GG be a connected graph of order n≥3n\geq 3, and let μ(G)\mu(G) denote its Mycielskian. Write D(G)D(G) for the distinguishing number of GG and D′(G)D'(G) for its distinguishing index. Mycielskian symmetry-breaking conjecture. Except for a finite number of graphs, one has

D(μ(G))≤D(G)andD′(μ(G))≤D′(G).D(\mu(G))\leq D(G)\quad\text{and}\quad D'(\mu(G))\leq D'(G).

The conjecture proposes that applying the Mycielskian does not increase either the distinguishing number or the distinguishing index, apart from finitely many connected graphs. The preceding results establish this monotonicity for the sequence of Mycielski graphs from MiM_i to Mi−1M_{i-1} for i≥5i\geq 5, but the general assertion remains open.

References

Primary source

Saeid Alikhani and Samaneh Soltani, “Symmetry breaking in planar and maximal outerplanar graphs”, arXiv:1801.08448 (2018).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.