Star: Difference between revisions

Revision as of 23:52, 25 May 2014

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$ edges (and therefore, $k+1$ vertices) is a graph where one of the $k+1$ vertices is adjacent to all other $k$ 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 $k\geq 2$ .

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

Explicit descriptions

Adjacency matrix

If we order the vertices such that the center of the star is the first vertex, the adjacency matrix has the form:

${\begin{pmatrix}0_{1\times 1}&E_{1\times k}\\E_{k\times 1}&0_{k\times k}\\\end{pmatrix}}$

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

Particular cases

Value of $k$	Description of graph
1	single edge graph (note that this is the only case where either vertex can be identified as the center).
2	path graph of length two
3	claw

Algebraic theory

Adjacency matrix

If we order the vertices such that the center of the star is the first vertex, the adjacency matrix has the form:

${\begin{pmatrix}0_{1\times 1}&E_{1\times k}\\E_{k\times 1}&0_{k\times k}\\\end{pmatrix}}$

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

Algebraic invariant	Value	Explanation
characteristic polynomial	$t^{k+1}-kt^{k-1}$
minimal polynomial	if $k>1$ : $t^{3}-kt$ if $k=1$ : $t^{2}-k$
rank of adjacency matrix	2
eigenvalues (roots of characteristic polynomial)	0 (multiplicity $k-1$ ), ${\sqrt {k}}$ (multiplicity 1), $-{\sqrt {k}}$ (multiplicity 1)

Laplacian matrix

The Laplacian matrix, defined as the matrix difference of the degree matrix and adjacency matrix, looks as follows:

${\begin{pmatrix}k&-E_{1\times k}\\-E_{k\times 1}&I_{k\times k}\\\end{pmatrix}}$

Here, $I$ denotes the identity matrix of the given (square) dimensions, and $E$ denotes the matrix with all entries one.

We can thus compute various algebraic invariants:

Algebraic invariant	Value	Explanation
characteristic polynomial	$t(t-(k+1))(t-1)^{k-1}$
minimal polynomial	If $m\neq n$ : $t(t-1)(t-(k+1))$ If $m=n$ : $t(t-m)(t-2m)$
rank of Laplacian matrix	$k$
eigenvalues (roots of characteristic polynomial)	0 (1 time), $k+1$ (1 time), 1 ( $k-1$ times)

The normalized Laplacian matrix is as follows:

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

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

Algebraic invariant	Value	Explanation
characteristic polynomial	$t(t-(k+1)/{\sqrt {k}})(t-1)^{k-1}$ Note that when $k=1$ , this simplifies to $t(t-2)(t-1)$
minimal polynomial	If $k>1$ : $t(t-1)(t-(k+1)/{\sqrt {k}})$ If $k=1$ : $t(t-2)$
rank of normalized Laplacian matrix	$k$
eigenvalues (roots of characteristic polynomial)	0 (1 time), $(k+1)/{\sqrt {k}}$ (1 time), 1 ( $k-1$ times)

@@ 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>.
+==Explicit descriptions==
+===Adjacency matrix===
+If we order the vertices such that the center of the star is the first vertex, the adjacency matrix has the form:
+<math>\begin{pmatrix} 0_{1 \times 1} & E_{1 \times k} \\ E_{k \times 1} & 0_{k \times k} \\\end{pmatrix}</math>
+where <math>E_{m \times n}</math> denotes a <math>m \times n</math> matrix all of whose entries are equal to 1.
+==Particular cases==
+{| class="sortable" border="1"
+! Value of <math>k</math> !! Description of graph
+|-
+| 1 || single edge graph (note that this is the only case where either vertex can be identified as the center).
+|-
+| 2 || path graph of length two
+|-
+| 3 || [[claw]]
+|}
+==Algebraic theory==
+===Adjacency matrix===
+If we order the vertices such that the center of the star is the first vertex, the adjacency matrix has the form:
+<math>\begin{pmatrix} 0_{1 \times 1} & E_{1 \times k} \\ E_{k \times 1} & 0_{k \times k} \\\end{pmatrix}</math>
+where <math>E_{m \times n}</math> denotes a <math>m \times n</math> matrix all of whose entries are equal to 1.
+{| class="sortable" border="1"
+! Algebraic invariant !! Value !! Explanation
+|-
+| [[characteristic polynomial of a graph|characteristic polynomial]] || <math>t^{k + 1} - kt^{k - 1}</math>
+|-
+| [[minimal polynomial of a matrix|minimal polynomial]] || if <math>k > 1</math>: <math>t^3 - kt</math><br>if <math>k = 1</math>: <math>t^2 - k</math> ||
+|-
+| rank of adjacency matrix || 2 ||
+|-
+| eigenvalues (roots of characteristic polynomial) || 0 (multiplicity <math>k - 1</math>), <math>\sqrt{k}</math> (multiplicity 1), <math>-\sqrt{k}</math> (multiplicity 1) ||
+|}
+===Laplacian matrix===
+The [[Laplacian matrix]], defined as the matrix difference of the [[degree matrix]] and [[adjacency matrix]], looks as follows:
+<math>\begin{pmatrix} k & -E_{1 \times k} \\ -E_{k \times 1} & I_{k \times k} \\\end{pmatrix}</math>
+Here, <math>I</math> denotes the [[linear:identity matrix|identity matrix]] of the given (square) dimensions, and <math>E</math> denotes the matrix with all entries one.
+We can thus compute various algebraic invariants:
+{| class="sortable" border="1"
+! Algebraic invariant !! Value !! Explanation
+|-
+| characteristic polynomial || <math>t(t - (k + 1))(t - 1)^{k-1}</math> ||
+|-
+| minimal polynomial || If <math>m \ne n</math>: <math>t(t - 1)(t - (k + 1))</math><br>If <math>m = n</math>: <math>t(t - m)(t - 2m)</math> ||
+|-
+| rank of Laplacian matrix || <math>k</math> ||
+|-
+| eigenvalues (roots of characteristic polynomial) || 0 (1 time), <math>k + 1</math> (1 time), 1 (<math>k - 1</math> times) ||
+|}
+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>
+The matrix is uniquely defined up to permutation by conjugations. Below are some algebraic invariants associated with the matrix:
+{| class="sortable" border="1"
+! 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> ||
+|-
+| 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> ||
+|-
+| 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) ||
+|}