File:Site search autocompletion working.png

2024-08-24T05:18:22Z

Vipul:

File:Site search autocompletion broken.png

2024-08-24T05:17:55Z

Vipul:

Graph:Enabling site search autocompletion

2024-08-24T05:11:49Z

Vipul: Created page with "Content copied from Ref:Ref:Enabling site search autocompletion. Images used are specific to this site (Graph). Site search autocompletion is currently broken by default on this site. This page includes details on how to get it to work, and what's going on. ==What's wrong with site search autocompletion and how to fix it== ===What's wrong=== When you start typing something in the site search bar, you'll see it stuck at "Loading search suggestions" as shown in the..."

Content copied from [[Ref:Ref:Enabling site search autocompletion]]. Images used are specific to this site (Graph).

Site search autocompletion is currently broken by default on this site. This page includes details on how to get it to work, and what's going on.

==What's wrong with site search autocompletion and how to fix it==

===What's wrong===

When you start typing something in the site search bar, you'll see it stuck at "Loading search suggestions" as shown in the screenshot below:

[[File:Site search autocompletion broken.png]]

Note that the actual search is still working -- you just have to hit Enter after typing the search query and it'll go to the search results page. It's the autocompletion before you hit Enter that is broken.

===How to fix it===

To fix it, you need to follow these steps:

* Write to vipulnaik1@gmail.com asking for a login to the site. Please include the following with your request: preferred username, preferred initial password (you can change it after logging in), real name (if you want it entered), email address to use (if you want an actual email address by which you can be contacted), and whether you want edit access as well. You don't need edit access for enabling site search autocompletion.
* Log in to the site. Then go to [[Special:Preferences]]. Go to the Appearance section and switch the Skin from "Vector (2022)" to "Vector legacy (2010)".
* Make sure to hit "Save" at the bottom.
* Now you can reload the page or load a new page.

Site search autocompletion should now work. Here's an example:

[[File:Site search autocompletion working.png]]

==More background==

We've recently upgraded the MediaWiki version of this wiki from 1.35.13 to 1.41.2 (see [[Special:Version]]). The upgrade allows us to migrate the wiki to a more modern operating system version running PHP 8. With the current setup for MediaWiki 1.41.2, we're in this situation:

* The "Vector legacy (2010)" skin has site search autocompletion working, but it doesn't render well on small screens. Specifically, even on small mobile screens, it still shows the left menu, and doesn't properly use the MobileFrontend extension settings.
* The "Vector (2022)" skin doesn't have site search autocompletion working (see screenshots in preceding section) but it does render fine on mobile devices.

It is possible to set only one default skin (that is applicable to all non-logged-in users and is the default for logged-in users who have not configured a skin for themselves). So, the selection of default skin comes down to whether it's more important for casual users to have the mobile experience working or to have site search autocompletion working. Based on a general understanding of user behavior, we believe that having a usable mobile experience is more important for casual users than having site search autocompletion.

However, for power users who are using the site extensively, site search autocompletion may be important. That's why we've written this page giving guidance on how to set up site search autocompletion.

Graph:429 Too Many Requests error

2024-08-24T05:10:48Z

Vipul: Created page with "If you get a 429 Too Many Requests error when browsing this site, read on. You're probably seeing this error because a large number of requests have been made from your IP address over a short period of time. That's probably a lot of requests from you or others who share your IP address (such as your home wi-fi network). Waiting a minute and then retrying should generally work. If you are an actual human being with a legitimate reason to be browsing the site heavily, f..."

If you get a 429 Too Many Requests error when browsing this site, read on.

You're probably seeing this error because a large number of requests have been made from your IP address over a short period of time. That's probably a lot of requests from you or others who share your IP address (such as your home wi-fi network). Waiting a minute and then retrying should generally work.

If you are an actual human being with a legitimate reason to be browsing the site heavily, first, thank you and sorry about this! We set rate limits to prevent bots, spiders, spammers, and malicious actors from consuming too much of our server's resources so that our server's resources can be devoted to real humans like you. Consider writing to vipulnaik1@gmail.com with your IP address to have the IP address whitelisted. You can get your IP address by [https://www.google.com/search?q=my+ip+address Googling "my IP address"] (scroll down a little bit to where Google includes the IP address in a box). NOTE: If you have both an IPv4 address and an IPv6 address, you should send both; the server supports both IPv4 and IPv6, so either may end up getting used. To check if you have an IPv6 address, try visiting [https://ipv6.google.com/ ipv6.google.com].

If your IP address changes, or you are away from your home network, then you'll get rate-limited again. So if you find yourself getting rate-limited after already having been whitelisted, check if you are on a different IP address than the one for which you requested whitelisting.

2024-07-21T05:03:12Z

Vipul: Created page with "<math>\sqrt{7 + 2}!! + 3 = 723</math>"

Laplacian matrix

2014-05-26T01:30:54Z

Vipul:

==Definition==

Suppose <math>G</math> is a [[finite graph|finite]] [[undirected graph]]. Let <math>n</math> be the size of the vertex set <math>V(G)</math>. Fix a bijective correspondence <math>v:\{ 1,2,\dots,n\} \to V(G)</math>. The '''Laplacian matrix''' of <math>G</math> is a <math>n \times n</math> [[linear:square matrix|square matrix]] defined in the following equivalent ways:

# It is the matrix difference <math>D - A</math> where <math>D</math> is the [[defining ingredient::degree matrix]] of <math>G</math> and <math>A</math> is the [[defining ingredient::adjacency matrix]] of <math>G</math>, both for the same vertex mapping <math>v</math>.
# It is the product <math>M^TM</math> where <math>M</math> is an ''oriented'' [[incidence matrix]] of <math>G</math> (where the vertices are ordered by the function <math>v</math>) and <math>M^T</math> is the [[linear:matrix transpose|matrix transpose]] of <math>M</math>.
# It is a matrix defined as follows:
#* For <math>1 \le i \le n</math>, the <math>(i,i)^{th}</math> entry equals the [[degree of a vertex|degree]] of vertex <math>v(i)</math>.
#* For <math>1 \le i,j \le n</math> with <math>i \ne j</math>, the <math>(i,j)^{th}</math> entry is -1 if <math>v(i)</math> and <math>v(j)</math> are adjacent, and 0 otherwise.

Other names for the Laplacian matrix are '''graph Laplacian''', '''admittance matrix''', '''Kirchhoff matrix''', and '''discrete Laplacian'''.

==Properties==

* The Laplacian matrix of a graph is always a [[linear:symmetric positive-semidefinite matrix|symmetric positive-definite matrix]] (this can easily be seen from version (2) of the definition).
* The Laplacian matrix is a [[linear:diagonally dominant matrix|diagonally dominant matrix]]: the magnitude of the diagonal entry is greater than or equal to the sum of the magnitudes of the off-diagonal entries in its row. In this case, in fact, exact equality holds for every row.
* The Laplacian matrix has determinant zero, i.e., it is non-invertible. More specifically, its kernel contains the vector with all coordinates one, and is therefore at least one-dimensional. Moreover, the dimension of the kernel equals the number of [[connected component]]s of the graph, and an explicit basis for the kernel is as follows: for each connected component, the corresponding basis vector is the sum of the standard basis vectors for the vertices in that component. In particular, if the whole graph is connected, the kernel is one-dimensional, the nullity is one, and the rank is <math>n - 1</math>.

Star

2014-05-26T00:33:00Z

Vipul: /* Explicit descriptions */

==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. 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> 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> 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> 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> 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) ||
|}

Complete bipartite graph:K3,3

2014-05-26T00:31:06Z

Vipul: /* Arithmetic functions */

{{particular undirected graph}}

==Definition==

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==

===Descriptions of vertex set and edge set===

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

Vertex set: <math>\{ 1,2,3,4,5,6 \}</math>

Edge set: <math>\{ \{ 1,4 \}, \{ 1,5 \}, \{ 1,6 \}, \{ 2,4 \}, \{ 2,5 \}, \{ 2,6 \}, \{ 3,4 \}, \{ 3,5 \}, \{ 3, 6 \} \}</math>

===Adjacency matrix===

With the above ordering of the vertices, the adjacency matrix is as follows:

<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>: 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|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 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)
|}

==Graph properties==

{| class="sortable" border="1"
! Property !! Satisfied? !! Explanation
|-
| [[satisfies property::connected graph]] || Yes ||
|-
| [[satisfies property::regular graph]] || Yes || <math>K_{m,n}</math> is regular if <math>m = n</math>
|-
| [[satisfies property::vertex-transitive graph]] || Yes || <math>K_{m,n}</math> is vertex-transitive if <math>m = n</math>
|-
| [[satisfies property::cubic graph]] || Yes ||
|-
| [[satisfies property::edge-transitive graph]] || Yes ||
|-
| [[satisfies property::symmetric graph]] || Yes ||
|-
| [[satisfies property::distance-transitive graph]] || Yes ||
|-
| [[satisfies property::bridgeless graph]] || Yes ||
|-
| [[satisfies property::strongly regular graph]] || Yes || The graph is a <math>\operatorname{srg}(6,3,0,3)</math>. In general, a complete bipartite graph <math>K_{m,n}</math> is strongly regular iff <math>m = n</math>, and in that case it is a <math>\operatorname{srg}(2m,m,0,m)</math>
|-
| [[satisfies property::bipartite graph]] || Yes || By definition of complete bipartite graph
|}

==Algebraic theory==

===Adjacency matrix===

The adjacency matrix is as follows:

<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>

This matrix is uniquely defined up to conjugation by permutations. Below are some important associated algebraic invariants:

{| class="sortable" border="1"
! Algebraic invariant !! Value !! Explanation
|-
| [[characteristic polynomial of a graph|characteristic polynomial]] || <math>t^6 - 9t^4</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>t^{m + n} - mnt^{m + n - 2} = t^{3 + 3} - (3)(3)t^{3 + 3 - 2} = t^6 - 9t^4</math>
|-
| [[minimal polynomial of a graph|minimal polynomial]] || <math>t^3 - 9t</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>t^3 - mnt = t^3 - (3)(3)t = t^3 - 9t</math>
|-
| rank of adjacency matrix || 2 || As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 2 (independent of <math>m,n</math>)
|-
| eigenvalues (roots of characteristic polynomial) || 0 (4 times), 3 (1 time), -3 (1 time)|| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (<math>m + n - 2 = 3 + 3 - 2 = 4</math> times), <math>\sqrt{mn} = \sqrt{(3)(3)} = 3</math> (1 time), <math>-\sqrt{mn} = -\sqrt{(3)(3)} = -3</math> (1 time)
|}

===Laplacian matrix===

The [[Laplacian matrix]] is as follows:

<math>\begin{pmatrix} 3 & 0 & 0 & -1 & -1 & -1 \\0 & 3 & 0 & -1 & -1 & -1 \\0 & 0 & 3 & -1 & -1 & -1 \\ -1 & -1 & -1 & 3 & 0 & 0 \\ -1 & -1 & -1 & 0 & 3 & 0 \\-1 & -1 & -1 & 0 & 0 & 3 \\\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 - 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 - 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>
|-
| 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>)
|}

===Normalized Laplacian matrix===

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

<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>

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)^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>)
|-
| 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 = 4</math> times)
|}

Square graph

2014-05-26T00:20:38Z

Vipul: /* Normalized Laplacian matrix */

{{particular undirected graph}}

==Definition==

This [[undirected graph]], called the '''square graph''', is defined in the following equivalent ways:

# It is the [[cycle graph]] on 4 vertices, denoted <math>C_4</math>.
# It is the [[complete bipartite graph]] <math>K_{2,2}</math>
# It is the 2-dimensional [[hypercube graph]].
# It is the 2-dimensional [[hyperoctahedron graph]].
==Explicit descriptions==

===Description of vertex set and edge set===

Vertex set: <math>\{ 1,2,3,4\}</math>

Edge set: <math>\{ \{ 1,2 \} , \{ 2,3 \} , \{ 3, 4 \} , \{ 1, 4 \} \}</math>

Note that with this description, the two parts in a bipartite graph description are <math>\{ 1,3 \}</math> and <math>\{ 2,4 \}</math>.

===Adjacency matrix===

With the ordering of the vertex set and edge set given above, the adjacency matrix is:

<math>\begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\\end{pmatrix}</math>

If we re-ordered the vertices by interchanging the roles of vertices 2 and 3, we would get the following adjacency matrix:

<math>\begin{pmatrix} 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\\end{pmatrix}</math>

==Arithmetic functions==

===Size measures===

