Vertex transitive graphs G with _D (G)>(G) and small automorphism group

Abstract: For a graph

G

and a positive integer

k

, a vertex labelling

f : V (G) o 1, 2 l d o t s, k

is said to be

k

-distinguishing if no non-trivial automorphism of

G

preserves the sets

f^{- 1} (i)

for each

i i n 1, l d o t s, k

. The distinguishing chromatic number of a graph

G

, denoted

c h i_{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 i n m a t h b b N

, there exists an infinite sequence of vertex-transitive graphs

G_{i} = (V_{i}, E_{i})

such that

c h i_{D} (G_{i}) > c h i (G_{i}) > k

and

| m a t h r m A u t (G_{i}) | = O_{k} (| V_{i} |)

, where

m a t h r m A u t (G_{i})

denotes the full automorphism group of

G_{i}

. In particular, this answers a problem raised in the paper

c h i_{D} (G)

,

| m a t h r m A u t (G) |

and a variant of the Motion lemma.

Recommendations

Cites Work

Cited In (7)

This page was built for publication: Vertex transitive graphs \(G\) with \(\chi_D (G)>\chi(G)\) and small automorphism group