On the distinguishing number of cyclic tournaments: towards the Albertson-Collins conjecture

DOI10.1016/J.DAM.2018.10.021MaRDI QIDQ2026341zbMATH OpenOpenAlexWikidataFDO

Authors Kahina Meslem, Éric Sopena

Publication date 19 May 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Albertson-Collins conjectureautomorphism groupcyclic tournamentdistinguishing number

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

Abstract: A distinguishing $r$-labeling of a digraph $G$ is a mapping $lambda$ from the set of verticesof $G$ to the set of labels $1,dots,r$ such that no nontrivial automorphism of $G$ preserves all the labels.The distinguishing number $D(G)$ of $G$ is then the smallest $r$ for which $G$ admits a distinguishing $r$-labeling.From a result of Gluck (David Gluck, Trivial set-stabilizers in finite permutation groups,{em Can. J. Math.} 35(1) (1983), 59--67),it follows that $D(T)=2$ for every cyclic tournament~$T$ of (odd) order $2q+1ge3$.Let $V(T)=0,dots,2q$ for every such tournament.Albertson and Collins conjectured in 1999that the canonical 2-labeling $lambd{a}^{\ast }$ given by$lambd{a}^{\ast }(i)=1$ if and only if $ileq$ is distinguishing.We prove that whenever one of the subtournaments of $T$ induced by vertices $0,dots,q$or $q+1,dots,2q$ is rigid, $T$ satisfies Albertson-Collins Conjecture.Using this property, we prove that several classes of cyclic tournaments satisfy Albertson-Collins Conjecture.Moreover, we also prove that every Paley tournament satisfies Albertson-Collins Conjecture.

Recommendations

• A conjecture on cycle-pancyclism in tournaments
• On disjoint cycles of the same length in tournaments
• scientific article; zbMATH DE number 810055
• On cycles in multipartite tournaments
• On the Number of Hamiltonian Cycles in a Tournament
• On \(n\)-partite tournaments with unique \(n\)-cycle
• Cycles in multipartite tournaments: Results and problems
• Cycles through arcs in multipartite tournaments and a conjecture of Volkmann
• Lichiardopol's conjecture on disjoint cycles in tournaments
• On cycles through a given vertex in multipartite tournaments

Cites work

• Another proof of Gluck's theorem
• Bounding the distinguishing number of infinite graphs and permutation groups
• Cartesian powers of graphs can be distinguished by two labels
• Destroying automorphisms by fixing nodes
• Distinguishability of locally finite trees
• Distinguishing Cartesian powers of graphs
• Distinguishing Cartesian powers of graphs
• Distinguishing Cartesian products of countable graphs
• Distinguishing colorings of Cartesian products of complete graphs
• Distinguishing infinite graphs
• Distinguishing number and adjacency properties
• Distinguishing number of countable homogeneous relational structures
• Finite factors of Bernoulli schemes and distinguishing labelings of directed graphs
• scientific article; zbMATH DE number 1439496 (Why is no real title available?)
• Identifying graph automorphisms using determining sets
• On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results
• On Computing the Distinguishing Numbers of Planar Graphs and Beyond: A Counting Approach
• On computing the distinguishing numbers of trees and forests
• Symmetry breaking in graphs
• Symmetry breaking in tournaments
• The cost of 2-distinguishing Cartesian powers
• The cost of 2-distinguishing selected Kneser graphs and hypercubes
• The distinguishing number of Cartesian products of complete graphs
• The distinguishing number of the hypercube
• Trivial Set-Stabilizers in Finite Permutation Groups
• Using determining sets to distinguish Kneser graphs

Cited in

(5)

• Lichiardopol's conjecture on disjoint cycles in tournaments
• Distinguishing numbers and distinguishing indices of oriented graphs
• scientific article; zbMATH DE number 1439496 (Why is no real title available?)
• Distinguishing orthogonality graphs
• Distinguishing tournaments with small label classes

This page was built for publication: On the distinguishing number of cyclic tournaments: towards the Albertson-Collins conjecture

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