{| class="sortable" border="1"
! Function !! Value !! Explanation
|-
| {{arithmetic function value|size of vertex set|4}} || As cycle graph <math>C_n, n = 4</math>: <math>n = 4</math> As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>m + n = 2 + 2 = 4</math> As <math>n</math>-dimensional hypercube, <math>n = 2</math>: <math>2^n = 2^2 = 4</math>
|-
| {{arithmetic function value|size of edge set|4}} || As cycle graph <math>C_n, n = 4</math>: <math>n = 4</math> As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>mn = 2(2) = 4</math> As <math>n</math>-dimensional hypercube, <math>n = 2</math>: <math>n \cdot 2^{n-1} = 2 \cdot 2^{2-1} = 4</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|2}} || As cycle graph <math>C_n, n = 4</math>: 2 (independent of <math>n</math>) As complete bipartite graph <math>K_{m,n}, m = n = 2</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 = 2</math> As <math>n</math>-dimensional hypercube, <math>n = 2</math>: <math>n = 2</math> As <math>n</math>-dimensional hyperoctahedron, <math>n = 2</math>: <math>2n - 2 = 2(2) - 2 = 2</math>
|-
| {{arithmetic function value|eccentricity of a vertex|2}} || As cycle graph <math>C_n, n = 4</math>: greatest integer of <math>n/2</math> equals greater integer of 4/2 equals 2 As complete bipartite graph <math>K_{m,n}, m= n = 2</math>: 2 (independent of <math>m,n</math>, though it uses that both numbers are greater than 1) As <math>n</math>-dimensional hypercube, <math>n = 2</math>: <math>n = 2</math> As <math>n</math>-dimensional hyperoctahedron, <math>n = 2</math>: 2 (independent of <math>n</math>, for <math>n \ge 2</math>)
|}

===Other numerical invariants===

{| class="sortable" border="1"
! Function !! Value !! Explanation
|-
| {{arithmetic function value|clique number|2}} || As [[cycle graph]] <math>C_n, n = 4</math>: 2 (independent of <math>n</math> for <math>n \ge 4</math>) As <math>K_{m,n}, m = n = 2</math>: 2 (independent of <math>m,n</math>, follows from being bipartite) As <math>n</math>-dimensional hypercube, <math>n = 2</math>: 2 (independent of <math>n</math>)
|-
| {{arithmetic function value|independence number|2}} || As [[cycle graph]] <math>C_n, n = 4</math>: greatest integer of <math>n/2</math> equals greatest integer of 4/2 equals 2 As <math>K_{m,n}, m = n = 2</math>: <math>\max \{ m,n \} = \max \{ 2,2 \} = 2</math> As <math>n</math>-dimensional hypercube, <math>n = 2</math>: <math>2^{n-1} = 2^{2-1} = 2</math>
|-
| {{arithmetic function value|chromatic number|2}} || As [[cycle graph]] <math>C_n, n = 4</math>: 2 (in general, it is 2 for even <math>n</math> and 3 for odd <math>n</math> As <math>K_{m,n}, m = n = 2</math>: 2 (independent of <math>m,n</math>, follows from being bipartite) As <math>n</math>-dimensional hypercube, <math>n = 2</math>: 2 (independent of <math>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 [[cycle graph]] <math>C_n, n = 4</math>: infinite (since <math>n</math> even) As <math>K_{m,n}, m = n = 2</math>: infinite, since bipartite As <math>n</math>-dimensional hypercube, <math>n = 2</math>: infinite, since bipartite
|-
| {{arithmetic function value|even girth|4}} || As [[cycle graph]] <math>C_n, n = 4</math>: <math>n = 4</math> (since <math>n</math> even) As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: 4 (independent of <math>m,n</math> as long as both are greater than 1) As <math>n</math>-dimensional hypercube, <math>n = 2</math>: 4 (independent of <math>n</math> for <math>n \ge 2</math>)
|-
| {{arithmetic function value|girth of a graph|4}} || As [[cycle graph]] <math>C_n, n = 4</math>: <math>n = 4</math> As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: 4 (independent of <math>m,n</math> as long as both are greater than 1) As <math>n</math>-dimensional hypercube, <math>n = 2</math>: 4 (independent of <math>n</math> for <math>n \ge 2</math>)
|}

==Graph properties==

{| class="sortable" border="1"
! Property !! Satisfied? !! Explanation
|-
| [[satisfies property::connected graph]] || Yes ||
|-
| [[satisfies property::regular graph]] || Yes || all vertices have degree two
|-
| [[satisfies property::vertex-transitive graph]] || Yes ||
|-
| [[dissatisfies property::cubic graph]] || No ||
|-
| [[satisfies property::edge-transitive graph]] || Yes ||
|-
| [[satisfies property::symmetric graph]] || Yes ||
|-
| [[satisfies property::distance-transitive graph]] || Yes ||
|-
| [[satisfies property::bridgeless graph]] || Yes ||
|-
| [[satisfies property::strongly regular graph]] || Yes || The graph is a <math>\operatorname{srg}(4,2,0,2)</math>
|-
| [[satisfies property::bipartite graph]] || Yes ||
|}

==Graph operations==

{| class="sortable" border="1"
! Operation !! Graph obtained as a result of the operation
|-
| [[complement of a graph]] || [[matching graph]] on 4 vertices
|-
| [[line graph]] || isomorphic to the original graph
|-
| [[prism of a graph]] || [[cube graph]]
|}

==Algebraic theory==

===Adjacency matrix===

The adjacency matrix is:

<math>\begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\\end{pmatrix}</math>

It can alternately be written in the following form, which is more computationally convenient because it clearly identifies blocks of 0s and 1s:

<math>\begin{pmatrix} 0 & 0 & 1 & 1 \\0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\1 & 1 & 0 & 0 \\\end{pmatrix}</math>

This matrix is uniquely defined up to conjugation by permutations. Below are some important associated algebraic invariants:

{| class="sortable" border="1"
! Algebraic invariant !! Value !! Explanation
|-
| [[characteristic polynomial of a graph|characteristic polynomial]] || <math>t^4 - 4t^2</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>t^{m + n} - mnt^{m + n - 2} = t^{2 + 2} - (2)(2)t^{2 + 2 - 2} = t^4 - 4t^2</math>
|-
| [[minimal polynomial of a graph|minimal polynomial]] || <math>t^3 - 4t</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>t^3 - mnt = t^3 - (2)(2)t = t^3 - 4t</math>
|-
| rank of adjacency matrix || 2 || As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: 2 (independent of <math>m,n</math>)
|-
| eigenvalues (roots of characteristic polynomial) || 0 (2 times), 2 (1 time), -2 (1 time)|| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: 0 (<math>m + n - 2 = 2 + 2 - 2 = 2</math> times), <math>\sqrt{mn} = \sqrt{(2)(2)} = 2</math> (1 time), <math>-\sqrt{mn} = -\sqrt{(2)(2)} = -2</math> (1 time)
|}

===Laplacian matrix===

The [[Laplacian matrix]] is as follows:

<math>\begin{pmatrix} 2 & 0 & -1 & -1 \\0 & 2 & -1 & -1 \\ -1 & -1 & 2 & 0 \\ -1 & -1 & 0 & 2 \\\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 - 4)(t - 2)^2</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>t(t - (m + n))(t - m)^{n-1}(t-n)^{m-1}</math>
|-
| minimal polynomial || <math>t(t - 2)(t - 4)</math> || As complete bipartite graph <math>K_{m,m}, m = 2</math>: <math>t(t - m)(t - 2m)</math>
|-
| rank of Laplacian matrix || 3 || As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>m + n - 1 = 2 + 2 - 1 = 3</math>
|-
| eigenvalues (roots of characteristic polynomial) || 0 (1 time), 4 (1 time), 2 (2 times) || As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (1 time), <math>m + n = 4</math> (1 time), <math>m = n = 2</math> (2 times: <math>n - 1 = 2 - 1 = 1</math> times as <math>m</math> and <math>m - 1 = 2 - 1 = 1</math> times as <math>m</math>)
|}

===Normalized Laplacian matrix===

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

<math>\begin{pmatrix} 1 & 0 & -1/2 & -1/2 \\0 & 1 & -1/2 & -1/2 \\ -1/2 & -1/2 & 1 & 0 \\ -1/2 & -1/2 & 0 & 1 \\\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)^2</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 2</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 = 2</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 || 3 || As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>m + n - 1 = 2 + 2 - 1 = 3</math>
|-
| eigenvalues (roots of characteristic polynomial) || 0 (1 time), 2 (1 time), 1 (2 times) || As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: 0 (1 time), 2 (1 time), 1 (<math>m + n - 2 = 2 + 2 - 2 = 2</math> times)
|}

==Realization==

===As Cayley graph===

Note that for this to be the Cayley graph of a group, the group must have order 4, and the generating set with respect to which we construct the Cayley graph must be a [[symmetric subset]] of the group of size 2.

{| class="sortable" border="1"
! Group !! Choice of [[groupprops:symmetric subset|symmetric set]] that is a [[groupprops:generating set|generating set]] for which the Cayley graph is this
|-
| [[groupprops:cyclic group:Z4|cyclic group:Z4]] || cyclic generator and its inverse
|-
| [[groupprops:Klein four-group|Klein four-group]] || two distinct elements of order two
|}

==Geometric embeddings==

===Planar embedding as a square===

The graph has a very nice embedding as a square in the plane: the vertices embed as the vertices of the square, and the edges as the edges of the square. Explicitly, we can embed the vertices as:

<math>1 \leftrightarrow (0,0), 2 \leftrightarrow (1,0), 3 \leftrightarrow (1,1), 4 \leftrightarrow (0,1)</math>

This embedding is nice in a number of ways:

* It demonstrates that the graph is a [[planar graph]].
* Moreover, it demonstrates that the graph can be embedded in the plane using straight line segments for edges. This is not possible for all planar graphs.
* It demonstrates that the graph is a [[unit distance graph]]: two points are adjacent in the embedding if and only if the distance between them in the Euclidean plane is 1.
* It preserves all the symmetries of the graph. Explicitly, for every automorphism of the cycle graph, there is a (unique) self-isometry of the Euclidean plane that induces that automorphism on the cycle graph.

Square graph

2014-05-26T00:18:50Z

Vipul: /* Normalized Laplacian matrix */

{{particular undirected graph}}

==Definition==

This [[undirected graph]], called the '''square graph''', is defined in the following equivalent ways:

# It is the [[cycle graph]] on 4 vertices, denoted <math>C_4</math>.
# It is the [[complete bipartite graph]] <math>K_{2,2}</math>
# It is the 2-dimensional [[hypercube graph]].
# It is the 2-dimensional [[hyperoctahedron graph]].
==Explicit descriptions==

===Description of vertex set and edge set===

Vertex set: <math>\{ 1,2,3,4\}</math>

Edge set: <math>\{ \{ 1,2 \} , \{ 2,3 \} , \{ 3, 4 \} , \{ 1, 4 \} \}</math>

Note that with this description, the two parts in a bipartite graph description are <math>\{ 1,3 \}</math> and <math>\{ 2,4 \}</math>.

===Adjacency matrix===

With the ordering of the vertex set and edge set given above, the adjacency matrix is:

<math>\begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\\end{pmatrix}</math>

If we re-ordered the vertices by interchanging the roles of vertices 2 and 3, we would get the following adjacency matrix:

<math>\begin{pmatrix} 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\\end{pmatrix}</math>

==Arithmetic functions==

===Size measures===

{| class="sortable" border="1"
! Function !! Value !! Explanation
|-
| {{arithmetic function value|size of vertex set|4}} || As cycle graph <math>C_n, n = 4</math>: <math>n = 4</math> As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>m + n = 2 + 2 = 4</math> As <math>n</math>-dimensional hypercube, <math>n = 2</math>: <math>2^n = 2^2 = 4</math>
|-
| {{arithmetic function value|size of edge set|4}} || As cycle graph <math>C_n, n = 4</math>: <math>n = 4</math> As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>mn = 2(2) = 4</math> As <math>n</math>-dimensional hypercube, <math>n = 2</math>: <math>n \cdot 2^{n-1} = 2 \cdot 2^{2-1} = 4</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|2}} || As cycle graph <math>C_n, n = 4</math>: 2 (independent of <math>n</math>) As complete bipartite graph <math>K_{m,n}, m = n = 2</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 = 2</math> As <math>n</math>-dimensional hypercube, <math>n = 2</math>: <math>n = 2</math> As <math>n</math>-dimensional hyperoctahedron, <math>n = 2</math>: <math>2n - 2 = 2(2) - 2 = 2</math>
|-
| {{arithmetic function value|eccentricity of a vertex|2}} || As cycle graph <math>C_n, n = 4</math>: greatest integer of <math>n/2</math> equals greater integer of 4/2 equals 2 As complete bipartite graph <math>K_{m,n}, m= n = 2</math>: 2 (independent of <math>m,n</math>, though it uses that both numbers are greater than 1) As <math>n</math>-dimensional hypercube, <math>n = 2</math>: <math>n = 2</math> As <math>n</math>-dimensional hyperoctahedron, <math>n = 2</math>: 2 (independent of <math>n</math>, for <math>n \ge 2</math>)
|}

