Odd graph: Difference between revisions

Revision as of 03:04, 29 May 2012

Definition

Let $n$ be a natural number greater than or equal to 2.

The odd graph with parameter $n$ , denoted $O_{n}$ , is defined as the Kneser graph $K G_{2 n - 1, n - 1}$ . Explicitly, dix a set of size $2 n - 1$ (we usually take the set as ${1, 2, \dots, 2 n - 1}$ for convenience). Then:

The vertex set of $O_{n}$ is the collection of $(n - 1)$ -element subsets of the fixed set of size $2 n - 1$ .
The edge set of $O_{n}$ is defined as follows: two vertices of $O_{n}$ are adjacent if and only if they are disjoint when viewed as subsets of the $(2 n - 1)$ -element set.

Particular cases

Value of $n$	Odd graph $O_{n}$
2	triangle graph
3	Petersen graph
4	odd graph:O4

Arithmetic functions

Size measures

Function	Value	Explanation
size of vertex set	$(\binom{2 n - 1}{n - 1}) = \frac{(2 n - 1)!}{(n - 1)! n!}$	By definition, it is the number of $(n - 1)$ -element subsets of a fixed $(2 n - 1)$ -element set.
size of edge set	$\frac{1}{2} (\binom{2 n - 1}{n - 1, n - 1, 1}) = \frac{1}{2} \frac{(2 n - 1)!}{(n - 1)! (n - 1)!}$	This is the number of ways of picking two disjoint and interchangeable $(n - 1)$ -element subsets from a $(2 n - 1)$ -element set.

Numerical invariants associated with vertices

Since the graph is a vertex-transitive graph, any numerical invariant associated to a vertex must be equal on all vertices of the graph. Below are listed some of these invariants:

Function	Value	Explanation
degree of a vertex	$n$	For any subset of size $n - 1$ , we need to count all the subsets of size $n - 1$ that are disjoint from it. This is $(\binom{(2 n - 1) - (n - 1)}{n - 1}) = (\binom{n}{n - 1}) = n$ .
eccentricity of a vertex	$n - 1$	Fill this in later

Other numerical invariants

Function	Value	Explanation
clique number	3 for $n = 2$ 2 for $n \geq 3$
independence number	Fill this in later
chromatic number	Fill this in later
radius of a graph	$n - 1$	Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
diameter of a graph	$n - 1$	Due to vertex-transitivity, the diameter equals the eccentricity of any vertex, which has been computed above.
odd girth	$2 n - 1$
even girth	6
girth of a graph	$min {2 n - 1, 6}$ . Explicitly, it is $2 n - 1$ for $n = 2, 3$ and 6 for $n \geq 4$ .

@@ Line 6: / Line 6: @@
 # The vertex set of <math>O_n</math> is the collection of <math>(n - 1)</math>-element subsets of the fixed set of size <math>2n - 1</math>.
-# The edge set of <math>O_n is defined as follows: two vertices of <math>O_n</math> are adjacent if and only if they are disjoint when viewed as subsets of the <math>(2n - 1)</math>-element set.
+# The edge set of <math>O_n</math> is defined as follows: two vertices of <math>O_n</math> are adjacent if and only if they are disjoint when viewed as subsets of the <math>(2n - 1)</math>-element set.
 ==Particular cases==