Complete graph:K4: Difference between revisions

Revision as of 19:45, 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 graph is defined as the complete graph on a set of size four.

Arithmetic functions

Size measures

Function	Value	Explanation
size of vertex set	4	As $K_{n}, n = 4$ : $n = 4$
size of edge set	6	As $K_{n}, n = 4$ : $(\binom{n}{2}) = (\binom{4}{2}) = 6$

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 $K_{n}, n = 4$ : $n - 1 = 3$
eccentricity of a vertex	1	As $K_{n}, n = 4$ : 1 (true for all $n \geq 2$ , independent of $n$ )

Other numerical invariants

Function	Value	Explanation
clique number	4	As $K_{n}, n = 4$ : $n = 4$
independence number	1	As $K_{n}, n = 4$ : 1 (independent of $n$ )
chromatic number	4	As $K_{n}, n = 4$ : $n = 4$
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 $K_{n}, n = 4$ : 3 (because $n \geq 3$ )
even girth	4	As $K_{n}, n = 4$ : 4 (because $n \geq 4$ )
girth of a graph	3	As $K_{n}, n = 4$ : 3 (because $n \geq 3$ )

Algebraic theory

The adjacency matrix is:

$(\begin{matrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 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^{4} - 6 t^{2} - 8 t - 3$	As $K_{n}, n = 4$ : $(t + 1)^{n - 1} (t - n + 1) = (t + 1)^{3} (t - 3) = t^{4} - 6 t^{2} - 8 t - 3$
minimal polynomial	$t^{2} - 2 t - 3$	As $K_{n}, n = 4$ : $(t + 1) (t - n + 1) = t^{2} - (n - 2) t - (n - 1) = t^{2} - 2 t - 3$
rank of adjacency matrix	4	As $K_{n}, n = 4$ : $n = 4$
eigenvalues (roots of characteristic polynomial)	-1 (multiplicity 3), 3 (multiplicity 1)	As $K_{n}, n = 4$ : -1 (multiplicity $n - 1 = 3$ ), $n - 1 = 3$ (multiplicity 1)

@@ Line 49: / Line 49: @@
 |-
 | {{arithmetic function value|girth of a graph|3}} || As <math>K_n, n = 4</math>: 3 (because <math>n \ge 3</math>)
+|}
+==Algebraic theory==
+The adjacency matrix is:
+<math>\begin{pmatrix} 0 & 1 & 1 & 1\\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 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^4 - 6t^2 - 8t - 3</math> || As <math>K_n, n = 4</math>: <math>(t + 1)^{n-1}(t - n + 1) = (t + 1)^3(t - 3) = t^4 - 6t^2 - 8t - 3</math>
+|-
+| [[minimal polynomial of a graph|minimal polynomial]] || <math>t^2 - 2t - 3</math> || As <math>K_n, n = 4</math>: <math>(t + 1)(t - n + 1) = t^2 - (n - 2)t - (n - 1) = t^2 - 2t - 3</math>
+|-
+| rank of adjacency matrix || 4 || As <math>K_n, n = 4</math>: <math>n = 4</math>
+|-
+| eigenvalues (roots of characteristic polynomial) ||  -1 (multiplicity 3), 3 (multiplicity 1) || As <math>K_n, n = 4</math>: -1 (multiplicity <math>n - 1 = 3</math>), <math>n - 1 = 3</math> (multiplicity 1)
 |}