===Other numerical invariants===

{| class="sortable" border="1"
! Function !! Value !! Explanation
|-
| {{arithmetic function value|clique number|2}} || As [[cycle graph]] <math>C_n, n = 4</math>: 2 (independent of <math>n</math> for <math>n \ge 4</math>) As <math>K_{m,n}, m = n = 2</math>: 2 (independent of <math>m,n</math>, follows from being bipartite) As <math>n</math>-dimensional hypercube, <math>n = 2</math>: 2 (independent of <math>n</math>)
|-
| {{arithmetic function value|independence number|2}} || As [[cycle graph]] <math>C_n, n = 4</math>: greatest integer of <math>n/2</math> equals greatest integer of 4/2 equals 2 As <math>K_{m,n}, m = n = 2</math>: <math>\max \{ m,n \} = \max \{ 2,2 \} = 2</math> As <math>n</math>-dimensional hypercube, <math>n = 2</math>: <math>2^{n-1} = 2^{2-1} = 2</math>
|-
| {{arithmetic function value|chromatic number|2}} || As [[cycle graph]] <math>C_n, n = 4</math>: 2 (in general, it is 2 for even <math>n</math> and 3 for odd <math>n</math> As <math>K_{m,n}, m = n = 2</math>: 2 (independent of <math>m,n</math>, follows from being bipartite) As <math>n</math>-dimensional hypercube, <math>n = 2</math>: 2 (independent of <math>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 [[cycle graph]] <math>C_n, n = 4</math>: infinite (since <math>n</math> even) As <math>K_{m,n}, m = n = 2</math>: infinite, since bipartite As <math>n</math>-dimensional hypercube, <math>n = 2</math>: infinite, since bipartite
|-
| {{arithmetic function value|even girth|4}} || As [[cycle graph]] <math>C_n, n = 4</math>: <math>n = 4</math> (since <math>n</math> even) As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: 4 (independent of <math>m,n</math> as long as both are greater than 1) As <math>n</math>-dimensional hypercube, <math>n = 2</math>: 4 (independent of <math>n</math> for <math>n \ge 2</math>)
|-
| {{arithmetic function value|girth of a graph|4}} || As [[cycle graph]] <math>C_n, n = 4</math>: <math>n = 4</math> As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: 4 (independent of <math>m,n</math> as long as both are greater than 1) As <math>n</math>-dimensional hypercube, <math>n = 2</math>: 4 (independent of <math>n</math> for <math>n \ge 2</math>)
|}

==Graph properties==

{| class="sortable" border="1"
! Property !! Satisfied? !! Explanation
|-
| [[satisfies property::connected graph]] || Yes ||
|-
| [[satisfies property::regular graph]] || Yes || all vertices have degree two
|-
| [[satisfies property::vertex-transitive graph]] || Yes ||
|-
| [[dissatisfies property::cubic graph]] || No ||
|-
| [[satisfies property::edge-transitive graph]] || Yes ||
|-
| [[satisfies property::symmetric graph]] || Yes ||
|-
| [[satisfies property::distance-transitive graph]] || Yes ||
|-
| [[satisfies property::bridgeless graph]] || Yes ||
|-
| [[satisfies property::strongly regular graph]] || Yes || The graph is a <math>\operatorname{srg}(4,2,0,2)</math>
|-
| [[satisfies property::bipartite graph]] || Yes ||
|}

==Graph operations==

{| class="sortable" border="1"
! Operation !! Graph obtained as a result of the operation
|-
| [[complement of a graph]] || [[matching graph]] on 4 vertices
|-
| [[line graph]] || isomorphic to the original graph
|-
| [[prism of a graph]] || [[cube graph]]
|}

==Algebraic theory==

===Adjacency matrix===

The adjacency matrix is:

<math>\begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\\end{pmatrix}</math>

It can alternately be written in the following form, which is more computationally convenient because it clearly identifies blocks of 0s and 1s:

<math>\begin{pmatrix} 0 & 0 & 1 & 1 \\0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\1 & 1 & 0 & 0 \\\end{pmatrix}</math>

This matrix is uniquely defined up to conjugation by permutations. Below are some important associated algebraic invariants:

{| class="sortable" border="1"
! Algebraic invariant !! Value !! Explanation
|-
| [[characteristic polynomial of a graph|characteristic polynomial]] || <math>t^4 - 4t^2</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>t^{m + n} - mnt^{m + n - 2} = t^{2 + 2} - (2)(2)t^{2 + 2 - 2} = t^4 - 4t^2</math>
|-
| [[minimal polynomial of a graph|minimal polynomial]] || <math>t^3 - 4t</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>t^3 - mnt = t^3 - (2)(2)t = t^3 - 4t</math>
|-
| rank of adjacency matrix || 2 || As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: 2 (independent of <math>m,n</math>)
|-
| eigenvalues (roots of characteristic polynomial) || 0 (2 times), 2 (1 time), -2 (1 time)|| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: 0 (<math>m + n - 2 = 2 + 2 - 2 = 2</math> times), <math>\sqrt{mn} = \sqrt{(2)(2)} = 2</math> (1 time), <math>-\sqrt{mn} = -\sqrt{(2)(2)} = -2</math> (1 time)
|}

===Laplacian matrix===

The [[Laplacian matrix]] is as follows:

<math>\begin{pmatrix} 2 & 0 & -1 & -1 \\0 & 2 & -1 & -1 \\ -1 & -1 & 2 & 0 \\ -1 & -1 & 0 & 2 \\\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 - 4)(t - 2)^2</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>t(t - (m + n))(t - m)^{n-1}(t-n)^{m-1}</math>
|-
| minimal polynomial || <math>t(t - 2)(t - 4)</math> || As complete bipartite graph <math>K_{m,m}, m = 2</math>: <math>t(t - m)(t - 2m)</math>
|-
| rank of Laplacian matrix || 3 || As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>m + n - 1 = 2 + 2 - 1 = 3</math>
|-
| eigenvalues (roots of characteristic polynomial) || 0 (1 time), 4 (1 time), 2 (2 times) || As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (1 time), <math>m + n = 4</math> (1 time), <math>m = n = 2</math> (2 times: <math>n - 1 = 2 - 1 = 1</math> times as <math>m</math> and <math>m - 1 = 2 - 1 = 1</math> times as <math>m</math>)
|}

===Normalized Laplacian matrix===

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

<math>\begin{pmatrix} 1 & 0 & -1/2 & -1/2 \\0 & 1 & -1/2 & -1/2 \\ -1/2 & -1/2 & 1 & 0 \\ -1/2 & -1/2 & 0 & 1 \\\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)^2</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 2</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 = 2</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 || 3 || As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>m + n - 1 = 2 + 2 - 1 = 5</math>
|-
| eigenvalues (roots of characteristic polynomial) || 0 (1 time), 2 (1 time), 1 (2 times) || As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: 0 (1 time), 2 (1 time), 1 (<math>m + n - 2 = 2 + 2 - 2 = 2</math> times)
|}

==Realization==

===As Cayley graph===

Note that for this to be the Cayley graph of a group, the group must have order 4, and the generating set with respect to which we construct the Cayley graph must be a [[symmetric subset]] of the group of size 2.

{| class="sortable" border="1"
! Group !! Choice of [[groupprops:symmetric subset|symmetric set]] that is a [[groupprops:generating set|generating set]] for which the Cayley graph is this
|-
| [[groupprops:cyclic group:Z4|cyclic group:Z4]] || cyclic generator and its inverse
|-
| [[groupprops:Klein four-group|Klein four-group]] || two distinct elements of order two
|}

==Geometric embeddings==

===Planar embedding as a square===

The graph has a very nice embedding as a square in the plane: the vertices embed as the vertices of the square, and the edges as the edges of the square. Explicitly, we can embed the vertices as:

<math>1 \leftrightarrow (0,0), 2 \leftrightarrow (1,0), 3 \leftrightarrow (1,1), 4 \leftrightarrow (0,1)</math>

This embedding is nice in a number of ways:

* It demonstrates that the graph is a [[planar graph]].
* Moreover, it demonstrates that the graph can be embedded in the plane using straight line segments for edges. This is not possible for all planar graphs.
* It demonstrates that the graph is a [[unit distance graph]]: two points are adjacent in the embedding if and only if the distance between them in the Euclidean plane is 1.
* It preserves all the symmetries of the graph. Explicitly, for every automorphism of the cycle graph, there is a (unique) self-isometry of the Euclidean plane that induces that automorphism on the cycle graph.

Complete bipartite graph:K3,3

2014-05-26T00:18:34Z

Vipul: /* Normalized Laplacian matrix */

{{particular undirected graph}}

==Definition==

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==

===Descriptions of vertex set and edge set===

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

Vertex set: <math>\{ 1,2,3,4,5,6 \}</math>

Edge set: <math>\{ \{ 1,4 \}, \{ 1,5 \}, \{ 1,6 \}, \{ 2,4 \}, \{ 2,5 \}, \{ 2,6 \}, \{ 3,4 \}, \{ 3,5 \}, \{ 3, 6 \} \}</math>

===Adjacency matrix===

With the above ordering of the vertices, the adjacency matrix is as follows:

<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 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)
|}

==Graph properties==

{| class="sortable" border="1"
! Property !! Satisfied? !! Explanation
|-
| [[satisfies property::connected graph]] || Yes ||
|-
| [[satisfies property::regular graph]] || Yes || <math>K_{m,n}</math> is regular if <math>m = n</math>
|-
| [[satisfies property::vertex-transitive graph]] || Yes || <math>K_{m,n}</math> is vertex-transitive if <math>m = n</math>
|-
| [[satisfies property::cubic graph]] || Yes ||
|-
| [[satisfies property::edge-transitive graph]] || Yes ||
|-
| [[satisfies property::symmetric graph]] || Yes ||
|-
| [[satisfies property::distance-transitive graph]] || Yes ||
|-
| [[satisfies property::bridgeless graph]] || Yes ||
|-
| [[satisfies property::strongly regular graph]] || Yes || The graph is a <math>\operatorname{srg}(6,3,0,3)</math>. In general, a complete bipartite graph <math>K_{m,n}</math> is strongly regular iff <math>m = n</math>, and in that case it is a <math>\operatorname{srg}(2m,m,0,m)</math>
|-
| [[satisfies property::bipartite graph]] || Yes || By definition of complete bipartite graph
|}

==Algebraic theory==

===Adjacency matrix===

The adjacency matrix is as follows:

<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>

This matrix is uniquely defined up to conjugation by permutations. Below are some important associated algebraic invariants:

{| class="sortable" border="1"
! Algebraic invariant !! Value !! Explanation
|-
| [[characteristic polynomial of a graph|characteristic polynomial]] || <math>t^6 - 9t^4</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>t^{m + n} - mnt^{m + n - 2} = t^{3 + 3} - (3)(3)t^{3 + 3 - 2} = t^6 - 9t^4</math>
|-
| [[minimal polynomial of a graph|minimal polynomial]] || <math>t^3 - 9t</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>t^3 - mnt = t^3 - (3)(3)t = t^3 - 9t</math>
|-
| rank of adjacency matrix || 2 || As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 2 (independent of <math>m,n</math>)
|-
| eigenvalues (roots of characteristic polynomial) || 0 (4 times), 3 (1 time), -3 (1 time)|| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (<math>m + n - 2 = 3 + 3 - 2 = 4</math> times), <math>\sqrt{mn} = \sqrt{(3)(3)} = 3</math> (1 time), <math>-\sqrt{mn} = -\sqrt{(3)(3)} = -3</math> (1 time)
|}

===Laplacian matrix===

The [[Laplacian matrix]] is as follows:

<math>\begin{pmatrix} 3 & 0 & 0 & -1 & -1 & -1 \\0 & 3 & 0 & -1 & -1 & -1 \\0 & 0 & 3 & -1 & -1 & -1 \\ -1 & -1 & -1 & 3 & 0 & 0 \\ -1 & -1 & -1 & 0 & 3 & 0 \\-1 & -1 & -1 & 0 & 0 & 3 \\\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 - 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 - 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>
|-
| 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>)
|}

===Normalized Laplacian matrix===

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

<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>

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)^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>)
|-
| 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 = 4</math> times)
|}

Square graph

2014-05-26T00:16:47Z

Vipul: /* Normalized Laplacian matrix */

{{particular undirected graph}}

==Definition==

This [[undirected graph]], called the '''square graph''', is defined in the following equivalent ways:

# It is the [[cycle graph]] on 4 vertices, denoted <math>C_4</math>.
# It is the [[complete bipartite graph]] <math>K_{2,2}</math>
# It is the 2-dimensional [[hypercube graph]].
# It is the 2-dimensional [[hyperoctahedron graph]].
==Explicit descriptions==

===Description of vertex set and edge set===

Vertex set: <math>\{ 1,2,3,4\}</math>

