Complete bipartite graph:K3,3 - Revision history

Vipul: /* Arithmetic functions */

2014-05-26T00:31:06Z

Arithmetic functions

← Older revision		Revision as of 00:31, 26 May 2014
Line 56:		Line 56:
	\| {{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\|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\|chromatic 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\|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\|radius of a graph\|2}} \|\| Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.

Vipul: /* Normalized Laplacian matrix */

2014-05-26T00:18:34Z

Normalized Laplacian matrix

← Older revision		Revision as of 00:18, 26 May 2014
Line 150:		Line 150:
	\| characteristic polynomial \|\| <math>t(t - 2)(t - 1)^4</math>\|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>t(t - 2)(t - 1)^{m + n -2}</math>		\| characteristic polynomial \|\| <math>t(t - 2)(t - 1)^4</math>\|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>t(t - 2)(t - 1)^{m + n -2}</math>
	\|-		\|-
	\| minimal polynomial \|\| <math>t(t - 1)(t - 2)</math> \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>t(t - 1)(t - 2)</math> (independent of <math>m,n</math> as long as <math>m + n > 2</math>		\| minimal polynomial \|\| <math>t(t - 1)(t - 2)</math> \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>t(t - 1)(t - 2)</math> (independent of <math>m,n</math> as long as <math>m + n > 2</math>)
	\|-		\|-
	\| rank of normalized Laplacian matrix \|\| 5 \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>m + n - 1 = 3 + 3 - 1 = 5</math>		\| rank of normalized Laplacian matrix \|\| 5 \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>m + n - 1 = 3 + 3 - 1 = 5</math>

Vipul: /* Normalized Laplacian matrix */

2014-05-26T00:16:04Z

Normalized Laplacian matrix

← Older revision		Revision as of 00:16, 26 May 2014
Line 154:		Line 154:
	\| rank of normalized Laplacian matrix \|\| 5 \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>m + n - 1 = 3 + 3 - 1 = 5</math>		\| rank of normalized Laplacian matrix \|\| 5 \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>m + n - 1 = 3 + 3 - 1 = 5</math>
	\|-		\|-
	\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), 2 (1 time), 1 (4 times) \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (1 time), 2 (1 time), 1 (<math>m + n- 2 = 3 + 3 - 2 = 2</math> times)		\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), 2 (1 time), 1 (4 times) \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (1 time), 2 (1 time), 1 (<math>m + n- 2 = 3 + 3 - 2 = 4</math> times)
	\|}		\|}

Vipul: /* Normalized Laplacian matrix */

2014-05-26T00:15:49Z

Normalized Laplacian matrix

← Older revision		Revision as of 00:15, 26 May 2014
Line 148:		Line 148:
	! Algebraic invariant !! Value !! Explanation		! Algebraic invariant !! Value !! Explanation
	\|-		\|-
	\| characteristic polynomial \|\| <math>t(t - 2)(t - 1)^4</math>\|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>t(t - ~~(m + n)/\sqrt{mn}~~)(t ~~- \sqrt{m/n})^{n~~-1~~}(t-\sqrt{n/m}~~)^{m-1}</math>		\| characteristic polynomial \|\| <math>t(t - 2)(t - 1)^4</math>\|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>t(t - 2)(t - 1)^{m + n -2}</math>
	\|-		\|-
	\| minimal polynomial \|\| <math>t(t - 1)(t - 2)</math> \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>t(t - 1)(t - (m + n~~)/\sqrt{mn}) = t(t - 1)(t -~~ 2)</math>		\| minimal polynomial \|\| <math>t(t - 1)(t - 2)</math> \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>t(t - 1)(t - 2)</math> (independent of <math>m,n</math> as long as <math>m + n > 2</math>
	\|-		\|-
	\| rank of normalized Laplacian matrix \|\| 5 \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>m + n - 1 = 3 + 3 - 1 = 5</math>		\| rank of normalized Laplacian matrix \|\| 5 \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>m + n - 1 = 3 + 3 - 1 = 5</math>
	\|-		\|-
	\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), 2 (1 time), 1 (4 times) \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (1 time), ~~<math>(m + n)/\sqrt{mn} = 3</math>~~ (1 time), 1 (<math>m + n- 2 = 3 + 3 - 2 = 2</math> times)		\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), 2 (1 time), 1 (4 times) \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (1 time), 2 (1 time), 1 (<math>m + n- 2 = 3 + 3 - 2 = 2</math> times)
	\|}		\|}

Vipul: /* Definition */

2014-05-25T23:20:19Z

Definition

