Breaking the Symmetries of Amenable Graphs
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911053739196416 |
|---|---|
| author | Cheng, Christine T. |
| author_facet | Cheng, Christine T. |
| contents | In this paper, we consider two ways of breaking a graph's symmetry: distinguishing labelings and fixing sets. A distinguishing labeling $ϕ$ of $G$ colors the vertices of $G$ so that the only automorphism of the labeled graph $(G, ϕ)$ is the identity map. The distinguishing number of $G$, $D(G)$, is the fewest number of colors needed to create a distinguishing labeling of $G$. A subset $S$ of vertices is a fixing set of $G$ if the only automorphism of $G$ that fixes every element in $S$ is the identity map. The fixing number of $G$, $Fix(G)$, is the size of a smallest fixing set. A fixing set $S$ of $G$ can be translated into a distinguishing labeling $ϕ_S$ by assigning distinct colors to the vertices in $S$ and assigning another color (e.g., the ``null" color) to the vertices not in $S$.
Color refinement is a well-known efficient heuristic for graph isomorphism. A graph $G$ is amenable if, for any graph $H$, color refinement correctly determines whether $G$ and $H$ are isomorphic or not. Using the characterization of amenable graphs by Arvind et al. as a starting point, we show that both $D(G)$ and $Fix(G)$ can be computed in $O((|V(G)|+|E(G)|) \log |V(G)|)$ time when $G$ is an amenable graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_09710 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Breaking the Symmetries of Amenable Graphs Cheng, Christine T. Combinatorics Discrete Mathematics 05 G.2.1; G.2.2 In this paper, we consider two ways of breaking a graph's symmetry: distinguishing labelings and fixing sets. A distinguishing labeling $ϕ$ of $G$ colors the vertices of $G$ so that the only automorphism of the labeled graph $(G, ϕ)$ is the identity map. The distinguishing number of $G$, $D(G)$, is the fewest number of colors needed to create a distinguishing labeling of $G$. A subset $S$ of vertices is a fixing set of $G$ if the only automorphism of $G$ that fixes every element in $S$ is the identity map. The fixing number of $G$, $Fix(G)$, is the size of a smallest fixing set. A fixing set $S$ of $G$ can be translated into a distinguishing labeling $ϕ_S$ by assigning distinct colors to the vertices in $S$ and assigning another color (e.g., the ``null" color) to the vertices not in $S$. Color refinement is a well-known efficient heuristic for graph isomorphism. A graph $G$ is amenable if, for any graph $H$, color refinement correctly determines whether $G$ and $H$ are isomorphic or not. Using the characterization of amenable graphs by Arvind et al. as a starting point, we show that both $D(G)$ and $Fix(G)$ can be computed in $O((|V(G)|+|E(G)|) \log |V(G)|)$ time when $G$ is an amenable graph. |
| title | Breaking the Symmetries of Amenable Graphs |
| topic | Combinatorics Discrete Mathematics 05 G.2.1; G.2.2 |
| url | https://arxiv.org/abs/2507.09710 |