Petersen graph: Difference between revisions

Revision as of 03:16, 29 May 2012

This article defines a particular undirected graph, i.e., the definition here determines the graph uniquely up to graph isomorphism.
View a complete list of particular undirected graphs

Definition

The Petersen graph is a particular undirected graph on 10 vertices that can be defined in the following equivalent ways:

It is the complement of the line graph of complete graph:K5.
It is the odd graph with parameter 3, i.e., the graph $O_{3}$ . Explicitly, this is the Kneser graph $KG_{5,2}$ : its vertices are identified with subsets of size two of a 5-element set, and two vertices are adjacent if and only if the corresponding subsets are disjoint.
It is the unique 5-cage.

Arithmetic functions

Size measures

Function	Value	Explanation
size of vertex set	10	As $O_{n},n=3$ : ${\binom {2n-1}{n-1}}={\binom {5}{2}}=10$
size of edge set	15	As $O_{n},n=3$ : ${\frac {1}{2}}{\binom {2n-1}{n-1,n-1,1}}={\frac {1}{2}}{\binom {5}{2,2,1}}=15$

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	3	As $O_{n},n=3$ : $n=3$
eccentricity of a vertex	2	As $O_{n},n=3$ : $n-1=2$

Other numerical invariants

Function	Value	Explanation
clique number	2	As $O_{n},n=3$ : 2, since $n\geq 3$
independence number	4	Fill this in later
chromatic number	3
radius of a graph	2	Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
diameter of a graph	2	Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
odd girth	5	As $O_{n},n=3$ : $2n-1=2(3)-1=5$
even girth	6	As $_{n},n=3$ : 6 (we use that $n\geq 3$ )
girth of a graph	5	As $O_{n},n=3$ : $\min\{2n-1,6\}$

@@ Line 6: / Line 6: @@
 # It is the [[defining ingredient::complement of a graph|complement]] of the [[defining ingredient::line graph]] of [[defining ingredient::complete graph:K5]].
-# It is the [[defining ingredient::Kneser graph]] <math>KG_{5,2}</math>: its vertices are identified with subsets of size two of a 5-element set, and two vertices are adjacent if and only if the corresponding subsets are disjoint.
+# It is the [[defining ingredient::odd graph]] with parameter 3, i.e., the graph <math>O_3</math>. Explicitly, this is the [[defining ingredient::Kneser graph]] <math>KG_{5,2}</math>: its vertices are identified with subsets of size two of a 5-element set, and two vertices are adjacent if and only if the corresponding subsets are disjoint.
 # It is the unique 5-[[defining ingredient::cage]].
+==Arithmetic functions==
+===Size measures===
+{| class="sortable" border="1"
+! Function !! Value !! Explanation
+|-
+| {{arithmetic function value|size of vertex set|10}} || As <math>O_n, n = 3</math>: <math>\binom{2n - 1}{n - 1} = \binom{5}{2} = 10</math>
+|-
+| {{arithmetic function value|size of edge set|15}} || As <math>O_n, n = 3</math>: <math>\frac{1}{2} \binom{2n - 1}{n - 1,n - 1,1} = \frac{1}{2} \binom{5}{2,2,1} = 15</math>
+|}
+===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
+|-
+| {{arithmetic function value|degree of a vertex|3}} || As <math>O_n, n = 3</math>: <math>n = 3</math>
+|-
+| {{arithmetic function value|eccentricity of a vertex|2}} || As <math>O_n, n = 3</math>: <math>n - 1 = 2</math>
+|}
+===Other numerical invariants===
+{| class="sortable" border="1"
+! Function !! Value !! Explanation
+|-
+| {{arithmetic function value|clique number|2}} || As <math>O_n, n = 3</math>: 2, since <math>n \ge 3</math>
+|-
+| {{arithmetic function value|independence number|4}} || {{fillin}}
+|-
+| {{arithmetic function value|chromatic number|3}} ||
+|-
+| {{arithmetic function value|radius of a graph|2}} || Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
+|-
+| {{arithmetic function value|diameter of a graph|2}} || Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
+|-
+| {{arithmetic function value|odd girth|5}} || As <math>O_n ,n = 3</math>: <math>2n - 1 = 2(3) - 1 = 5</math>
+|-
+| {{arithmetic function value|even girth|6}} || As <math>_n, n = 3</math>: 6 (we use that <matH>n \ge 3</math>)
+|-
+| {{arithmetic function value|girth of a graph|5}} || As <matH>O_n, n = 3</math>: <math>\min \{ 2n - 1,6 \}</math>
+|}