← Older revision		Revision as of 23:20, 25 May 2014
Line 4:		Line 4:

	This [[undirected graph]] is defined as the [[complete bipartite graph]] <math>K_{3,3}</math>. 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.		This [[undirected graph]] is defined as the [[complete bipartite graph]] <math>K_{3,3}</math>. 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.

			The graph is also known as the '''utility graph'''. The name arises from a real-world problem that involves connecting three utilities to three buildings. The problen is modeled using this graph.

	==Explicit descriptions==		==Explicit descriptions==

Vipul: /* Normalized Laplacian matrix */

2014-05-25T23:16:37Z

Normalized Laplacian matrix

← Older revision		Revision as of 23:16, 25 May 2014
Line 152:		Line 152:
	\| rank of normalized Laplacian matrix \|\| 5 \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>m + n - 1 = 3 + 3 - 1 = 5</math>		\| rank of normalized Laplacian matrix \|\| 5 \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>m + n - 1 = 3 + 3 - 1 = 5</math>
	\|-		\|-
	\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), 2 (1 time), 1 (4 times) \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (1 time), <math>(m + n)/\sqrt{mn} = 3</math> (1 time), 1 (<math>m + n- 2 = 2 + 2 - 2 = 2</math> times)		\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), 2 (1 time), 1 (4 times) \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (1 time), <math>(m + n)/\sqrt{mn} = 3</math> (1 time), 1 (<math>m + n- 2 = 3 + 3 - 2 = 2</math> times)
	\|}		\|}

Vipul: /* Normalized Laplacian matrix */

2014-05-25T23:15:27Z

Normalized Laplacian matrix

← Older revision		Revision as of 23:15, 25 May 2014
Line 148:		Line 148:
	\| characteristic polynomial \|\| <math>t(t - 2)(t - 1)^4</math>\|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>t(t - (m + n)/\sqrt{mn})(t - \sqrt{m/n})^{n-1}(t-\sqrt{n/m})^{m-1}</math>		\| characteristic polynomial \|\| <math>t(t - 2)(t - 1)^4</math>\|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>t(t - (m + n)/\sqrt{mn})(t - \sqrt{m/n})^{n-1}(t-\sqrt{n/m})^{m-1}</math>
	\|-		\|-
	\| minimal polynomial \|\| <math>t(t - 1)(t - 2)</math> \|\| As complete bipartite graph <math>K_{m,m}, m = 3</math>: <math>t(t - 1)(t - 2)</math>		\| minimal polynomial \|\| <math>t(t - 1)(t - 2)</math> \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>t(t - 1)(t - (m + n)/\sqrt{mn}) = t(t - 1)(t - 2)</math>
	\|-		\|-
	\| rank of normalized Laplacian matrix \|\| 5 \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>m + n - 1 = 3 + 3 - 1 = 5</math>		\| rank of normalized Laplacian matrix \|\| 5 \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>m + n - 1 = 3 + 3 - 1 = 5</math>
	\|-		\|-
	\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), 2 (1 time), 1 (4 times) \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (1 time), <math>(m + n)/\sqrt{mn} = 2</math> (1 time), 1 (~~4 times:~~ <math>n - 1 = 3 - ~~1 =~~ 2~~</math> times as <math>\sqrt{m/n}</math> and <math>m - 1 = 3 - 1~~ = 2</math> times ~~as <math>\sqrt{n/m}</math>~~)		\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), 2 (1 time), 1 (4 times) \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (1 time), <math>(m + n)/\sqrt{mn} = 3</math> (1 time), 1 (<math>m + n- 2 = 2 + 2 - 2 = 2</math> times)
	\|}		\|}

Vipul: /* Normalized Laplacian matrix */

2014-05-25T22:45:59Z

Normalized Laplacian matrix