Edge set: <math>\{ \{ 1,2 \} , \{ 2,3 \} , \{ 3, 4 \} , \{ 1, 4 \} \}</math>

Note that with this description, the two parts in a bipartite graph description are <math>\{ 1,3 \}</math> and <math>\{ 2,4 \}</math>.

===Adjacency matrix===

With the ordering of the vertex set and edge set given above, the adjacency matrix is:

<math>\begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\\end{pmatrix}</math>

If we re-ordered the vertices by interchanging the roles of vertices 2 and 3, we would get the following adjacency matrix:

<math>\begin{pmatrix} 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\\end{pmatrix}</math>

==Arithmetic functions==

===Size measures===

{| class="sortable" border="1"
! Function !! Value !! Explanation
|-
| {{arithmetic function value|size of vertex set|4}} || As cycle graph <math>C_n, n = 4</math>: <math>n = 4</math> As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>m + n = 2 + 2 = 4</math> As <math>n</math>-dimensional hypercube, <math>n = 2</math>: <math>2^n = 2^2 = 4</math>
|-
| {{arithmetic function value|size of edge set|4}} || As cycle graph <math>C_n, n = 4</math>: <math>n = 4</math> As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>mn = 2(2) = 4</math> As <math>n</math>-dimensional hypercube, <math>n = 2</math>: <math>n \cdot 2^{n-1} = 2 \cdot 2^{2-1} = 4</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|2}} || As cycle graph <math>C_n, n = 4</math>: 2 (independent of <math>n</math>) As complete bipartite graph <math>K_{m,n}, m = n = 2</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 = 2</math> As <math>n</math>-dimensional hypercube, <math>n = 2</math>: <math>n = 2</math> As <math>n</math>-dimensional hyperoctahedron, <math>n = 2</math>: <math>2n - 2 = 2(2) - 2 = 2</math>
|-
| {{arithmetic function value|eccentricity of a vertex|2}} || As cycle graph <math>C_n, n = 4</math>: greatest integer of <math>n/2</math> equals greater integer of 4/2 equals 2 As complete bipartite graph <math>K_{m,n}, m= n = 2</math>: 2 (independent of <math>m,n</math>, though it uses that both numbers are greater than 1) As <math>n</math>-dimensional hypercube, <math>n = 2</math>: <math>n = 2</math> As <math>n</math>-dimensional hyperoctahedron, <math>n = 2</math>: 2 (independent of <math>n</math>, for <math>n \ge 2</math>)
|}

===Other numerical invariants===

{| class="sortable" border="1"
! Function !! Value !! Explanation
|-
| {{arithmetic function value|clique number|2}} || As [[cycle graph]] <math>C_n, n = 4</math>: 2 (independent of <math>n</math> for <math>n \ge 4</math>) As <math>K_{m,n}, m = n = 2</math>: 2 (independent of <math>m,n</math>, follows from being bipartite) As <math>n</math>-dimensional hypercube, <math>n = 2</math>: 2 (independent of <math>n</math>)
|-
| {{arithmetic function value|independence number|2}} || As [[cycle graph]] <math>C_n, n = 4</math>: greatest integer of <math>n/2</math> equals greatest integer of 4/2 equals 2 As <math>K_{m,n}, m = n = 2</math>: <math>\max \{ m,n \} = \max \{ 2,2 \} = 2</math> As <math>n</math>-dimensional hypercube, <math>n = 2</math>: <math>2^{n-1} = 2^{2-1} = 2</math>
|-
| {{arithmetic function value|chromatic number|2}} || As [[cycle graph]] <math>C_n, n = 4</math>: 2 (in general, it is 2 for even <math>n</math> and 3 for odd <math>n</math> As <math>K_{m,n}, m = n = 2</math>: 2 (independent of <math>m,n</math>, follows from being bipartite) As <math>n</math>-dimensional hypercube, <math>n = 2</math>: 2 (independent of <math>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 [[cycle graph]] <math>C_n, n = 4</math>: infinite (since <math>n</math> even) As <math>K_{m,n}, m = n = 2</math>: infinite, since bipartite As <math>n</math>-dimensional hypercube, <math>n = 2</math>: infinite, since bipartite
|-
| {{arithmetic function value|even girth|4}} || As [[cycle graph]] <math>C_n, n = 4</math>: <math>n = 4</math> (since <math>n</math> even) As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: 4 (independent of <math>m,n</math> as long as both are greater than 1) As <math>n</math>-dimensional hypercube, <math>n = 2</math>: 4 (independent of <math>n</math> for <math>n \ge 2</math>)
|-
| {{arithmetic function value|girth of a graph|4}} || As [[cycle graph]] <math>C_n, n = 4</math>: <math>n = 4</math> As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: 4 (independent of <math>m,n</math> as long as both are greater than 1) As <math>n</math>-dimensional hypercube, <math>n = 2</math>: 4 (independent of <math>n</math> for <math>n \ge 2</math>)
|}

==Graph properties==

{| class="sortable" border="1"
! Property !! Satisfied? !! Explanation
|-
| [[satisfies property::connected graph]] || Yes ||
|-
| [[satisfies property::regular graph]] || Yes || all vertices have degree two
|-
| [[satisfies property::vertex-transitive graph]] || Yes ||
|-
| [[dissatisfies property::cubic graph]] || No ||
|-
| [[satisfies property::edge-transitive graph]] || Yes ||
|-
| [[satisfies property::symmetric graph]] || Yes ||
|-
| [[satisfies property::distance-transitive graph]] || Yes ||
|-
| [[satisfies property::bridgeless graph]] || Yes ||
|-
| [[satisfies property::strongly regular graph]] || Yes || The graph is a <math>\operatorname{srg}(4,2,0,2)</math>
|-
| [[satisfies property::bipartite graph]] || Yes ||
|}

==Graph operations==

{| class="sortable" border="1"
! Operation !! Graph obtained as a result of the operation
|-
| [[complement of a graph]] || [[matching graph]] on 4 vertices
|-
| [[line graph]] || isomorphic to the original graph
|-
| [[prism of a graph]] || [[cube graph]]
|}

==Algebraic theory==

===Adjacency matrix===

The adjacency matrix is:

<math>\begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\\end{pmatrix}</math>

It can alternately be written in the following form, which is more computationally convenient because it clearly identifies blocks of 0s and 1s:

<math>\begin{pmatrix} 0 & 0 & 1 & 1 \\0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\1 & 1 & 0 & 0 \\\end{pmatrix}</math>

This matrix is uniquely defined up to conjugation by permutations. Below are some important associated algebraic invariants:

{| class="sortable" border="1"
! Algebraic invariant !! Value !! Explanation
|-
| [[characteristic polynomial of a graph|characteristic polynomial]] || <math>t^4 - 4t^2</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>t^{m + n} - mnt^{m + n - 2} = t^{2 + 2} - (2)(2)t^{2 + 2 - 2} = t^4 - 4t^2</math>
|-
| [[minimal polynomial of a graph|minimal polynomial]] || <math>t^3 - 4t</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>t^3 - mnt = t^3 - (2)(2)t = t^3 - 4t</math>
|-
| rank of adjacency matrix || 2 || As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: 2 (independent of <math>m,n</math>)
|-
| eigenvalues (roots of characteristic polynomial) || 0 (2 times), 2 (1 time), -2 (1 time)|| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: 0 (<math>m + n - 2 = 2 + 2 - 2 = 2</math> times), <math>\sqrt{mn} = \sqrt{(2)(2)} = 2</math> (1 time), <math>-\sqrt{mn} = -\sqrt{(2)(2)} = -2</math> (1 time)
|}

===Laplacian matrix===

The [[Laplacian matrix]] is as follows:

<math>\begin{pmatrix} 2 & 0 & -1 & -1 \\0 & 2 & -1 & -1 \\ -1 & -1 & 2 & 0 \\ -1 & -1 & 0 & 2 \\\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 - 4)(t - 2)^2</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>t(t - (m + n))(t - m)^{n-1}(t-n)^{m-1}</math>
|-
| minimal polynomial || <math>t(t - 2)(t - 4)</math> || As complete bipartite graph <math>K_{m,m}, m = 2</math>: <math>t(t - m)(t - 2m)</math>
|-
| rank of Laplacian matrix || 3 || As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>m + n - 1 = 2 + 2 - 1 = 3</math>
|-
| eigenvalues (roots of characteristic polynomial) || 0 (1 time), 4 (1 time), 2 (2 times) || As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (1 time), <math>m + n = 4</math> (1 time), <math>m = n = 2</math> (2 times: <math>n - 1 = 2 - 1 = 1</math> times as <math>m</math> and <math>m - 1 = 2 - 1 = 1</math> times as <math>m</math>)
|}

===Normalized Laplacian matrix===

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

<math>\begin{pmatrix} 1 & 0 & -1/2 & -1/2 \\0 & 1 & -1/2 & -1/2 \\ -1/2 & -1/2 & 1 & 0 \\ -1/2 & -1/2 & 0 & 1 \\\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)^2</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 2</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 = 2</math>: <math>t(t - 1)(t - 2)</math>
|-
| rank of normalized Laplacian matrix || 3 || As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>m + n - 1 = 2 + 2 - 1 = 5</math>
|-
| eigenvalues (roots of characteristic polynomial) || 0 (1 time), 2 (1 time), 1 (2 times) || As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: 0 (1 time), 2 (1 time), 1 (<math>m + n - 2 = 2 + 2 - 2 = 2</math> times)
|}

==Realization==

===As Cayley graph===

Note that for this to be the Cayley graph of a group, the group must have order 4, and the generating set with respect to which we construct the Cayley graph must be a [[symmetric subset]] of the group of size 2.

{| class="sortable" border="1"
! Group !! Choice of [[groupprops:symmetric subset|symmetric set]] that is a [[groupprops:generating set|generating set]] for which the Cayley graph is this
|-
| [[groupprops:cyclic group:Z4|cyclic group:Z4]] || cyclic generator and its inverse
|-
| [[groupprops:Klein four-group|Klein four-group]] || two distinct elements of order two
|}

==Geometric embeddings==

===Planar embedding as a square===

The graph has a very nice embedding as a square in the plane: the vertices embed as the vertices of the square, and the edges as the edges of the square. Explicitly, we can embed the vertices as:

<math>1 \leftrightarrow (0,0), 2 \leftrightarrow (1,0), 3 \leftrightarrow (1,1), 4 \leftrightarrow (0,1)</math>

This embedding is nice in a number of ways:

* It demonstrates that the graph is a [[planar graph]].
* Moreover, it demonstrates that the graph can be embedded in the plane using straight line segments for edges. This is not possible for all planar graphs.
* It demonstrates that the graph is a [[unit distance graph]]: two points are adjacent in the embedding if and only if the distance between them in the Euclidean plane is 1.
* It preserves all the symmetries of the graph. Explicitly, for every automorphism of the cycle graph, there is a (unique) self-isometry of the Euclidean plane that induces that automorphism on the cycle graph.

Complete bipartite graph:K3,3

2014-05-26T00:16:04Z

Vipul: /* Normalized Laplacian matrix */

{{particular undirected graph}}

==Definition==

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==

===Descriptions of vertex set and edge set===

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

Vertex set: <math>\{ 1,2,3,4,5,6 \}</math>

Edge set: <math>\{ \{ 1,4 \}, \{ 1,5 \}, \{ 1,6 \}, \{ 2,4 \}, \{ 2,5 \}, \{ 2,6 \}, \{ 3,4 \}, \{ 3,5 \}, \{ 3, 6 \} \}</math>

===Adjacency matrix===

With the above ordering of the vertices, the adjacency matrix is as follows:

<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 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)
|}

==Graph properties==

{| class="sortable" border="1"
! Property !! Satisfied? !! Explanation
|-
| [[satisfies property::connected graph]] || Yes ||
|-
| [[satisfies property::regular graph]] || Yes || <math>K_{m,n}</math> is regular if <math>m = n</math>
|-
| [[satisfies property::vertex-transitive graph]] || Yes || <math>K_{m,n}</math> is vertex-transitive if <math>m = n</math>
|-
| [[satisfies property::cubic graph]] || Yes ||
|-
| [[satisfies property::edge-transitive graph]] || Yes ||
|-
| [[satisfies property::symmetric graph]] || Yes ||
|-
| [[satisfies property::distance-transitive graph]] || Yes ||
|-
| [[satisfies property::bridgeless graph]] || Yes ||
|-
| [[satisfies property::strongly regular graph]] || Yes || The graph is a <math>\operatorname{srg}(6,3,0,3)</math>. In general, a complete bipartite graph <math>K_{m,n}</math> is strongly regular iff <math>m = n</math>, and in that case it is a <math>\operatorname{srg}(2m,m,0,m)</math>
|-
| [[satisfies property::bipartite graph]] || Yes || By definition of complete bipartite graph
|}

==Algebraic theory==

===Adjacency matrix===

The adjacency matrix is as follows:

<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>

