Identifying graph automorphisms using determining sets
type: Item
instance of: scholarly article
title: Identifying graph automorphisms using determining sets
zbMATH Open document ID: 1111.05043
author: Debra L. Boutin
published in: The Electronic Journal of Combinatorics
publication date: 2007-03-12T00:00:00Z
full work available at URL: https://eudml.org/doc/127269
full work available at URL: v13i1r78.html
review text: Summary: A set of vertices \(S\) is a determining set for a graph \(G\) if every automorphism of \(G\) is uniquely determined by its action on \(S\). The determining number of a graph is the size of a smallest determining set. This paper describes ways of finding and verifying determining sets, gives natural lower bounds on the determining number, and shows how to use orbits to investigate determining sets. Further, determining sets of Kneser graphs are extensively studied, sharp bounds for their determining numbers are provided, and all Kneser graphs with determining number 2, 3, or 4 are given.
Mathematics Subject Classification ID: 05C25
zbMATH DE Number: 5132791
zbMATH Keywords: Kneser graphs
zbMATH Keywords: determining number
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5132791