Star: Difference between revisions

Latest revision as of 00:33, 26 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.

Arithmetic functions

Size measures

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

Numerical invariants

Function	Value	Explanation
clique number	2	As $K_{m,n},m=1,n=k$ : 2 (independent of $m,n$ , follows from being bipartite)
independence number	$k$	As $K_{m,n},m=1,n=k$ : $\max\{m,n\}=\max\{1,k\}=k$
chromatic number	2	As $K_{m,n},m=1,n=k$ : 2 (independent of $m,n$ , follows from being bipartite)
radius of a graph	1	The center vertex is adjacent to every other vertex
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

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)

Normalized Laplacian matrix

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_{k\times k}\\\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-2)(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-2)$ If $k=1$ : $t(t-2)$
rank of normalized Laplacian matrix	$k$
eigenvalues (roots of characteristic polynomial)	0 (1 time), 2 (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.
+==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==
+{| 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) ||
+|}
+===Normalized Laplacian matrix===
+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_{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:
+{| class="sortable" border="1"
+! Algebraic invariant !! Value !! Explanation
+|-
+| 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 - 2)</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), 2 (1 time), 1 (<math>k - 1</math> times) ||
+|}