This matrix is uniquely defined up to conjugation by permutations. Below are some important associated algebraic invariants:

{| class="sortable" border="1"
! Algebraic invariant !! Value !! Explanation
|-
| [[characteristic polynomial of a graph|characteristic polynomial]] || <math>t^6 - 9t^4</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>t^{m + n} - mnt^{m + n - 2} = t^{3 + 3} - (3)(3)t^{3 + 3 - 2} = t^6 - 9t^4</math>
|-
| [[minimal polynomial of a graph|minimal polynomial]] || <math>t^3 - 9t</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>t^3 - mnt = t^3 - (3)(3)t = t^3 - 9t</math>
|-
| rank of adjacency matrix || 2 || As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 2 (independent of <math>m,n</math>)
|-
| eigenvalues (roots of characteristic polynomial) || 0 (4 times), 3 (1 time), -3 (1 time)|| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (<math>m + n - 2 = 3 + 3 - 2 = 4</math> times), <math>\sqrt{mn} = \sqrt{(3)(3)} = 3</math> (1 time), <math>-\sqrt{mn} = -\sqrt{(3)(3)} = -3</math> (1 time)
|}

===Laplacian matrix===

The [[Laplacian matrix]] is as follows:

<math>\begin{pmatrix} 3 & 0 & 0 & -1 & -1 & -1 \\0 & 3 & 0 & -1 & -1 & -1 \\0 & 0 & 3 & -1 & -1 & -1 \\ -1 & -1 & -1 & 3 & 0 & 0 \\ -1 & -1 & -1 & 0 & 3 & 0 \\-1 & -1 & -1 & 0 & 0 & 3 \\\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 - 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 - 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>
|-
| 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>)
|}

===Normalized Laplacian matrix===

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

<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>

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)^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>
|-
| 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 = 4</math> times)
|}

Complete bipartite graph:K3,3

2014-05-26T00:15:49Z

Vipul: /* Normalized Laplacian matrix */

{{particular undirected graph}}

==Definition==

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==

===Descriptions of vertex set and edge set===

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

Vertex set: <math>\{ 1,2,3,4,5,6 \}</math>

Edge set: <math>\{ \{ 1,4 \}, \{ 1,5 \}, \{ 1,6 \}, \{ 2,4 \}, \{ 2,5 \}, \{ 2,6 \}, \{ 3,4 \}, \{ 3,5 \}, \{ 3, 6 \} \}</math>

===Adjacency matrix===

With the above ordering of the vertices, the adjacency matrix is as follows:

<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 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)
|}

==Graph properties==

{| class="sortable" border="1"
! Property !! Satisfied? !! Explanation
|-
| [[satisfies property::connected graph]] || Yes ||
|-
| [[satisfies property::regular graph]] || Yes || <math>K_{m,n}</math> is regular if <math>m = n</math>
|-
| [[satisfies property::vertex-transitive graph]] || Yes || <math>K_{m,n}</math> is vertex-transitive if <math>m = n</math>
|-
| [[satisfies property::cubic graph]] || Yes ||
|-
| [[satisfies property::edge-transitive graph]] || Yes ||
|-
| [[satisfies property::symmetric graph]] || Yes ||
|-
| [[satisfies property::distance-transitive graph]] || Yes ||
|-
| [[satisfies property::bridgeless graph]] || Yes ||
|-
| [[satisfies property::strongly regular graph]] || Yes || The graph is a <math>\operatorname{srg}(6,3,0,3)</math>. In general, a complete bipartite graph <math>K_{m,n}</math> is strongly regular iff <math>m = n</math>, and in that case it is a <math>\operatorname{srg}(2m,m,0,m)</math>
|-
| [[satisfies property::bipartite graph]] || Yes || By definition of complete bipartite graph
|}

==Algebraic theory==

===Adjacency matrix===

The adjacency matrix is as follows:

<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>

This matrix is uniquely defined up to conjugation by permutations. Below are some important associated algebraic invariants:

{| class="sortable" border="1"
! Algebraic invariant !! Value !! Explanation
|-
| [[characteristic polynomial of a graph|characteristic polynomial]] || <math>t^6 - 9t^4</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>t^{m + n} - mnt^{m + n - 2} = t^{3 + 3} - (3)(3)t^{3 + 3 - 2} = t^6 - 9t^4</math>
|-
| [[minimal polynomial of a graph|minimal polynomial]] || <math>t^3 - 9t</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>t^3 - mnt = t^3 - (3)(3)t = t^3 - 9t</math>
|-
| rank of adjacency matrix || 2 || As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 2 (independent of <math>m,n</math>)
|-
| eigenvalues (roots of characteristic polynomial) || 0 (4 times), 3 (1 time), -3 (1 time)|| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (<math>m + n - 2 = 3 + 3 - 2 = 4</math> times), <math>\sqrt{mn} = \sqrt{(3)(3)} = 3</math> (1 time), <math>-\sqrt{mn} = -\sqrt{(3)(3)} = -3</math> (1 time)
|}

===Laplacian matrix===

The [[Laplacian matrix]] is as follows:

<math>\begin{pmatrix} 3 & 0 & 0 & -1 & -1 & -1 \\0 & 3 & 0 & -1 & -1 & -1 \\0 & 0 & 3 & -1 & -1 & -1 \\ -1 & -1 & -1 & 3 & 0 & 0 \\ -1 & -1 & -1 & 0 & 3 & 0 \\-1 & -1 & -1 & 0 & 0 & 3 \\\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 - 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 - 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>
|-
| 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>)
|}

===Normalized Laplacian matrix===

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

<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>

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)^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>
|-
| 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)
|}

Square graph

2014-05-26T00:14:21Z

Vipul: /* Normalized Laplacian matrix */

{{particular undirected graph}}

==Definition==

This [[undirected graph]], called the '''square graph''', is defined in the following equivalent ways:

# It is the [[cycle graph]] on 4 vertices, denoted <math>C_4</math>.
# It is the [[complete bipartite graph]] <math>K_{2,2}</math>
# It is the 2-dimensional [[hypercube graph]].
# It is the 2-dimensional [[hyperoctahedron graph]].
==Explicit descriptions==

===Description of vertex set and edge set===

Vertex set: <math>\{ 1,2,3,4\}</math>

Edge set: <math>\{ \{ 1,2 \} , \{ 2,3 \} , \{ 3, 4 \} , \{ 1, 4 \} \}</math>

Note that with this description, the two parts in a bipartite graph description are <math>\{ 1,3 \}</math> and <math>\{ 2,4 \}</math>.

===Adjacency matrix===

With the ordering of the vertex set and edge set given above, the adjacency matrix is:

<math>\begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\\end{pmatrix}</math>

If we re-ordered the vertices by interchanging the roles of vertices 2 and 3, we would get the following adjacency matrix:

<math>\begin{pmatrix} 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\\end{pmatrix}</math>

==Arithmetic functions==

===Size measures===

{| class="sortable" border="1"
! Function !! Value !! Explanation
|-
| {{arithmetic function value|size of vertex set|4}} || As cycle graph <math>C_n, n = 4</math>: <math>n = 4</math> As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>m + n = 2 + 2 = 4</math> As <math>n</math>-dimensional hypercube, <math>n = 2</math>: <math>2^n = 2^2 = 4</math>
|-
| {{arithmetic function value|size of edge set|4}} || As cycle graph <math>C_n, n = 4</math>: <math>n = 4</math> As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>mn = 2(2) = 4</math> As <math>n</math>-dimensional hypercube, <math>n = 2</math>: <math>n \cdot 2^{n-1} = 2 \cdot 2^{2-1} = 4</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|2}} || As cycle graph <math>C_n, n = 4</math>: 2 (independent of <math>n</math>) As complete bipartite graph <math>K_{m,n}, m = n = 2</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 = 2</math> As <math>n</math>-dimensional hypercube, <math>n = 2</math>: <math>n = 2</math> As <math>n</math>-dimensional hyperoctahedron, <math>n = 2</math>: <math>2n - 2 = 2(2) - 2 = 2</math>
|-
| {{arithmetic function value|eccentricity of a vertex|2}} || As cycle graph <math>C_n, n = 4</math>: greatest integer of <math>n/2</math> equals greater integer of 4/2 equals 2 As complete bipartite graph <math>K_{m,n}, m= n = 2</math>: 2 (independent of <math>m,n</math>, though it uses that both numbers are greater than 1) As <math>n</math>-dimensional hypercube, <math>n = 2</math>: <math>n = 2</math> As <math>n</math>-dimensional hyperoctahedron, <math>n = 2</math>: 2 (independent of <math>n</math>, for <math>n \ge 2</math>)
|}

===Other numerical invariants===

{| class="sortable" border="1"
! Function !! Value !! Explanation
|-
| {{arithmetic function value|clique number|2}} || As [[cycle graph]] <math>C_n, n = 4</math>: 2 (independent of <math>n</math> for <math>n \ge 4</math>) As <math>K_{m,n}, m = n = 2</math>: 2 (independent of <math>m,n</math>, follows from being bipartite) As <math>n</math>-dimensional hypercube, <math>n = 2</math>: 2 (independent of <math>n</math>)
|-
| {{arithmetic function value|independence number|2}} || As [[cycle graph]] <math>C_n, n = 4</math>: greatest integer of <math>n/2</math> equals greatest integer of 4/2 equals 2 As <math>K_{m,n}, m = n = 2</math>: <math>\max \{ m,n \} = \max \{ 2,2 \} = 2</math> As <math>n</math>-dimensional hypercube, <math>n = 2</math>: <math>2^{n-1} = 2^{2-1} = 2</math>
|-
| {{arithmetic function value|chromatic number|2}} || As [[cycle graph]] <math>C_n, n = 4</math>: 2 (in general, it is 2 for even <math>n</math> and 3 for odd <math>n</math> As <math>K_{m,n}, m = n = 2</math>: 2 (independent of <math>m,n</math>, follows from being bipartite) As <math>n</math>-dimensional hypercube, <math>n = 2</math>: 2 (independent of <math>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 [[cycle graph]] <math>C_n, n = 4</math>: infinite (since <math>n</math> even) As <math>K_{m,n}, m = n = 2</math>: infinite, since bipartite As <math>n</math>-dimensional hypercube, <math>n = 2</math>: infinite, since bipartite
|-
| {{arithmetic function value|even girth|4}} || As [[cycle graph]] <math>C_n, n = 4</math>: <math>n = 4</math> (since <math>n</math> even) As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: 4 (independent of <math>m,n</math> as long as both are greater than 1) As <math>n</math>-dimensional hypercube, <math>n = 2</math>: 4 (independent of <math>n</math> for <math>n \ge 2</math>)
|-
| {{arithmetic function value|girth of a graph|4}} || As [[cycle graph]] <math>C_n, n = 4</math>: <math>n = 4</math> As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: 4 (independent of <math>m,n</math> as long as both are greater than 1) As <math>n</math>-dimensional hypercube, <math>n = 2</math>: 4 (independent of <math>n</math> for <math>n \ge 2</math>)
|}

==Graph properties==

{| class="sortable" border="1"
! Property !! Satisfied? !! Explanation
|-
| [[satisfies property::connected graph]] || Yes ||
|-
| [[satisfies property::regular graph]] || Yes || all vertices have degree two
|-
| [[satisfies property::vertex-transitive graph]] || Yes ||
|-
| [[dissatisfies property::cubic graph]] || No ||
|-
| [[satisfies property::edge-transitive graph]] || Yes ||
|-
| [[satisfies property::symmetric graph]] || Yes ||
|-
| [[satisfies property::distance-transitive graph]] || Yes ||
|-
| [[satisfies property::bridgeless graph]] || Yes ||
|-
| [[satisfies property::strongly regular graph]] || Yes || The graph is a <math>\operatorname{srg}(4,2,0,2)</math>
|-
| [[satisfies property::bipartite graph]] || Yes ||
|}

==Graph operations==

{| class="sortable" border="1"
! Operation !! Graph obtained as a result of the operation
|-
| [[complement of a graph]] || [[matching graph]] on 4 vertices
|-
| [[line graph]] || isomorphic to the original graph
|-
| [[prism of a graph]] || [[cube graph]]
|}

==Algebraic theory==

===Adjacency matrix===

The adjacency matrix is:

<math>\begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\\end{pmatrix}</math>

It can alternately be written in the following form, which is more computationally convenient because it clearly identifies blocks of 0s and 1s:

<math>\begin{pmatrix} 0 & 0 & 1 & 1 \\0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\1 & 1 & 0 & 0 \\\end{pmatrix}</math>

This matrix is uniquely defined up to conjugation by permutations. Below are some important associated algebraic invariants:

{| class="sortable" border="1"
! Algebraic invariant !! Value !! Explanation
|-
| [[characteristic polynomial of a graph|characteristic polynomial]] || <math>t^4 - 4t^2</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>t^{m + n} - mnt^{m + n - 2} = t^{2 + 2} - (2)(2)t^{2 + 2 - 2} = t^4 - 4t^2</math>
|-
| [[minimal polynomial of a graph|minimal polynomial]] || <math>t^3 - 4t</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>t^3 - mnt = t^3 - (2)(2)t = t^3 - 4t</math>
|-
| rank of adjacency matrix || 2 || As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: 2 (independent of <math>m,n</math>)
|-
| eigenvalues (roots of characteristic polynomial) || 0 (2 times), 2 (1 time), -2 (1 time)|| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: 0 (<math>m + n - 2 = 2 + 2 - 2 = 2</math> times), <math>\sqrt{mn} = \sqrt{(2)(2)} = 2</math> (1 time), <math>-\sqrt{mn} = -\sqrt{(2)(2)} = -2</math> (1 time)
|}

===Laplacian matrix===

The [[Laplacian matrix]] is as follows:

<math>\begin{pmatrix} 2 & 0 & -1 & -1 \\0 & 2 & -1 & -1 \\ -1 & -1 & 2 & 0 \\ -1 & -1 & 0 & 2 \\\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 - 4)(t - 2)^2</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>t(t - (m + n))(t - m)^{n-1}(t-n)^{m-1}</math>
|-
| minimal polynomial || <math>t(t - 2)(t - 4)</math> || As complete bipartite graph <math>K_{m,m}, m = 2</math>: <math>t(t - m)(t - 2m)</math>
|-
| rank of Laplacian matrix || 3 || As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>m + n - 1 = 2 + 2 - 1 = 3</math>
|-
| eigenvalues (roots of characteristic polynomial) || 0 (1 time), 4 (1 time), 2 (2 times) || As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (1 time), <math>m + n = 4</math> (1 time), <math>m = n = 2</math> (2 times: <math>n - 1 = 2 - 1 = 1</math> times as <math>m</math> and <math>m - 1 = 2 - 1 = 1</math> times as <math>m</math>)
|}

