Hypergraphs for computing determining sets of Kneser graphs

Details Hypergraphs for computing determining sets of Kneser graphs Hypergraphs for computing determining sets of Kneser graphs

2011-11-14

arxiv.org/abs/1111.3252v1

Mathematics

Combinatorics

Scientific paper

A set of vertices $S$ is a \emph{determining set} of a graph $G$ if every automorphism of $G$ is uniquely determined by its action on $S$. The \emph{determining number} of $G$ is the minimum cardinality of a determining set of $G$. This paper studies determining sets of Kneser graphs from a hypergraph perspective. This new technique lets us compute the determining number of a wide range of Kneser graphs, concretely $K_{n:k}$ with $n\geq \frac{k(k+1)}{2}+1$. We also show its usefulness by giving shorter proofs of the characterization of all Kneser graphs with fixed determining number 2, 3 or 4, going even further to fixed determining number 5. We finally establish for which Kneser graphs $K_{n:k}$ the determining number is equal to $n-k$, answering a question posed by Boutin.

Affiliated with

Also associated with

No associations

Rating

Hypergraphs for computing determining sets of Kneser graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hypergraphs for computing determining sets of Kneser graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hypergraphs for computing determining sets of Kneser graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-218561