Breaking the symmetries of Amenable graphs
Ars Combinatoria · 29.03.2026 · 166 · 85-108
DOI: 10.61091/ars166-07 ↗Kurz gefasst
Fachartikel in der Zeitschrift Ars Combinatoria, online erschienen am 29.03.2026. Verfasst von Christine T. Cheng.
Abstract (Originalsprache)
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.
Zitieren
APA
Cheng, C. T. (2026). Breaking the symmetries of Amenable graphs. Ars Combinatoria, 166, 85-108. https://doi.org/10.61091/ars166-07
Vancouver
Cheng CT. Breaking the symmetries of Amenable graphs. Ars Combinatoria. 2026;166:85-108. doi:10.61091/ars166-07
BibTeX
@article{Cheng2026,
author = {Cheng, Christine T.},
title = {Breaking the symmetries of Amenable graphs},
journal = {Ars Combinatoria},
year = {2026},
volume = {166},
pages = {85--108},
doi = {10.61091/ars166-07}
}
EUVIMED