===Normalized Laplacian matrix===

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

<math>\begin{pmatrix} 1 & 0 & -1/2 & -1/2 \\0 & 1 & -1/2 & -1/2 \\ -1/2 & -1/2 & 1 & 0 \\ -1/2 & -1/2 & 0 & 1 \\\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)^2</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 2</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 = 2</math>: <math>t(t - 1)(t - 2)</math>
|-
| rank of normalized Laplacian matrix || 3 || As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>m + n - 1 = 2 + 2 - 1 = 5</math>
|-
| eigenvalues (roots of characteristic polynomial) || 0 (1 time), 2 (1 time), 1 (2 times) || As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (1 time), 2 (1 time), 1 (<math>m + n - 2 = 2 + 2 - 2 = 2</math> times)
|}

==Realization==

===As Cayley graph===

Note that for this to be the Cayley graph of a group, the group must have order 4, and the generating set with respect to which we construct the Cayley graph must be a [[symmetric subset]] of the group of size 2.

{| class="sortable" border="1"
! Group !! Choice of [[groupprops:symmetric subset|symmetric set]] that is a [[groupprops:generating set|generating set]] for which the Cayley graph is this
|-
| [[groupprops:cyclic group:Z4|cyclic group:Z4]] || cyclic generator and its inverse
|-
| [[groupprops:Klein four-group|Klein four-group]] || two distinct elements of order two
|}

==Geometric embeddings==

===Planar embedding as a square===

The graph has a very nice embedding as a square in the plane: the vertices embed as the vertices of the square, and the edges as the edges of the square. Explicitly, we can embed the vertices as:

<math>1 \leftrightarrow (0,0), 2 \leftrightarrow (1,0), 3 \leftrightarrow (1,1), 4 \leftrightarrow (0,1)</math>

This embedding is nice in a number of ways:

* It demonstrates that the graph is a [[planar graph]].
* Moreover, it demonstrates that the graph can be embedded in the plane using straight line segments for edges. This is not possible for all planar graphs.
* It demonstrates that the graph is a [[unit distance graph]]: two points are adjacent in the embedding if and only if the distance between them in the Euclidean plane is 1.
* It preserves all the symmetries of the graph. Explicitly, for every automorphism of the cycle graph, there is a (unique) self-isometry of the Euclidean plane that induces that automorphism on the cycle graph.

Star

2014-05-26T00:12:23Z

Vipul: /* Normalized Laplacian matrix */

==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. 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> 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> 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> 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> 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) ||
|}

Complete bipartite graph

2014-05-26T00:11:53Z

Vipul: /* Normalized Laplacian matrix */

{{undirected graph family}}

==Definition==

Suppose <matH>m,n</math> are positive integers. The '''complete bipartite graph''' <math>K_{m,n}</math> is an [[undirected graph]] defined as follows:

# Its vertex set is a disjoint union of a subset <math>A</math> of size <math>m</math> and a subset <math>B</math> of size <math>n</math>
# Its edge set is defined as follows: every vertex in <math>A</math> is adjacent to every vertex in <math>B</math>. However, no two vertices in <math>A</math> are adjacent to each other, and no two vertices in <math>B</math> are adjacent to each other.

Note that <math>K_{m,n}</math> and <math>K_{n,m}</math> are isomorphic, so the complete bipartite graph can be thought of as parametrized by ''unordered pairs'' of (possibly equal, possibly distinct) positive integers.

==Explicit descriptions==

===Adjacency matrix===

If we order the vertices so that <math>A</math> makes up the first <math>m</math> vertices and <math>B</math> makes up the last <math>n</math> vertices, the adjacency matrix looks like the block matrix below:

<math>\begin{pmatrix} 0_{m \times m} & E_{m \times n} \\ E_{n \times m} & 0_{n \times n}\\\end{pmatrix}</math>

Here, <math>0_{a \times b}</math> is shorthand for the <math>a \times b</math> matrix with 0s for all its entries and
<math>E_{a \times b}</math> is shorthand for the <math>a \times b</math> matrix with 1s for all its entries.

==Particular cases==

* One special case of interest is where <math>\min \{ m, n \} = 1</math>. This case of interesting because in this case, the graph becomes a [[tree]].
* Another case of interest is where <math>m = n</math>. This case is interesting because the graph acquires additional symmetry and becomes a [[vertex-transitive graph]].

==Arithmetic functions==

===Size measures===

{| class="sortable" border="1"
! Function !! Value !! Explanation
|-
| [[size of vertex set]] || <math>m + n</math> || Follows from definition as disjoint union of subsets of size <matH>m,n</math>
|-
| [[size of edge set]] || <math>mn</math> || Follows from definition: the edges correspond to choosing one element each from <math>A</math> (size <math>m</math>) and <math>B</math> (size <math>n</math>)
|}

===Numerical invariants associated with vertices===

Note that if <matH>m = n</math>, the graph is a [[vertex-transitive graph]], but if <math>m \ne n</math>, the graph is not a vertex-transitive graph.

{| class="sortable" border="1"
! Function !! Value !! Explanation
|-
| [[degree of a vertex]] || <math>n</math> for vertices in <math>A</math> <math>m</math> for vertices in <math>B</math> ||
|-
| [[eccentricity of a vertex]] || For vertices in <math>A</math>: 1 if <math>m = 1</math>, 2 if <math>m > 1</math> For vertices in <math>B</math>: 1 if <math>n = 1</math>, 2 if <math>n > 1</math> ||
|}

===Other numerical invariants===

{| class="sortable" border="1"
! Function !! Value !! Explanation
|-
| {{arithmetic function value|clique number|2}} ||Follows from being non-empty and bipartite
|-
| [[independence number]] || <math>\max \{ m, n \}</math> || <math>A</math> and <math>B</math> are the only ''maximal'' independent sets, so the larger among their sizes gives the independence number.
|-
| {{arithmetic function value|chromatic number|2}} ||Follows from being non-empty and bipartite
|-
| [[radius of a graph]] || 1 if <math>\min \{ m,n \} = 1</math> 2 if <math>\min \{m,n \} > 1</math> || Follows from computation of eccentricity of each vertex above
|-
| [[diameter of a graph]] || 1 if <math>\max \{ m,n \} = 1</math> 2 if <math>\max \{ m,n \} > 1</math> || Follows from computation of eccentricity of each vertex above
|-
| [[odd girth]] || infinite || follows from being bipartite
|-
| [[even girth]] || infinite if <math>\min \{ m,n \} = 1</math> 4 if <math>\min \{ m,n \} > 1</math> ||
|-
|[[girth of a graph]] || infinite if <math>\min \{ m,n \} = 1</math> 4 if <math>\min \{ m,n \} > 1</math> ||
|}

==Algebraic theory==

===Adjacency matrix===

If we order the vertices so that <math>A</math> makes up the first <math>m</math> vertices and <math>B</math> makes up the last <math>n</math> vertices, the adjacency matrix looks like the block matrix below:

<math>\begin{pmatrix} 0_{m \times m} & E_{m \times n} \\ E_{n \times m} & 0_{n \times n}\\\end{pmatrix}</math>

Here, <math>0_{a \times b}</math> is shorthand for the <math>a \times b</math> matrix with 0s for all its entries and
<math>E_{a \times b}</math> is shorthand for the <math>a \times b</math> matrix with 1s for all its entries.

We can thus compute various algebraic invariants:

{| class="sortable" border="1"
! Algebraic invariant !! Value !! Explanation
|-
| [[characteristic polynomial of a graph|characteristic polynomial]] || <math>t^{m + n} - mnt^{m + n - 2} = t^{m + n - 2}(t^2 - mn)</math> ||
|-
| [[minimal polynomial of a matrix|minimal polynomial]] || if <math>m + n > 2</math>: <math>t^3 - mnt = t(t^2 - mn)</math> if <math>m = n = 1</math>: <math>t^2 - mn</math> ||
|-
| rank of adjacency matrix || 2 ||
|-
| eigenvalues (roots of characteristic polynomial) || 0 (multiplicity <math>m + n - 2</math>), <math>\sqrt{mn}</math> (multiplicity 1), <math>-\sqrt{mn}</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} nI_{m \times m} & -E_{m \times n} \\ -E_{n \times m} & mI_{n \times n} \\\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 - (m + n))(t - m)^{n-1}(t-n)^{m-1}</math> ||
|-
| minimal polynomial || If <math>m \ne n</math> and both are greater than 1: <math>t(t - m)(t - n)(t - (m + n))</math> If <math>m = n > 1</math>: <math>t(t - m)(t - 2m)</math> If <math>m = 1, n > 1</math>: <math>t(t - 1)(t - (n + 1))</math> If <math>m > 1, n = 1</math>: <math>t(t - 1)(t - (m + 1))</math> ||
|-
| rank of Laplacian matrix || <math>m + n - 1</math> ||
|-
| eigenvalues (roots of characteristic polynomial) || 0 (1 time), <math>m + n</math> (1 time), <math>m</math> (<math>n - 1</math> times), <math>n</math> (<math>m - 1</math> times). If <math>m = 1</math>, <math>n</math> disappears as an eigenvalue. If <math>n = 1</math>, <math>m</math> disappears as an eigenvalue. ||
|}

===Normalized Laplacian matrix===

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

<math>\begin{pmatrix} I_{m \times m} & (-1/\sqrt{mn}) E_{m \times n} \\ (-1/\sqrt{mn}) E_{n \times m} & 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 - 2)(t - 1)^{m+n-2}</math> Note that when <math>m = n</math>, this simplifies to <math>t(t - 2)(t - 1)^{2(m - 1)}</math> ||
|-
| minimal polynomial || If <math>m + n > 2</math>: <math>t(t - 1)(t - 2)</math> If <math>m = n = 1</math>: <math>t(t - 2)</math> ||
|-
| rank of normalized Laplacian matrix || <math>m + n - 1</math> ||
|-
| eigenvalues (roots of characteristic polynomial) || 0 (1 time), 2 (1 time), 1 (<math>m + n - 2</math> times) Note that the eigenvalue 1 disappears if <math>m = n = 1</math> ||
|}

Star

2014-05-26T00:01:31Z

Vipul: /* Normalized Laplacian matrix */

==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. 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> 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> 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 - (k + 1)/\sqrt{k})(t - 1)^{k-1}</math> 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> 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) ||
|}

Star

2014-05-25T23:58:59Z

Vipul: /* Laplacian matrix */

==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. 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> 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> 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_{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> 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> 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) ||
|}

Complete bipartite graph

2014-05-25T23:58:00Z

Vipul: /* Normalized Laplacian matrix */

{{undirected graph family}}

==Definition==

Suppose <matH>m,n</math> are positive integers. The '''complete bipartite graph''' <math>K_{m,n}</math> is an [[undirected graph]] defined as follows:

# Its vertex set is a disjoint union of a subset <math>A</math> of size <math>m</math> and a subset <math>B</math> of size <math>n</math>
# Its edge set is defined as follows: every vertex in <math>A</math> is adjacent to every vertex in <math>B</math>. However, no two vertices in <math>A</math> are adjacent to each other, and no two vertices in <math>B</math> are adjacent to each other.

