Mycielskian symmetry-breaking conjecture

Let GG be a connected graph of order n3n\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 Mi1M_{i-1} for i5i\geq 5, but the general assertion remains open.

Sources & referencesView supporting material

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.