Star - Revision history

Vipul: /* Explicit descriptions */

2014-05-26T00:33:00Z

Explicit descriptions

← Older revision		Revision as of 00:33, 26 May 2014
Line 14:		Line 14:

	where <math>E_{m \times n}</math> denotes a <math>m \times n</math> matrix all of whose entries are equal to 1.		where <math>E_{m \times n}</math> denotes a <math>m \times n</math> matrix all of whose entries are equal to 1.

			==Arithmetic functions==

			===Size measures===

			{\| class="sortable" border="1"
			! Function !! Value !! Explanation
			\|-
			\| [[size of vertex set]] \|\| <math>k + 1</math> \|\| As <math>K_{m,n}, m = 1, n = k</math>: <math>m + n = 1 + k = k + 1</math>
			\|-
			\| [[size of edge set]] \|\| <math>k</math> \|\| As <math>K_{m,n}, m = 1, n = k</math>: <math>mn = (1)(k) = k</math>
			\|}

			===Numerical invariants===

			{\| class="sortable" border="1"
			! Function !! Value !! Explanation
			\|-
			\| {{arithmetic function value\|clique number\|2}} \|\| As <math>K_{m,n}, m = 1, n = k</math>: 2 (independent of <math>m,n</math>, follows from being bipartite)
			\|-
			\| [[independence number]] \|\| <math>k</math> \|\| As <math>K_{m,n}, m = 1, n = k</math>: <math>\max \{ m,n \} = \max \{ 1,k \} = k</math>
			\|-
			\| {{arithmetic function value\|chromatic number\|2}} \|\| As <math>K_{m,n}, m = 1, n = k</math>: 2 (independent of <math>m,n</math>, follows from being bipartite)
			\|-
			\| {{arithmetic function value\|radius of a graph\|1}} \|\| The center vertex is adjacent to every other vertex
			\|-
			\| {{arithmetic function value\|diameter of a graph\|2}} \|\| Any two vertices are either adjacent or have a path of length two between them via the center
			\|-
			\| [[odd girth]] \|\| infinite \|\| there are no cycles
			\|-
			\| [[even girth]] \|\| infinite \|\| there are no cycles
			\|-
			\| [[girth of a graph]] \|\| infinite \|\| there are no cycles
			\|}

	==Particular cases==		==Particular cases==

Vipul: /* Normalized Laplacian matrix */

2014-05-26T00:12:23Z

Normalized Laplacian matrix

← Older revision		Revision as of 00:12, 26 May 2014
Line 82:		Line 82:
	! Algebraic invariant !! Value !! Explanation		! Algebraic invariant !! Value !! Explanation
	\|-		\|-
	\| characteristic polynomial \|\| <math>t(t - ~~(k + 1)/\sqrt{k}~~)(t - 1)^{k-1}</math><br>Note that when <math>k = 1</math>, this simplifies to <math>t(t - 2)(t - 1)</math> \|\|		\| characteristic polynomial \|\| <math>t(t - 2)(t - 1)^{k-1}</math><br>Note that when <math>k = 1</math>, this simplifies to <math>t(t - 2)(t - 1)</math> \|\|
	\|-		\|-
	\| minimal polynomial \|\| If <math>k > 1</math>: <math>t(t - 1)(t - ~~(k + 1)/\sqrt{k}~~)</math><br>If <math>k = 1</math>: <math>t(t - 2)</math> \|\|		\| minimal polynomial \|\| If <math>k > 1</math>: <math>t(t - 1)(t - 2)</math><br>If <math>k = 1</math>: <math>t(t - 2)</math> \|\|
	\|-		\|-
	\| rank of normalized Laplacian matrix \|\| <math>k</math> \|\|		\| rank of normalized Laplacian matrix \|\| <math>k</math> \|\|
	\|-		\|-
	\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), ~~<math>(k + 1)/\sqrt{k}</math>~~ (1 time), 1 (<math>k - 1</math> times) \|\|		\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), 2 (1 time), 1 (<math>k - 1</math> times) \|\|
	\|}		\|}

