Triangle graph: Difference between revisions

Revision as of 19:37, 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

This is a particular finite undirected graph defined as follows:

It is a graph whose geometric realization is a triangle: it has three vertices and an edge between each pair of vertices.
It is the cycle graph on 3 vertices, and is denoted $C_{3}$ .
It is the complete graph on 3 vertices, and is denoted $K_{3}$ .
It is the odd graph $O_{2}$ , i.e., the Kneser graph $K G_{3, 1}$ .

Explicit descriptions

Descriptions of vertex set and edge set

Vertex set: ${1, 2, 3}$

Edge set: ${{1, 2}, {2, 3}, {1, 3}}$

Adjacency matrix

The adjacency matrix is:

$(\begin{matrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{matrix})$

Arithmetic functions

Size measures

Function	Value	Explanation
size of vertex set	3	As $C_{n}, n = 3$ : $n = 3$ As $K_{n}, n = 3$ : $n = 3$ As $O_{n}, n = 2$ : $(\binom{2 n - 1}{n - 1}) = (\binom{3}{1}) = 3$
size of edge set	3	As $C_{n}, n = 3$ : $n = 3$ As $K_{n}, n = 3$ : $(\binom{n}{2}) = (\binom{3}{2}) = 3$ As $O_{n}, n = 2$ : $(\binom{2 n - 1}{n - 1, n - 1, 1}) = (\binom{3}{1, 1, 1}) = 3$

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	2	As $C_{n}, n = 3$ : 2 (independent of $n$ ) As $K_{n}, n = 3$ : $n - 1 = 2$ As $O_{n}, n = 2$ : $n = 2$
eccentricity of a vertex	1	As $C_{n}, n = 3$ : greatest integer function of $n / 2$ equals greatest integer function of 3/2 equals 1 As $K_{n}, n = 3$ : 1 (true for any $n \geq 2$ ) As $O_{n}, n = 2$ : $n - 1 = 1$

Other numerical invariants

Function	Value	Explanation
clique number	3	As $C_{n}, n = 3$ : 3 (since $n = 3$ ; it's 2 for larger $n$ ) As $K_{n}, n = 3$ : $n = 3$ As $O_{n}, n = 2$ : 3
independence number	1	As $C_{n}, n = 3$ : greatest integer function of $n / 2$ equals greatest integer function of 3/2 equals 1 As $K_{n}, n = 3$ : 1 (independent of $n$ )
chromatic number	3	As $C_{n}, n = 3$ : 3 since $n$ is odd As $K_{n}, n = 3$ : $n = 3$
radius of a graph	1	Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
diameter of a graph	1	Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
odd girth	3	As $C_{n}, n = 3$ : $n = 3$ As $K_{n}, n = 3$ : 3 (true for any $n \geq 3$ ) As $O_{n}, n = 2$ : $2 n - 1 = 2 (2) - 1 = 3$
even girth	infinite	there are no cycles of even length
girth of a graph	3	minimum of even and odd girth

Algebraic theory

The adjacency matrix is:

$(\begin{matrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{matrix})$

The matrix is uniquely defined (note that it centralizes all permutations). Below are some important associated algebraic invariants:

Algebraic invariant	Value	Explanation
characteristic polynomial	$t^{3} - 3 t - 2$
minimal polynomial	$t^{2} - t - 2$
rank of adjacency matrix	3
eigenvalues (roots of characteristic polynomial)	-1 (multiplicity 2), 2 (multiplicity 1)

@@ Line 9: / Line 9: @@
 # It is the [[complete graph]] on 3 vertices, and is denoted <math>K_3</math>.
 # It is the [[odd graph]] <math>O_2</math>, i.e., the [[Kneser graph]] <math>KG_{3,1}</math>.
+==Explicit descriptions==
+===Descriptions of vertex set and edge set===
+Vertex set: <math>\{ 1,2,3 \}</math>
+Edge set: <math>\{ \{ 1,2 \}, \{ 2,3 \}, \{ 1,3 \}\}</math>
+===Adjacency matrix===
+The adjacency matrix is:
+<math>\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end{pmatrix}</math>
 ==Arithmetic functions==
@@ Line 54: / Line 68: @@
 |-
 | {{arithmetic function value|girth of a graph|3}} || minimum of even and odd girth
+|}
+==Algebraic theory==
+The adjacency matrix is:
+<math>\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end{pmatrix}</math>
+The matrix is uniquely defined (note that it centralizes all permutations). Below are some important associated algebraic invariants:
+{| class="sortable" border="1"
+! Algebraic invariant !! Value !! Explanation
+|-
+| [[characteristic polynomial of a graph|characteristic polynomial]] || <math>t^3 - 3t - 2</math> ||
+|-
+| [[minimal polynomial of a graph|minimal polynomial]] || <math>t^2 - t - 2</math> ||
+|-
+| rank of adjacency matrix || 3 ||
+|-
+| eigenvalues (roots of characteristic polynomial) ||  -1 (multiplicity 2), 2 (multiplicity 1) ||
 |}