Determining Number of Kneser Graphs: Exact Values and Improved Bounds

DOI10.46298/DMTCS.7627MaRDI QIDQ6041430zbMATH OpenWikidataFDO

Authors Angsuman Das, Hiranya Kishore Dey

Publication date 30 May 2023

Published in Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

automorphism groupsfixing number

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Structural characterization of families of graphs (05C75)

Abstract: The determining number of a graph $G=(V,E)$ is the minimum cardinality of a set $SsubseteqV$ such that pointwise stabilizer of $S$ under the action of $Aut(G)$ is trivial. In this paper, we provide some improved upper and lower bounds on the determining number of Kneser graphs. Moreover, we provide the exact value of the determining number for some subfamilies of Kneser graphs.

Recommendations

• The determining number of Kneser graphs
• Determining number of generalized and double generalized Petersen graph
• Determining number of some families of cubic graphs
• Graphs of order n with determining number n-3
• Using determining sets to distinguish Kneser graphs

Cites work

• Destroying automorphisms by fixing nodes
• Determining number of generalized and double generalized Petersen graph
• Determining number of some families of cubic graphs
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• Identifying graph automorphisms using determining sets
• The determining number of a Cartesian product
• The determining number of Kneser graphs
• The full automorphism groups, determining sets and resolving sets of coprime graphs
• Using determining sets to distinguish Kneser graphs

Cited in

(6)

• Optimal Real Number Graph Labellings of a Subfamily of Kneser Graphs
• Determining and distinguishing number of hypergraphs
• The determining number of Kneser graphs
• Determining number of some families of cubic graphs
• A formula for the base size of the symmetric group in its action on subsets
• Identifying graph automorphisms using determining sets

This page was built for publication: Determining Number of Kneser Graphs: Exact Values and Improved Bounds

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