Vipul: /* Normalized Laplacian matrix */

2014-05-26T00:01:31Z

Normalized Laplacian matrix

← Older revision		Revision as of 00:01, 26 May 2014
Line 75:		Line 75:
	The [[normalized Laplacian matrix]] is as follows:		The [[normalized Laplacian matrix]] is as follows:

	<math>\begin{pmatrix} 1 & (-1/\sqrt{k}) E_{1 \times k} \\ (-1/\sqrt{k}) E_{k \times 1} & I_{n \times n} \\\end{pmatrix}</math>		<math>\begin{pmatrix} 1 & (-1/\sqrt{k}) E_{1 \times k} \\ (-1/\sqrt{k}) E_{k \times 1} & I_{k \times k} \\\end{pmatrix}</math>

	The matrix is uniquely defined up to permutation by conjugations. Below are some algebraic invariants associated with the matrix:		The matrix is uniquely defined up to permutation by conjugations. Below are some algebraic invariants associated with the matrix:

Vipul: /* Laplacian matrix */

2014-05-25T23:58:59Z

Laplacian matrix

← Older revision		Revision as of 23:58, 25 May 2014
Line 70:		Line 70:
	\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), <math>k + 1</math> (1 time), 1 (<math>k - 1</math> times) \|\|		\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), <math>k + 1</math> (1 time), 1 (<math>k - 1</math> times) \|\|
	\|}		\|}

			===Normalized Laplacian matrix===

	The [[normalized Laplacian matrix]] is as follows:		The [[normalized Laplacian matrix]] is as follows:

Vipul at 23:52, 25 May 2014

2014-05-25T23:52:24Z

@@ Line 1: / Line 1: @@
 ==Definition==
-A '''star''' is a graph where one vertex is adjacent to all the other vertices, and that vertex is incident on every edge. Explicitly, a star with <math>k</math> edges (and therefore, <math>k + 1</math> vertices) is a graph where one of the <math>k + 1</math> vertices is adjacent to all other <math>k</math> vertices, and there are no edges other than the edges involving that vertex.
+A '''star''' is a graph where one vertex is adjacent to all the other vertices, and that vertex is incident on every edge. Explicitly, a star with <math>k</math> edges (and therefore, <math>k + 1</math> vertices) is a graph where one of the <math>k + 1</math> vertices is adjacent to all other <math>k</math> vertices, and there are no edges other than the edges involving that vertex. The vertex that is adjacent to all other vertices is termed the ''center'' of the star (note that this agrees with the usual definition of [[central vertex]]. The center is uniquely defined for <math>k \ge 2</math>.
 A star can also be described as a [[complete bipartite graph]] where one of the parts has size one. Explicitly, a star with <math>k</math> edges can be described as the complete bipartite graph <math>K_{1,k}</math>.

Vipul: Created page with "==Definition== A '''star''' is a graph where one vertex is adjacent to all the other vertices, and that vertex is incident on every edge. Explicitly, a star with $k$
2014-05-25T23:23:47Z

Created page with "==Definition== A '''star''' is a graph where one vertex is adjacent to all the other vertices, and that vertex is incident on every edge. Explicitly, a star with <math>k</mat..."

New page
==Definition==

A '''star''' is a graph where one vertex is adjacent to all the other vertices, and that vertex is incident on every edge. Explicitly, a star with <math>k</math> edges (and therefore, <math>k + 1</math> vertices) is a graph where one of the <math>k + 1</math> vertices is adjacent to all other <math>k</math> vertices, and there are no edges other than the edges involving that vertex.

A star can also be described as a [[complete bipartite graph]] where one of the parts has size one. Explicitly, a star with <math>k</math> edges can be described as the complete bipartite graph <math>K_{1,k}</math>.