Note that <math>K_{m,n}</math> and <math>K_{n,m}</math> are isomorphic, so the complete bipartite graph can be thought of as parametrized by ''unordered pairs'' of (possibly equal, possibly distinct) positive integers.

==Explicit descriptions==

===Adjacency matrix===

If we order the vertices so that <math>A</math> makes up the first <math>m</math> vertices and <math>B</math> makes up the last <math>n</math> vertices, the adjacency matrix looks like the block matrix below:

<math>\begin{pmatrix} 0_{m \times m} & E_{m \times n} \\ E_{n \times m} & 0_{n \times n}\\\end{pmatrix}</math>

Here, <math>0_{a \times b}</math> is shorthand for the <math>a \times b</math> matrix with 0s for all its entries and
<math>E_{a \times b}</math> is shorthand for the <math>a \times b</math> matrix with 1s for all its entries.

==Particular cases==

* One special case of interest is where <math>\min \{ m, n \} = 1</math>. This case of interesting because in this case, the graph becomes a [[tree]].
* Another case of interest is where <math>m = n</math>. This case is interesting because the graph acquires additional symmetry and becomes a [[vertex-transitive graph]].

==Arithmetic functions==

===Size measures===

{| class="sortable" border="1"
! Function !! Value !! Explanation
|-
| [[size of vertex set]] || <math>m + n</math> || Follows from definition as disjoint union of subsets of size <matH>m,n</math>
|-
| [[size of edge set]] || <math>mn</math> || Follows from definition: the edges correspond to choosing one element each from <math>A</math> (size <math>m</math>) and <math>B</math> (size <math>n</math>)
|}

===Numerical invariants associated with vertices===

Note that if <matH>m = n</math>, the graph is a [[vertex-transitive graph]], but if <math>m \ne n</math>, the graph is not a vertex-transitive graph.

{| class="sortable" border="1"
! Function !! Value !! Explanation
|-
| [[degree of a vertex]] || <math>n</math> for vertices in <math>A</math> <math>m</math> for vertices in <math>B</math> ||
|-
| [[eccentricity of a vertex]] || For vertices in <math>A</math>: 1 if <math>m = 1</math>, 2 if <math>m > 1</math> For vertices in <math>B</math>: 1 if <math>n = 1</math>, 2 if <math>n > 1</math> ||
|}

===Other numerical invariants===

{| class="sortable" border="1"
! Function !! Value !! Explanation
|-
| {{arithmetic function value|clique number|2}} ||Follows from being non-empty and bipartite
|-
| [[independence number]] || <math>\max \{ m, n \}</math> || <math>A</math> and <math>B</math> are the only ''maximal'' independent sets, so the larger among their sizes gives the independence number.
|-
| {{arithmetic function value|chromatic number|2}} ||Follows from being non-empty and bipartite
|-
| [[radius of a graph]] || 1 if <math>\min \{ m,n \} = 1</math> 2 if <math>\min \{m,n \} > 1</math> || Follows from computation of eccentricity of each vertex above
|-
| [[diameter of a graph]] || 1 if <math>\max \{ m,n \} = 1</math> 2 if <math>\max \{ m,n \} > 1</math> || Follows from computation of eccentricity of each vertex above
|-
| [[odd girth]] || infinite || follows from being bipartite
|-
| [[even girth]] || infinite if <math>\min \{ m,n \} = 1</math> 4 if <math>\min \{ m,n \} > 1</math> ||
|-
|[[girth of a graph]] || infinite if <math>\min \{ m,n \} = 1</math> 4 if <math>\min \{ m,n \} > 1</math> ||
|}

==Algebraic theory==

===Adjacency matrix===

If we order the vertices so that <math>A</math> makes up the first <math>m</math> vertices and <math>B</math> makes up the last <math>n</math> vertices, the adjacency matrix looks like the block matrix below:

<math>\begin{pmatrix} 0_{m \times m} & E_{m \times n} \\ E_{n \times m} & 0_{n \times n}\\\end{pmatrix}</math>

Here, <math>0_{a \times b}</math> is shorthand for the <math>a \times b</math> matrix with 0s for all its entries and
<math>E_{a \times b}</math> is shorthand for the <math>a \times b</math> matrix with 1s for all its entries.

We can thus compute various algebraic invariants:

{| class="sortable" border="1"
! Algebraic invariant !! Value !! Explanation
|-
| [[characteristic polynomial of a graph|characteristic polynomial]] || <math>t^{m + n} - mnt^{m + n - 2} = t^{m + n - 2}(t^2 - mn)</math> ||
|-
| [[minimal polynomial of a matrix|minimal polynomial]] || if <math>m + n > 2</math>: <math>t^3 - mnt = t(t^2 - mn)</math> if <math>m = n = 1</math>: <math>t^2 - mn</math> ||
|-
| rank of adjacency matrix || 2 ||
|-
| eigenvalues (roots of characteristic polynomial) || 0 (multiplicity <math>m + n - 2</math>), <math>\sqrt{mn}</math> (multiplicity 1), <math>-\sqrt{mn}</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} nI_{m \times m} & -E_{m \times n} \\ -E_{n \times m} & mI_{n \times n} \\\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 - (m + n))(t - m)^{n-1}(t-n)^{m-1}</math> ||
|-
| minimal polynomial || If <math>m \ne n</math> and both are greater than 1: <math>t(t - m)(t - n)(t - (m + n))</math> If <math>m = n > 1</math>: <math>t(t - m)(t - 2m)</math> If <math>m = 1, n > 1</math>: <math>t(t - 1)(t - (n + 1))</math> If <math>m > 1, n = 1</math>: <math>t(t - 1)(t - (m + 1))</math> ||
|-
| rank of Laplacian matrix || <math>m + n - 1</math> ||
|-
| eigenvalues (roots of characteristic polynomial) || 0 (1 time), <math>m + n</math> (1 time), <math>m</math> (<math>n - 1</math> times), <math>n</math> (<math>m - 1</math> times). If <math>m = 1</math>, <math>n</math> disappears as an eigenvalue. If <math>n = 1</math>, <math>m</math> disappears as an eigenvalue. ||
|}

===Normalized Laplacian matrix===

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

<math>\begin{pmatrix} I_{m \times m} & (-1/\sqrt{mn}) E_{m \times n} \\ (-1/\sqrt{mn}) E_{n \times m} & 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 - (m + n)/\sqrt{mn})(t - 1)^{m+n-2}</math> Note that when <math>m = n</math>, this simplifies to <math>t(t - 2)(t - 1)^{2(m - 1)}</math> ||
|-
| minimal polynomial || If <math>m + n > 2</math>: <math>t(t - 1)(t - (m + n)/\sqrt{mn})</math> If <math>m = n = 1</math>: <math>t(t - 2)</math> ||
|-
| rank of normalized Laplacian matrix || <math>m + n - 1</math> ||
|-
| eigenvalues (roots of characteristic polynomial) || 0 (1 time), <math>(m + n)/\sqrt{mn}</math> (1 time), 1 (<math>m + n - 2</math> times) Note that the eigenvalue 1 disappears if <math>m = n = 1</math> ||
|}

Star

2014-05-25T23:52:24Z

Vipul:

==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. 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> 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> 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> 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> 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) ||
|}

Complete bipartite graph

2014-05-25T23:41:20Z

Vipul: /* Laplacian matrix */

{{undirected graph family}}

==Definition==

Suppose <matH>m,n</math> are positive integers. The '''complete bipartite graph''' <math>K_{m,n}</math> is an [[undirected graph]] defined as follows:

# Its vertex set is a disjoint union of a subset <math>A</math> of size <math>m</math> and a subset <math>B</math> of size <math>n</math>
# Its edge set is defined as follows: every vertex in <math>A</math> is adjacent to every vertex in <math>B</math>. However, no two vertices in <math>A</math> are adjacent to each other, and no two vertices in <math>B</math> are adjacent to each other.

Note that <math>K_{m,n}</math> and <math>K_{n,m}</math> are isomorphic, so the complete bipartite graph can be thought of as parametrized by ''unordered pairs'' of (possibly equal, possibly distinct) positive integers.

==Explicit descriptions==

===Adjacency matrix===

If we order the vertices so that <math>A</math> makes up the first <math>m</math> vertices and <math>B</math> makes up the last <math>n</math> vertices, the adjacency matrix looks like the block matrix below:

<math>\begin{pmatrix} 0_{m \times m} & E_{m \times n} \\ E_{n \times m} & 0_{n \times n}\\\end{pmatrix}</math>

Here, <math>0_{a \times b}</math> is shorthand for the <math>a \times b</math> matrix with 0s for all its entries and
<math>E_{a \times b}</math> is shorthand for the <math>a \times b</math> matrix with 1s for all its entries.

==Particular cases==

* One special case of interest is where <math>\min \{ m, n \} = 1</math>. This case of interesting because in this case, the graph becomes a [[tree]].
* Another case of interest is where <math>m = n</math>. This case is interesting because the graph acquires additional symmetry and becomes a [[vertex-transitive graph]].

==Arithmetic functions==

===Size measures===

{| class="sortable" border="1"
! Function !! Value !! Explanation
|-
| [[size of vertex set]] || <math>m + n</math> || Follows from definition as disjoint union of subsets of size <matH>m,n</math>
|-
| [[size of edge set]] || <math>mn</math> || Follows from definition: the edges correspond to choosing one element each from <math>A</math> (size <math>m</math>) and <math>B</math> (size <math>n</math>)
|}

===Numerical invariants associated with vertices===

Note that if <matH>m = n</math>, the graph is a [[vertex-transitive graph]], but if <math>m \ne n</math>, the graph is not a vertex-transitive graph.

{| class="sortable" border="1"
! Function !! Value !! Explanation
|-
| [[degree of a vertex]] || <math>n</math> for vertices in <math>A</math> <math>m</math> for vertices in <math>B</math> ||
|-
| [[eccentricity of a vertex]] || For vertices in <math>A</math>: 1 if <math>m = 1</math>, 2 if <math>m > 1</math> For vertices in <math>B</math>: 1 if <math>n = 1</math>, 2 if <math>n > 1</math> ||
|}

===Other numerical invariants===

{| class="sortable" border="1"
! Function !! Value !! Explanation
|-
| {{arithmetic function value|clique number|2}} ||Follows from being non-empty and bipartite
|-
| [[independence number]] || <math>\max \{ m, n \}</math> || <math>A</math> and <math>B</math> are the only ''maximal'' independent sets, so the larger among their sizes gives the independence number.
|-
| {{arithmetic function value|chromatic number|2}} ||Follows from being non-empty and bipartite
|-
| [[radius of a graph]] || 1 if <math>\min \{ m,n \} = 1</math> 2 if <math>\min \{m,n \} > 1</math> || Follows from computation of eccentricity of each vertex above
|-
| [[diameter of a graph]] || 1 if <math>\max \{ m,n \} = 1</math> 2 if <math>\max \{ m,n \} > 1</math> || Follows from computation of eccentricity of each vertex above
|-
| [[odd girth]] || infinite || follows from being bipartite
|-
| [[even girth]] || infinite if <math>\min \{ m,n \} = 1</math> 4 if <math>\min \{ m,n \} > 1</math> ||
|-
|[[girth of a graph]] || infinite if <math>\min \{ m,n \} = 1</math> 4 if <math>\min \{ m,n \} > 1</math> ||
|}

==Algebraic theory==

===Adjacency matrix===

If we order the vertices so that <math>A</math> makes up the first <math>m</math> vertices and <math>B</math> makes up the last <math>n</math> vertices, the adjacency matrix looks like the block matrix below:

<math>\begin{pmatrix} 0_{m \times m} & E_{m \times n} \\ E_{n \times m} & 0_{n \times n}\\\end{pmatrix}</math>

Here, <math>0_{a \times b}</math> is shorthand for the <math>a \times b</math> matrix with 0s for all its entries and
<math>E_{a \times b}</math> is shorthand for the <math>a \times b</math> matrix with 1s for all its entries.

We can thus compute various algebraic invariants:

