Complete bipartite graph:K3,3: Difference between revisions

Revision as of 20:20, 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 undirected graph is defined as the complete bipartite graph $K_{3,3}$ . Explicitly, it is a graph on six vertices divided into two subsets of size three each, with edges joining every vertex in one subset to every vertex in the other subset.

Explicit descriptions

Descriptions of vertex set and edge set

We provide a description where the vertex set is $\{1,2,3,4,5,6\}$ and the two parts are $\{1,2,3\}$ and $\{4,5,6\}$ :

Vertex set: $\{1,2,3,4,5,6\}$

Edge set: $\{\{1,4\},\{1,5\},\{1,6\},\{2,4\},\{2,5\},\{2,6\},\{3,4\},\{3,5\},\{3,6\}\}$

Adjacency matrix

The adjacency matrix is as follows:

${\begin{pmatrix}0&0&0&1&1&1\\0&0&0&1&1&1\\0&0&0&1&1&1\\1&1&1&0&0&0\\1&1&1&0&0&0\\1&1&1&0&0&0\\\end{pmatrix}}$

Arithmetic functions

Size measures

Function	Value	Explanation
size of vertex set	6	As $K_{m,n},m=n=3$ : $m+n=3+3=6$
size of edge set	9	As $K_{m,n},m=n=3$ : $mn=(3)(3)=9$

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_{m,n},m=n=3$ : Since $m,n$ are equal, the graph is vertex-transitive and $(m=n)$ -regular, so we get $m=n=3$
eccentricity of a vertex	2	As $K_{m,n},m=n=3$ : 3 (independent of $m,n$ , though it uses that both numbers are greater than 1)

Other numerical invariants

Function	Value	Explanation
clique number	2	As $K_{m,n},m=n=3$ : 2 (independent of $m,n$ , follows from being bipartite)
independence number	3	As $K_{m,n},m=n=3$ : $\max\{m,n\}=\max\{3,3\}=3$
chromatic number	2	As $K_{m,n},m=n=3$ : 3 (independent of $m,n$ , follows from being bipartite)
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	infinite	As $K_{m,n},m=n=3$ : infinite, since bipartite As $n$ -dimensional hypercube, $n=3$ : infinite, since bipartite
even girth	4	As $K_{m,n},m=n=3$ : 4 (independent of $m,n$ as long as both are greater than 1)
girth of a graph	4	As $K_{m,n},m=n=3$ : 4 (independent of $m,n$ as long as both are greater than 1)

@@ Line 20: / Line 20: @@
 <math>\begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 \\0 & 0 & 0 & 1 & 1 & 1 \\0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 &1 & 0 & 0 & 0 \\1 & 1 &1 & 0 & 0 & 0 \\1 & 1 &1 & 0 & 0 & 0 \\\end{pmatrix}</math>
+==Arithmetic functions==
+===Size measures===
+{| class="sortable" border="1"
+! Function !! Value !! Explanation
+|-
+| {{arithmetic function value|size of vertex set|6}} || As <math>K_{m,n}, m = n = 3</math>: <math>m + n = 3 + 3 = 6</math>
+|-
+| {{arithmetic function value|size of edge set|9}} || As <math>K_{m,n}, m = n = 3</math>: <math>mn = (3)(3) = 9</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>K_{m,n}, m = n = 3</math>: Since <math>m,n</math> are equal, the graph is vertex-transitive and <math>(m = n)</math>-regular, so we get <math>m = n = 3</math>
+|-
+| {{arithmetic function value|eccentricity of a vertex|2}} || As <math>K_{m,n}, m= n = 3</math>: 3 (independent of <math>m,n</math>, though it uses that both numbers are greater than 1)
+|}
+===Other numerical invariants===
+{| class="sortable" border="1"
+! Function !! Value !! Explanation
+|-
+| {{arithmetic function value|clique number|2}} || As <math>K_{m,n}, m = n = 3</math>: 2 (independent of <math>m,n</math>, follows from being bipartite)
+|-
+| {{arithmetic function value|independence number|3}} || As <math>K_{m,n}, m = n = 3</math>: <math>\max \{ m,n \} = \max \{ 3,3 \} = 3</math>
+|-
+| {{arithmetic function value|chromatic number|2}} || As <math>K_{m,n}, m = n = 3</math>: 3 (independent of <math>m,n</math>, follows from being bipartite)
+|-
+| {{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.
+|-
+| [[odd girth]] || infinite ||  As <math>K_{m,n}, m = n = 3</math>: infinite, since bipartite<br>As <math>n</math>-dimensional hypercube, <math>n = 3</math>: infinite, since bipartite
+|-
+| {{arithmetic function value|even girth|4}} || As <math>K_{m,n}, m = n = 3</math>: 4 (independent of <math>m,n</math> as long as both are greater than 1)
+|-
+| {{arithmetic function value|girth of a graph|4}} || As<math>K_{m,n}, m = n = 3</math>: 4 (independent of <math>m,n</math> as long as both are greater than 1)
+|}