Finite and infinite vertex-transitive cubic graphs and their distinguishing cost and density

Authors

DOI:

https://doi.org/10.26493/2590-9770.1395.a37

Keywords:

Distinguishing number, asymmetrizing number, automorphisms, infinite graphs

Abstract

A set S of vertices in a graph G with nontrivial automorphism group is distinguishing if the identity mapping is the only automorphism that preserves S as a set. If such sets exist, then their minimum cardinality is the distinguishing cost ρ(G) of G. A closely related concept is the distinguishing density δ(G). For finite G it is the quotient of ρ(G) by the order of G.

We consider connected, vertex-transitive, cubic graphs G and show that either ρ(G) ≤ 5 or ρ(G) = ∞ and δ(G) = 0 if G has one or three arc-orbits, or two arc-orbits and vertex-stabilisers of order at most 2.

For the case of two arc-orbits and vertex stabilizers of order  > 2 we show the existence of finite graphs with ρ(G) > 5 and infinite graphs with δ(G) > 0.

We also prove that two well known results about finite, vertex-transitive, cubic graphs hold without the finiteness condition and construct infinitely many cubic GRRs.

Published

2022-08-30

Issue

Section

The Marston Conder Issue of ADAM