Vipul: /* Arithmetic functions */

2012-05-29T03:15:41Z

Arithmetic functions

← Older revision		Revision as of 03:15, 29 May 2012
Line 60:		Line 60:
	\| [[odd girth]] \|\| <math>2n - 1</math> \|\|		\| [[odd girth]] \|\| <math>2n - 1</math> \|\|
	\|-		\|-
	\| [[even girth]] \|\| 6 \|\|		\| [[even girth]] \|\| 6 for <math>n \ge 3</math><br><math>\infty</math> for <math>n = 2</math> \|\|
	\|-		\|-
	\| [[girth of a graph]] \|\| <math>\min \{ 2n - 1, 6 \}</math>. Explicitly, it is <math>2n - 1</math> for <math>n = 2,3</math> and 6 for <matH>n \ge 4</math>. \|\|		\| [[girth of a graph]] \|\| <math>\min \{ 2n - 1, 6 \}</math>. Explicitly, it is <math>2n - 1</math> for <math>n = 2,3</math> and 6 for <matH>n \ge 4</math>. \|\|
	\|}		\|}

Vipul: /* Definition */

2012-05-29T03:04:36Z

Definition

← Older revision		Revision as of 03:04, 29 May 2012
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 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==		==Particular cases==

Vipul: Created page with "==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 ..."

2012-05-29T03:02:25Z

Created page with "==Definition== Let <math>n</math> be a natural number greater than or equal to 2. The '''odd graph''' with parameter <math>n</math>, denoted <math>O_n</math>, is defined as ..."

New page

==Definition==

Let <math>n</math> be a natural number greater than or equal to 2.

The '''odd graph''' with parameter <math>n</math>, denoted <math>O_n</math>, is defined as the [[defining ingredient::Kneser graph]] <math>KG_{2n - 1,n - 1}</math>. Explicitly, dix a set of size <math>2n - 1</math> (we usually take the set as <math>\{1,2,\dots,2n - 1 \}</math> for convenience). Then:

# 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.

==Particular cases==

{| class="sortable" border="1"
! Value of <math>n</math> !! Odd graph <math>O_n</math>
|-
| 2 || [[triangle graph]]
|-
| 3 || [[Petersen graph]]
|-
| 4 || [[odd graph:O4]]
|}
==Arithmetic functions==

===Size measures===

{| class="sortable" border="1"
! Function !! Value !! Explanation
|-
| [[size of vertex set]] || <math>\binom{2n - 1}{n - 1} = \frac{(2n - 1)!}{(n - 1)!n!}</math> || By definition, it is the number of <math>(n - 1)</math>-element subsets of a fixed <math>(2n - 1)</math>-element set.
|-
| [[size of edge set]] || <math>\frac{1}{2} \binom{2n - 1}{n - 1, n - 1, 1} = \frac{1}{2} \frac{(2n - 1)!}{(n - 1)!(n - 1)!}</math> || This is the number of ways of picking two disjoint and interchangeable <math>(n - 1)</math>-element subsets from a <math>(2n - 1)</math>-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:

{| class="sortable" border="1"
! Function !! Value !! Explanation
|-
| [[degree of a vertex]] || <math>n</math> || For any subset of size <matH>n - 1</math>, we need to count all the subsets of size <math>n - 1</math> that are disjoint from it. This is <math>\binom{(2n - 1) - (n - 1)}{n - 1} = \binom{n}{n - 1} = n</math>.
|-
| [[eccentricity of a vertex]] || <math>n - 1</math> || {{fillin}}
|}

===Other numerical invariants===

{| class="sortable" border="1"
! Function !! Value !! Explanation
|-
| [[clique number]] || 3 for <matH>n =2</math><br>2 for <math>n \ge 3</math> ||
|-
| [[independence number]] || {{fillin}} ||
|-
| [[chromatic number]] || {{fillin}} ||
|-
| [[radius of a graph]] || <math>n - 1</math> || Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
|-
| [[diameter of a graph]] || <math>n - 1</math> || Due to vertex-transitivity, the diameter equals the eccentricity of any vertex, which has been computed above.
|-
| [[odd girth]] || <math>2n - 1</math> ||
|-
| [[even girth]] || 6 ||
|-
| [[girth of a graph]] || <math>\min \{ 2n - 1, 6 \}</math>. Explicitly, it is <math>2n - 1</math> for <math>n = 2,3</math> and 6 for <matH>n \ge 4</math>. ||
|}

Odd graph - Revision history

Vipul: /* Arithmetic functions */

Vipul: /* Definition */

Vipul: Created page with "==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 ..."

Vipul: Created page with "==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 ..."