Symmetry breaking in planar and maximal outerplanar graphs
Saeid Alikhani, Samaneh Soltani · Discrete Mathematics Algorithms and Applications · 2018
The distinguishing number (index) [Formula: see text] ([Formula: see text]) of a graph [Formula: see text] is the least integer [Formula: see text] such that [Formula: see text] has a vertex (edge) labeling with [Formula: see text] labels that is preserved only by a trivial automorphism. In this paper, we consider the maximal outerplanar graphs (MOP graphs) and show that MOP graphs, except [Formula: see text], can be distinguished by at most two vertex (edge) labels. We also compute the distinguishing number and the distinguishing index of Halin and Mycielskian graphs.