Symmetry breaking in graphs (Q1918875): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
(2 intermediate revisions by one other user not shown) | |||
Property / author | |||
Property / author: Michael O. Albertson / rank | |||
Property / author | |||
Property / author: Michael O. Albertson / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Latest revision as of 07:15, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Symmetry breaking in graphs |
scientific article |
Statements
Symmetry breaking in graphs (English)
0 references
21 July 1996
0 references
Summary: A labeling of the vertices of a graph \(G\), \(\phi: V(G)\to \{1,\dots, r\}\), is said to be \(r\)-distinguishing provided no automorphism of the graph preserves all of the vertex labels. The distinguishing number of a graph \(G\), denoted by \(D(G)\), is the minimum \(r\) such that \(G\) has an \(r\)-distinguishing labeling. The distinguishing number of the complete graph on \(t\) vertices is \(t\). In contrast, we prove (i) given any group \(\Gamma\), there is a graph \(G\) such that \(\Aut(G)\) is \(\Gamma\) and \(D(G)= 2\); (ii) \(D(G)= O(\log(|\Aut(G)|))\); (iii) if \(\Aut(G)\) is abelian, then \(D(G)\leq 2\); (iv) if \(\Aut(G)\) is dihedral, then \(D(G)\leq 3\); and (v) if \(\Aut(G)= S_4\), then either \(D(G)= 2\) or \(D(G)= 4\).
0 references
symmetry breaking
0 references
labeling
0 references
automorphism
0 references
distinguishing number
0 references
group
0 references