Using determining sets to distinguish Kneser graphs

MaRDI QIDQ870080zbMATH OpenFDO

Authors Michael O. Albertson, Debra L. Boutin

Publication date 12 March 2007

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/127568, http://www.emis.de/journals/EJC/Volume_14/Abstracts/v14i1r20.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

distinguishing labeling

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Review text

Summary: This work introduces the technique of using a carefully chosen determining set to prove the existence of a distinguishing labeling using few labels. A graph \(G\) is said to be \(d\)-distinguishable if there is a labeling of the vertex set using \(1, \dots, d\) so that no nontrivial automorphism of \(G\) preserves the labels. A set of vertices \(S\subseteq V(G)\) is a determining set for \(G\) if every automorphism of \(G\) is uniquely determined by its action on \(S\). We prove that a graph is \(d\)-distinguishable if and only if it has a determining set that can be \((d-1)\)-distinguished. We use this to prove that every Kneser graph \(K_{n:k}\) with \(n\geq6\) and \(k\geq2\) is 2-distinguishable.

Recommendations

• The distinguishing chromatic number of Kneser graphs
• The list distinguishing number of Kneser graphs
• The determining number of Kneser graphs
• The cost of 2-distinguishing selected Kneser graphs and hypercubes
• Identifying graph automorphisms using determining sets

Cited in

(35)

• A note on the asymptotic and computational complexity of graph distinguishability
• The list distinguishing number of Kneser graphs
• The full automorphism groups, determining sets and resolving sets of coprime graphs
• The distinguishing chromatic number of Kneser graphs
• On the distinguishing number of cyclic tournaments: towards the Albertson-Collins conjecture
• The cost of 2-distinguishing hypercubes
• Graphs of order n with determining number n-3
• Symmetry parameters for Mycielskian graphs
• Trees with distinguishing number two
• On the distinguishing number of functigraphs
• Distinguishing number of hierarchical products of graphs
• Symmetry breaking in tournaments
• Distinguishing geometric graphs
• The determining number of a Cartesian product
• scientific article; zbMATH DE number 2113454 (Why is no real title available?)
• Infinite graphs with finite 2-distinguishing cost
• The cost number and the determining number of a graph
• Paint cost and the frugal distinguishing number
• Symmetry parameters of various hypercube families
• Distinguishing generalized Mycielskian graphs
• On some parameters related to fixing sets in graphs
• The cost of 2-distinguishing selected Kneser graphs and hypercubes
• The determining number of Kneser graphs
• Determining Number of Kneser Graphs: Exact Values and Improved Bounds
• On the connectivity of the disjointness graph of segments of point sets in general position in the plane
• Distinguishing orthogonality graphs
• Distinguishing threshold of graphs
• The determining number and cost of 2-distinguishing of select Kneser graphs
• Distinguishing labeling of the actions of almost simple groups.
• Symmetry parameters of two-generator circulant graphs
• Paint cost spectrum of perfect k-ary trees
• Determining number and cost of generalized Mycielskian graphs
• Identifying graph automorphisms using determining sets
• Automorphisms and distinguishing numbers of geometric cliques
• Determining sets, resolving sets, and the exchange property

This page was built for publication: Using determining sets to distinguish Kneser graphs

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