← Older revision		Revision as of 22:45, 25 May 2014
Line 148:		Line 148:
	\| characteristic polynomial \|\| <math>t(t - 2)(t - 1)^4</math>\|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>t(t - (m + n)/\sqrt{mn})(t - \sqrt{m/n})^{n-1}(t-\sqrt{n/m})^{m-1}</math>		\| characteristic polynomial \|\| <math>t(t - 2)(t - 1)^4</math>\|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>t(t - (m + n)/\sqrt{mn})(t - \sqrt{m/n})^{n-1}(t-\sqrt{n/m})^{m-1}</math>
	\|-		\|-
	\| minimal polynomial \|\| <math>t(t - 2)(t - 1)</math> \|\| As complete bipartite graph <math>K_{m,m}, m = 3</math>: <math>t(t - 2)(t - 1)</math>		\| minimal polynomial \|\| <math>t(t - 1)(t - 2)</math> \|\| As complete bipartite graph <math>K_{m,m}, m = 3</math>: <math>t(t - 1)(t - 2)</math>
	\|-		\|-
	\| rank of normalized Laplacian matrix \|\| 5 \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>m + n - 1 = 3 + 3 - 1 = 5</math>		\| rank of normalized Laplacian matrix \|\| 5 \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>m + n - 1 = 3 + 3 - 1 = 5</math>
	\|-		\|-
	\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), 2 (1 time), 1 (4 times) \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (1 time), <math>(m + n)/\sqrt{mn} = 2</math> (1 time), ~~<math>m = n =~~ 1~~</math>~~ (4 times: <math>n - 1 = 3 - 1 = 2</math> times as <math>\sqrt{m/n}</math> and <math>m - 1 = 3 - 1 = 2</math> times as <math>\sqrt{n/m}</math>)		\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), 2 (1 time), 1 (4 times) \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (1 time), <math>(m + n)/\sqrt{mn} = 2</math> (1 time), 1 (4 times: <math>n - 1 = 3 - 1 = 2</math> times as <math>\sqrt{m/n}</math> and <math>m - 1 = 3 - 1 = 2</math> times as <math>\sqrt{n/m}</math>)
	\|}		\|}

Vipul: /* Algebraic theory */

2014-05-25T22:42:13Z

Algebraic theory

← Older revision		Revision as of 22:42, 25 May 2014
Line 128:		Line 128:
	\| characteristic polynomial \|\| <math>t(t - 6)(t - 3)^4</math>\|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>t(t - (m + n))(t - m)^{n-1}(t-n)^{m-1}</math>		\| characteristic polynomial \|\| <math>t(t - 6)(t - 3)^4</math>\|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>t(t - (m + n))(t - m)^{n-1}(t-n)^{m-1}</math>
	\|-		\|-
	\| minimal polynomial \|\| <math>t(t - 6)(t - 3)</math> \|\| As complete bipartite graph <math>K_{m,m}, m = 3</math>: <math>t(t - m)(t - 2m)</math>		\| minimal polynomial \|\| <math>t(t - 3)(t - 6)</math> \|\| As complete bipartite graph <math>K_{m,m}, m = 3</math>: <math>t(t - m)(t - 2m)</math>
	\|-		\|-
	\| rank of Laplacian matrix \|\| 5 \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>m + n - 1 = 3 + 3 - 1 = 5</math>		\| rank of Laplacian matrix \|\| 5 \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>m + n - 1 = 3 + 3 - 1 = 5</math>

Vipul: /* Algebraic theory */

2014-05-25T22:37:31Z

Algebraic theory

@@ Line 132: / Line 132: @@
 | rank of Laplacian matrix || 5 || As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>m + n - 1 = 3 + 3 - 1 = 5</math>
 |-
-| eigenvalues (roots of characteristic polynomial) || 0 (1 time), 6 (1 time), 3 (4 times) || As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (1 time), <math>m + n = 6</math> (1 time), <math>m = n = 3</math> (<matH>n - 1 = 3 - 1 = 2</math> times as <math>m</math> and <math>m - 1 = 3 - 1 = 2</math> times as <math>n</math>)
+| eigenvalues (roots of characteristic polynomial) || 0 (1 time), 6 (1 time), 3 (4 times) || As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (1 time), <math>m + n = 6</math> (1 time), <math>m = n = 3</math> (4 times: <matH>n - 1 = 3 - 1 = 2</math> times as <math>m</math> and <math>m - 1 = 3 - 1 = 2</math> times as <math>n</math>)
 |}
@@ Line 139: / Line 139: @@
 The [[normalized Laplacian matrix]] is as follows:
-<math>\begin{pmatrix} 1 & 0 & 0 & -1/3 & -1/3 & -1/3 \\0 & 1 & 0 & -1 & -1 & -1 \\0 & 0 & 1 & -1/3 & -1/3 & -1/3 \\ -1/3 & -1/3 & -1/3 & 1 & 0 & 0 \\ -1/3 & -1/3 & -1/3 & 0 & 1 & 0 \\-1/3 & -1/3 & -1/3 & 0 & 0 & 1 \\\end{pmatrix}</math>
+<math>\begin{pmatrix} 1 & 0 & 0 & -1/3 & -1/3 & -1/3 \\0 & 1 & 0 & -1/3 & -1/3 & -1/3 \\0 & 0 & 1 & -1/3 & -1/3 & -1/3 \\ -1/3 & -1/3 & -1/3 & 1 & 0 & 0 \\ -1/3 & -1/3 & -1/3 & 0 & 1 & 0 \\-1/3 & -1/3 & -1/3 & 0 & 0 & 1 \\\end{pmatrix}</math>