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

DOI10.26493/1855-3974.1435.C71MaRDI QIDQ5217075zbMATH OpenOpenAlexFDO

Authors Niranjan Balachandran, Sajith Padinhatteeri, Pablo Spiga

Publication date 21 February 2020

Published in Ars Mathematica Contemporanea (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.10465

zbMATH Keywords

Cayley graphsvertex transitive graphsdistinguishing chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Group actions on combinatorial structures (05E18)

Abstract: For a graph $G$ and a positive integer $k$, a vertex labelling $f:V(G)o1,2ldots,k$ is said to be $k$-distinguishing if no non-trivial automorphism of $G$ preserves the sets $f^{-1}(i)$ for each $iin1,ldots,k$. The distinguishing chromatic number of a graph $G$, denoted $ch{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 $kinmathbbN$, there exists an infinite sequence of vertex-transitive graphs $G_i=(V_i,E_i)$ such that $ch{i}_D(G_i)>chi(G_i)>k$ and $|mathrmAut(G_i)|=O_k(|V_i|)$, where $mathrmAut(G_i)$ denotes the full automorphism group of $G_i$. In particular, this answers a problem raised in the paper $ch{i}_D(G)$, $|mathrmAut(G)|$ and a variant of the Motion lemma.

Recommendations

• χ_D(G), |Aut(G)|, and a variant of the motion lemma
• Graphs with large distinguishing chromatic number
• Bounds on the distinguishing chromatic number
• Distinguishing numbers of finite 4-valent vertex-transitive graphs
• The distinguishing chromatic number of line graphs of complete graphs

Cites work

• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Abelian Carter subgroups in finite permutation groups.
• Asymptotic enumeration of vertex-transitive graphs of fixed valency
• Bounds on the distinguishing chromatic number
• Cayley graphs on abelian groups
• Distinguishing chromatic number of Cartesian products of graphs
• Finite primitive groups and regular orbits of group elements
• Finite soluble groups
• Linear point sets and Rédei type \(k\)-blocking sets in \(\mathrm{PG}(n,q)\)
• The distinguishing chromatic number
• The distinguishing chromatic number of Kneser graphs
• The finite primitive groups with soluble stabilizers, and the edge-primitive \(s\)-arc transitive graphs.
• χ_D(G), |Aut(G)|, and a variant of the motion lemma

Cited in

(7)

• Finite and infinite vertex-transitive cubic graphs and their distinguishing cost and density
• Distinguishing numbers of finite 4-valent vertex-transitive graphs
• Transitive coloring of graphs
• Bounds on the distinguishing chromatic number
• A conjecture on bipartite graphical regular representations
• The distinguishing chromatic number of line graphs of complete graphs
• The distinguishing chromatic number of Kneser graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5217075)