{| class="sortable" border="1"
! Algebraic invariant !! Value !! Explanation
|-
| [[characteristic polynomial of a graph|characteristic polynomial]] || <math>t^{m + n} - mnt^{m + n - 2} = t^{m + n - 2}(t^2 - mn)</math> ||
|-
| [[minimal polynomial of a matrix|minimal polynomial]] || if <math>m + n > 2</math>: <math>t^3 - mnt = t(t^2 - mn)</math> if <math>m = n = 1</math>: <math>t^2 - mn</math> ||
|-
| rank of adjacency matrix || 2 ||
|-
| eigenvalues (roots of characteristic polynomial) || 0 (multiplicity <math>m + n - 2</math>), <math>\sqrt{mn}</math> (multiplicity 1), <math>-\sqrt{mn}</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} nI_{m \times m} & -E_{m \times n} \\ -E_{n \times m} & mI_{n \times n} \\\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 - (m + n))(t - m)^{n-1}(t-n)^{m-1}</math> ||
|-
| minimal polynomial || If <math>m \ne n</math> and both are greater than 1: <math>t(t - m)(t - n)(t - (m + n))</math> If <math>m = n > 1</math>: <math>t(t - m)(t - 2m)</math> If <math>m = 1, n > 1</math>: <math>t(t - 1)(t - (n + 1))</math> If <math>m > 1, n = 1</math>: <math>t(t - 1)(t - (m + 1))</math> ||
|-
| rank of Laplacian matrix || <math>m + n - 1</math> ||
|-
| eigenvalues (roots of characteristic polynomial) || 0 (1 time), <math>m + n</math> (1 time), <math>m</math> (<math>n - 1</math> times), <math>n</math> (<math>m - 1</math> times). If <math>m = 1</math>, <math>n</math> disappears as an eigenvalue. If <math>n = 1</math>, <math>m</math> disappears as an eigenvalue. ||
|}

===Normalized Laplacian matrix===

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

<math>\begin{pmatrix} I_{m \times m} & (-1/\sqrt{mn}) E_{m \times n} \\ (-1/\sqrt{mn}) E_{n \times m} & 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 - (m + n)/\sqrt{mn})(t - 1)^{m+n-2}</math> Note that when <math>m = n</math>, this simplifies to <math>t(t - 2)(t - 1)^{2(m - 1)}</math> ||
|-
| minimal polynomial || <math>t(t - 1)(t - (m + n)/\sqrt{mn})</math> ||
|-
| rank of normalized Laplacian matrix || <math>m + n - 1</math> ||
|-
| eigenvalues (roots of characteristic polynomial) || 0 (1 time), <math>(m + n)/\sqrt{mn}</math> (1 time), 1 (<math>m + n - 2</math> times) ||
|}

Complete bipartite graph

2014-05-25T23:35:10Z

Vipul: /* Adjacency matrix */

{{undirected graph family}}

==Definition==

Suppose <matH>m,n</math> are positive integers. The '''complete bipartite graph''' <math>K_{m,n}</math> is an [[undirected graph]] defined as follows:

# Its vertex set is a disjoint union of a subset <math>A</math> of size <math>m</math> and a subset <math>B</math> of size <math>n</math>
# Its edge set is defined as follows: every vertex in <math>A</math> is adjacent to every vertex in <math>B</math>. However, no two vertices in <math>A</math> are adjacent to each other, and no two vertices in <math>B</math> are adjacent to each other.

Note that <math>K_{m,n}</math> and <math>K_{n,m}</math> are isomorphic, so the complete bipartite graph can be thought of as parametrized by ''unordered pairs'' of (possibly equal, possibly distinct) positive integers.

==Explicit descriptions==

===Adjacency matrix===

If we order the vertices so that <math>A</math> makes up the first <math>m</math> vertices and <math>B</math> makes up the last <math>n</math> vertices, the adjacency matrix looks like the block matrix below:

<math>\begin{pmatrix} 0_{m \times m} & E_{m \times n} \\ E_{n \times m} & 0_{n \times n}\\\end{pmatrix}</math>

Here, <math>0_{a \times b}</math> is shorthand for the <math>a \times b</math> matrix with 0s for all its entries and
<math>E_{a \times b}</math> is shorthand for the <math>a \times b</math> matrix with 1s for all its entries.

==Particular cases==

* One special case of interest is where <math>\min \{ m, n \} = 1</math>. This case of interesting because in this case, the graph becomes a [[tree]].
* Another case of interest is where <math>m = n</math>. This case is interesting because the graph acquires additional symmetry and becomes a [[vertex-transitive graph]].

==Arithmetic functions==

===Size measures===

{| class="sortable" border="1"
! Function !! Value !! Explanation
|-
| [[size of vertex set]] || <math>m + n</math> || Follows from definition as disjoint union of subsets of size <matH>m,n</math>
|-
| [[size of edge set]] || <math>mn</math> || Follows from definition: the edges correspond to choosing one element each from <math>A</math> (size <math>m</math>) and <math>B</math> (size <math>n</math>)
|}

===Numerical invariants associated with vertices===

Note that if <matH>m = n</math>, the graph is a [[vertex-transitive graph]], but if <math>m \ne n</math>, the graph is not a vertex-transitive graph.

{| class="sortable" border="1"
! Function !! Value !! Explanation
|-
| [[degree of a vertex]] || <math>n</math> for vertices in <math>A</math> <math>m</math> for vertices in <math>B</math> ||
|-
| [[eccentricity of a vertex]] || For vertices in <math>A</math>: 1 if <math>m = 1</math>, 2 if <math>m > 1</math> For vertices in <math>B</math>: 1 if <math>n = 1</math>, 2 if <math>n > 1</math> ||
|}

===Other numerical invariants===

{| class="sortable" border="1"
! Function !! Value !! Explanation
|-
| {{arithmetic function value|clique number|2}} ||Follows from being non-empty and bipartite
|-
| [[independence number]] || <math>\max \{ m, n \}</math> || <math>A</math> and <math>B</math> are the only ''maximal'' independent sets, so the larger among their sizes gives the independence number.
|-
| {{arithmetic function value|chromatic number|2}} ||Follows from being non-empty and bipartite
|-
| [[radius of a graph]] || 1 if <math>\min \{ m,n \} = 1</math> 2 if <math>\min \{m,n \} > 1</math> || Follows from computation of eccentricity of each vertex above
|-
| [[diameter of a graph]] || 1 if <math>\max \{ m,n \} = 1</math> 2 if <math>\max \{ m,n \} > 1</math> || Follows from computation of eccentricity of each vertex above
|-
| [[odd girth]] || infinite || follows from being bipartite
|-
| [[even girth]] || infinite if <math>\min \{ m,n \} = 1</math> 4 if <math>\min \{ m,n \} > 1</math> ||
|-
|[[girth of a graph]] || infinite if <math>\min \{ m,n \} = 1</math> 4 if <math>\min \{ m,n \} > 1</math> ||
|}

==Algebraic theory==

===Adjacency matrix===

If we order the vertices so that <math>A</math> makes up the first <math>m</math> vertices and <math>B</math> makes up the last <math>n</math> vertices, the adjacency matrix looks like the block matrix below:

<math>\begin{pmatrix} 0_{m \times m} & E_{m \times n} \\ E_{n \times m} & 0_{n \times n}\\\end{pmatrix}</math>

Here, <math>0_{a \times b}</math> is shorthand for the <math>a \times b</math> matrix with 0s for all its entries and
<math>E_{a \times b}</math> is shorthand for the <math>a \times b</math> matrix with 1s for all its entries.

We can thus compute various algebraic invariants:

{| class="sortable" border="1"
! Algebraic invariant !! Value !! Explanation
|-
| [[characteristic polynomial of a graph|characteristic polynomial]] || <math>t^{m + n} - mnt^{m + n - 2} = t^{m + n - 2}(t^2 - mn)</math> ||
|-
| [[minimal polynomial of a matrix|minimal polynomial]] || if <math>m + n > 2</math>: <math>t^3 - mnt = t(t^2 - mn)</math> if <math>m = n = 1</math>: <math>t^2 - mn</math> ||
|-
| rank of adjacency matrix || 2 ||
|-
| eigenvalues (roots of characteristic polynomial) || 0 (multiplicity <math>m + n - 2</math>), <math>\sqrt{mn}</math> (multiplicity 1), <math>-\sqrt{mn}</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} nI_{m \times m} & -E_{m \times n} \\ -E_{n \times m} & mI_{n \times n} \\\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 - (m + n))(t - m)^{n-1}(t-n)^{m-1}</math> ||
|-
| minimal polynomial || If <math>m \ne n</math>: <math>t(t - m)(t - n)(t - (m + n))</math> If <math>m = n</math>: <math>t(t - m)(t - 2m)</math> ||
|-
| rank of Laplacian matrix || <math>m + n - 1</math> ||
|-
| eigenvalues (roots of characteristic polynomial) || 0 (1 time), <math>m + n</math> (1 time), <math>m</math> (<math>n - 1</math> times), <math>n</math> (<math>m - 1</math> times) ||
|}

===Normalized Laplacian matrix===

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

<math>\begin{pmatrix} I_{m \times m} & (-1/\sqrt{mn}) E_{m \times n} \\ (-1/\sqrt{mn}) E_{n \times m} & 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 - (m + n)/\sqrt{mn})(t - 1)^{m+n-2}</math> Note that when <math>m = n</math>, this simplifies to <math>t(t - 2)(t - 1)^{2(m - 1)}</math> ||
|-
| minimal polynomial || <math>t(t - 1)(t - (m + n)/\sqrt{mn})</math> ||
|-
| rank of normalized Laplacian matrix || <math>m + n - 1</math> ||
|-
| eigenvalues (roots of characteristic polynomial) || 0 (1 time), <math>(m + n)/\sqrt{mn}</math> (1 time), 1 (<math>m + n - 2</math> times) ||
|}

2014-05-25T22:37:31Z

Vipul: /* Algebraic theory */

{{particular undirected graph}}

==Definition==

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.

==Explicit descriptions==

===Descriptions of vertex set and edge set===

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

Vertex set: <math>\{ 1,2,3,4,5,6 \}</math>

Edge set: <math>\{ \{ 1,4 \}, \{ 1,5 \}, \{ 1,6 \}, \{ 2,4 \}, \{ 2,5 \}, \{ 2,6 \}, \{ 3,4 \}, \{ 3,5 \}, \{ 3, 6 \} \}</math>

===Adjacency matrix===

With the above ordering of the vertices, the adjacency matrix is as follows:

<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 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)
|}

==Graph properties==

{| class="sortable" border="1"
! Property !! Satisfied? !! Explanation
|-
| [[satisfies property::connected graph]] || Yes ||
|-
| [[satisfies property::regular graph]] || Yes || <math>K_{m,n}</math> is regular if <math>m = n</math>
|-
| [[satisfies property::vertex-transitive graph]] || Yes || <math>K_{m,n}</math> is vertex-transitive if <math>m = n</math>
|-
| [[satisfies property::cubic graph]] || Yes ||
|-
| [[satisfies property::edge-transitive graph]] || Yes ||
|-
| [[satisfies property::symmetric graph]] || Yes ||
|-
| [[satisfies property::distance-transitive graph]] || Yes ||
|-
| [[satisfies property::bridgeless graph]] || Yes ||
|-
| [[satisfies property::strongly regular graph]] || Yes || The graph is a <math>\operatorname{srg}(6,3,0,3)</math>. In general, a complete bipartite graph <math>K_{m,n}</math> is strongly regular iff <math>m = n</math>, and in that case it is a <math>\operatorname{srg}(2m,m,0,m)</math>
|-
| [[satisfies property::bipartite graph]] || Yes || By definition of complete bipartite graph
|}

==Algebraic theory==

===Adjacency matrix===

The adjacency matrix is as follows:

<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>

This matrix is uniquely defined up to conjugation by permutations. Below are some important associated algebraic invariants:

{| class="sortable" border="1"
! Algebraic invariant !! Value !! Explanation
|-
| [[characteristic polynomial of a graph|characteristic polynomial]] || <math>t^6 - 9t^4</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>t^{m + n} - mnt^{m + n - 2} = t^{3 + 3} - (3)(3)t^{3 + 3 - 2} = t^6 - 9t^4</math>
|-
| [[minimal polynomial of a graph|minimal polynomial]] || <math>t^3 - 9t</math>|| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>t^3 - mnt = t^3 - (3)(3)t = t^3 - 9t</math>
|-
| rank of adjacency matrix || 2 || As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 2 (independent of <math>m,n</math>)
|-
| eigenvalues (roots of characteristic polynomial) || 0 (4 times), 3 (1 time), -3 (1 time)|| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (<math>m + n - 2 = 3 + 3 - 2 = 4</math> times), <math>\sqrt{mn} = \sqrt{(3)(3)} = 3</math> (1 time), <math>-\sqrt{mn} = -\sqrt{(3)(3)} = -3</math> (1 time)
|}

===Laplacian matrix===

The [[Laplacian matrix]] is as follows:

<math>\begin{pmatrix} 3 & 0 & 0 & -1 & -1 & -1 \\0 & 3 & 0 & -1 & -1 & -1 \\0 & 0 & 3 & -1 & -1 & -1 \\ -1 & -1 & -1 & 3 & 0 & 0 \\ -1 & -1 & -1 & 0 & 3 & 0 \\-1 & -1 & -1 & 0 & 0 & 3 \\\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 - 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>
|-
| 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> (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>)
|}

===Normalized Laplacian matrix===

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

<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>

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)^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>
|-
| 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>)
|}