EUVIMEDEUVIMED entdecken
Crossref

Breaking the symmetries of Amenable graphs

Christine T. Cheng

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →