For a graph G and a positive integer k, a vertex labelling f : V (G) → {1, 2, . . ., k} is said to be k-distinguishing if no non-trivial automorphism of G preserves the sets f− 1(i) for each i ∈ {1, . . ., k}. The distinguishing chromatic number of a graph G, denoted χD(G), is defined as the minimum k such that there is a k-distinguishing labelling of V (G) which is also a proper coloring of the vertices of G. In this paper, we prove the following theorem: Given k ∈ N, there exists an infinite sequence of vertex-transitive graphs Gi = (Vi, Ei) such that 1. χD(Gi) > χ(Gi) > k, 2. |Aut(Gi)| < 2k|Vi|, where Aut(Gi) denotes the full automorphism group of Gi. In particular, this answers a question posed by the first and second authors of this paper.
Balachandran, N., Padinhatteeri, S., Spiga, P. (2019). Vertex transitive graphs G with χD(G) > χ(G) and small automorphism group. ARS MATHEMATICA CONTEMPORANEA, 17(1), 311-318 [10.26493/1855-3974.1435.c71].
Vertex transitive graphs G with χD(G) > χ(G) and small automorphism group
Spiga P.
2019
Abstract
For a graph G and a positive integer k, a vertex labelling f : V (G) → {1, 2, . . ., k} is said to be k-distinguishing if no non-trivial automorphism of G preserves the sets f− 1(i) for each i ∈ {1, . . ., k}. The distinguishing chromatic number of a graph G, denoted χD(G), is defined as the minimum k such that there is a k-distinguishing labelling of V (G) which is also a proper coloring of the vertices of G. In this paper, we prove the following theorem: Given k ∈ N, there exists an infinite sequence of vertex-transitive graphs Gi = (Vi, Ei) such that 1. χD(Gi) > χ(Gi) > k, 2. |Aut(Gi)| < 2k|Vi|, where Aut(Gi) denotes the full automorphism group of Gi. In particular, this answers a question posed by the first and second authors of this paper.File | Dimensione | Formato | |
---|---|---|---|
Spiga-2018-Ars Math Contemporanea-preprint.pdf
accesso aperto
Descrizione: Article
Tipologia di allegato:
Submitted Version (Pre-print)
Licenza:
Creative Commons
Dimensione
167.97 kB
Formato
Adobe PDF
|
167.97 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.