Graph catalog: Families of graphs

Version: July 8, 2008

Index of families of graphs

$ C_s\Box C_s$     Cartesian product cycle and itself
$ H_s$     half-graph
$ C_t\circ K_s$     corona of $ C_t$ with $ K_s$ ($ s>1$ )
$ P_n$     path on $ n$ vertices
$ C_n$     $ n$-cycle
$ K_n$     complete graph on $ n$ vertices
$ K_{p,q}$     complete bipartite graph on $ p,q$ vertices
$ K_{n_1, n_2, \ldots, n_k}$     Complete multipartite graph
$ Q_s$     $ s$ th hypercube
$ T_m$     $ m$th supertriangle
$ W_n$     wheel on $ n$ vertices
$ N_s$     $ s$th necklace
$ K_m\cup K_{1,k}$     $ m,k$ -pineapple ( $ k\ge 2, m\ge 3$ )
    Moebius ladder
$ T$     tree
    unicyclic graph
    polygonal path
    claw-free block-clique (1-chordal) graph
$ \mathstrut\overline{\mathstrut C_n}$     complement of $ n$-cycle
$ \overline T$     complement of a tree
    complement of a 2-tree
$ L(K_n)$     line graph of complete graph
$ L(T)$     line graph of a tree
$ P_s\Box P_t$     Cartesian product of two paths
$ K_s \Box P_t$     Cartesian product of complete graph and path
$ C_s\Box P_t$     Cartesian product of a cycle and a path
$ K_s \Box K_t$     cartesian product of two complete graphs
$ C_s\Box K_t (s\ge 4)$     Cartesian product of a cycle and a complete graph
$ P_s \boxtimes P_t$     strong product of two paths
$ K_t\circ K_s$     corona of $ K_t$ by $ K_s$ ($ t\ge 2$ )
$ C_t\circ K_1$     corona of $ C_t$ with $ K_1$ ($ t$ -sun)

Main Index

Index of graphs
Description of graph entries
Graph operations
Parameter relationships
References
The catalog

This catalog provides information about the minimum rank and other graph parameters for families of connected graphs. The description of a family of graphs involves one or more parameters (often the order n of the graph). For specific small graphs, please consult the Graph catalog: Small graphs. For general background on the minimum rank problem, please see [FH]. Proofs of the results in the catalog can be found in the references cited in the catalog.

This catalog was developed through the American Institute of Mathematics workshop, "Spectra of Families of Matrices described by Graphs, Digraphs, and Sign Patterns," and is hosted by AIM. It is edited by Wayne Barrett, Jason Grout, Leslie Hogben, and Hein van der Holst. The web-page was designed by David Farmer.

Please refer any questions or comments about the content of the catalog, including corrections or suggestions for additional information, to Leslie Hogben (lhogben(())iastate.edu). Please refer any questions or comments about the operation of this web-site to David Farmer (farmer(())aimath.org).

AIM workshop participants: Francesco Barioli, Wayne Barrett, Avi Berman, Richard Brualdi, Steven Butler, Sebastian Cioaba, Dragos Cvetkovic, Jane Day, Louis Deaett, Luz DeAlba, Shaun Fallat, Shmuel Friedland, Chris Godsil, Jason Grout, Willem Haemers, Leslie Hogben, In-Jae Kim, Steve Kirkland, Raphael Loewy, Judith McDonald, Rana Mikkelson, Sivaram Narayan, Olga Pryporova, Uri Rothblum, Irene Sciriha, Bryan Shader, Wasin So, Dragan Stevanovic, Pauline van den Driessche, Hein van der Holst, Kevin Vander Meulen, Amy Wangsness, Amy Yielding.


Entries in the catalog

A typical entry in this catalog includes the following information for the graph or family of graphs.
Symbol name Common names/symbols are used to describe a graph G in the family. Sometimes a graph operation is used.
picture A picture of the graph, or a representative example from the family.
orderThe number of vertices in the graph
mr For a real symmetric matrix A, the graph of A, denoted G(A), is the graph with vertices {1,...,n } and edges { {i,j } | aij ≠ 0 and i ≠ j }
(note that the diagonal of A is ignored in determining G(A)).

The minimum rank of G is
  mr(G)=min{rank(A) : A ∈ Rn×n, AT=A, and G(A)=G}.

M The maximum nullity (= maximum multiplicity of an eigenvalue) of a real symmetric matrix A such that G(A)=G
field independent Minimum rank can be defined for symmetric matrices over any field. ``Yes" means the minimum rank of G is the same for all fields.
ξ A real symmetric matrix M satisfies the Strong Arnold Hypothesis provided there does not exist a nonzero symmetric matrix X satisfying:
  1. MX = 0,
  2. M ° X = 0,
  3. I ° X=0, where ° denotes the Hadamard (entrywise) product and I is the identity matrix.
The Colin de Veriere-type parameter ξ(G) is the maximum multiplicity of 0 as an eigenvalue among symmetric real matrices that satisfy
  1. G(A )=G and
  2. A satisfies the Strong Arnold Hypothesis.
ω The largest value of m for which G has a clique of order m (subgraph isomorphic to Km) is called the clique number of G and denoted by ω(G).
δ The minimum degree of a vertex of G is denoted by δ(G).
cc Clique covering number, or Cliquecover.
A set of subgraphs of G, each of which is a clique and such that every edge of G is contained in at least one of these cliques, is called a clique covering of G. The clique covering number of G, denoted by cc(G), is the smallest number of cliques in a clique covering of G.
diam The distance between two vertices in a graph G is the number of edges in a shortest path between them. The diameter of G, diam(G), is the maximum distance between any two vertices of G.
maxinducedpath The maximum number of edges in a path that is an induced subgraph of G.
Z Color-change rule:
If G is a graph with each vertex colored either white or black, u is a black vertex of G, and exactly one neighbor v of u is white, then change the color of v to black.

Given a coloring of G, the derived coloring is the result of applying the color-change rule until no more changes result. A zero forcing set for a graph G is a subset of vertices Z such that if initially the vertices in Z are colored black and the remaining vertices are colored white, the derived coloring of G is all black.

Z(G) is the minimum of |Z| over all zero forcing sets Z⊆ V(G).

α An induced subgraph H of a graph G is a coclique or independent set of vertices if H has no edges. The largest value of m for which a coclique with m vertices exists is called the vertex independence number of G and denoted by α(G).
Notes: Any other comments.

Graph operations

The following graph operations are used to construct families:

Parameter Relationships

The following relationships between the parameters are known:

References

[AIM] AIM Minimum rank - special graphs work group. Zero forcing sets and the minimum rank of graphs. Preprint.

[BFH] F. Barioli, S. Fallat, and L. Hogben. Computation of minimal rank and path cover number for graphs. Linear Algebra and Its Applications, 392: 289--303, 2004.

[BFH2] F. Barioli, S. Fallat, and L. Hogben. On the difference between the maximum multiplicity and path cover number for tree-like graphs. Linear Algebra and Its Applications 409: 13--31, 2005.

[BFH3] F. Barioli, S. Fallat, and L. Hogben. A variant on the graph parameters of Colin de Verdi`ere: Implications to the minimum rank of graphs. Electronic Journal of Linear Algebra, 13: 387--404, 2005.

[BHL2] W. Barrett, H. van der Holst and R. Loewy. Graphs whose minimal rank is two: The finite fields case. Electronic Journal of Linear Algebra, 14: 32--42, 2005.

[BvdHL] W. Barrett, H. van der Holst and R. Loewy. Graphs whose minimal rank is two. Electronic Journal of Linear Algebra, 11: 258--280, 2004.

[FH] S. Fallat and L. Hogben. The Minimum Rank of Symmetric Matrices Described by a Graph: A Survey. Preprint.

[H] L. Hogben. Spectral graph theory and the inverse eigenvalue problem of a graph. Electronic Journal of Linear Algebra, 14:12-31, 2005.

[H2] L. Hogben. Orthogonal representations, minimum rank, and graph complements. Preprint. Available at http://orion.math.iastate.edu/lhogben/research/Hogbenminrank07.pdf

[HvdH] L. Hogben and H. van der Holst. Forbidden minors for the class of graphs G with ξ(G) ≤ 2. To appear in Linear Algebra and Its Applications.

[JLD] C. R. Johnson and A. Leal Duarte. The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree. Linear and Multilinear Algebra 46: 139--144, 1999.

[JS] C. R. Johnson and C. M. Saiago. Estimation of the maximum multiplicity of an eigenvalue in terms of the vertex degrees of the graph of the matrix. Electronic Journal of Linear Algebra, 9:27--31, 2002.

Catalog of graphs

$ C_s\Box C_s$     Cartesian product cycle and itself
Order :$ s^2$
mr : $ s^2-(s+2\lfloor \frac s 2 \rfloor)$
M : $ (s+2\lfloor \frac s 2 \rfloor)$
field independent :yes
δ :4
Z : $ (s+2\lfloor \frac s 2 \rfloor)$
Notes : $ C_4\Box C_4$ is shown.
Reference: [ISU]

$ H_s$     half-graph
Order :$ 2s$
mr :$ s$
M :$ s$
field independent :no (see notes)
ω :$ s+1$
δ :1
cc :$ s$
Z :$ s$
Notes : mr$ ^{Z_2}(H_3)=4>3=$mr$ (H_3)$

Reference: [ISU]


$ C_t\circ K_s$     corona of $ C_t$ with $ K_s$ ($ s>1$ )
Order :$ st+t$
mr :$ 2t-2$
M :$ st-t+2$
field independent :yes
δ :$ s$
cc :$ 2t$
Diameter : $ \lfloor \frac t 2 \rfloor +2$
maxinducedpath :$ t$
Z :$ st-t+2$
Notes : $ C_5\circ K_2$ is shown.
Reference [ISU]

$ P_n$     path on $ n$ vertices
Order :$ n$
mr :$ n-1$
M :1
field independent :yes
ξ :1
ω :2
δ :1
cc :$ n-1$
Diameter :$ n-1$
maxinducedpath :$ n-1$
Z :1
α : $ \lceil \frac n 2\rceil$
Notes :$ P_5$ is displayed.

$ C_n$     $ n$-cycle
Order :$ n$
mr :$ n-2$
M :2
field independent :yes
ξ :2
ω :2 (for $ n>3$)
δ :2
cc :$ n$
Diameter : $ \lfloor \frac n 2\rfloor$
maxinducedpath :$ n-2$
Z :2
α : $ \lfloor \frac n 2\rfloor$
Notes :$ C_5$ is displayed. $ C_3=K_3$.

$ K_n$     complete graph on $ n$ vertices
Order :$ n$
mr :1 ($ n\ge 2$)
M :$ n-1$
field independent :yes
ξ :$ n-1$
ω :$ n$
δ :$ n-1$
cc :1
Diameter :1
maxinducedpath :1
Z :$ n-1$
α :1
Notes :$ K_5$ is displayed.

$ K_{p,q}$     complete bipartite graph on $ p,q$ vertices
Order :$ p+q$
mr :2
M :$ p+q-2$
field independent :yes
ξ : $ \min\{p,q\}+1$ (for $ 3\le\max\{p,q\}$)
ω :2
δ : $ \min\{p,q\}$
cc :$ pq$
Diameter :2
maxinducedpath :2
Z :$ p+q-2$
α : $ \max\{p,q\}$
Notes :$ K_{2,3}$ is displayed. $ K_{1,1}=K_1, K_{1,2}=P_3, K_{2,2}=C_2$.
References: [BvdHL], [BvdHL2], [BFH3]

$ K_{n_1, n_2, \ldots, n_k}$     Complete multipartite graph
Order : $ n_1+ n_2 +\dots +n_k$
mr : $ =\left\{ \begin{array}{cl} 0 & \mbox{if $k=1$;}  1 & \mbox{if $n_1=n_2=1, n_...
... & \mbox{if $n_1 >1, n_3 <3$;} 3 & \mbox{if $n_3 \geq 3$;}\end{array} \right.$
field independent :no
δ : $ n_1+ n_2 +\dots +n_k-\max\{n_1, n_2, \ldots, n_k\}$
Notes : $ K_{n_1, n_2, \ldots, n_k}= {\overline K}_{n_1} \vee \overline K_{n_2}\vee \cdots \vee {\overline K}_{n_k}$ where $ n_1 \geq n_2 \geq \cdots \geq n_k > 0$ .
$ K_{2,2,2}$ is shown.
$ Z(K_{3,3,3})=7>M(K_{3,3,3})$ .
$ M^{{\mathbb{Z}}_2}(K_{3,3,3})=7>M(K_{3,3,3})$ .
References:[BvdHL04], [FH]

$ Q_s$     $ s$ th hypercube
Order :$ 2^s$
mr : $ \mathstrut 2^{s-1}$
M : $ \mathstrut 2^{s-1}$
field independent :see notes
ω :2
δ :$ s$
cc : $ \mathstrut 2^{s-1} s$ (= # edges)
Diameter :$ s$
Z : $ \mathstrut 2^{s-1}$
α : $ \mathstrut 2^{s-1}$
Notes :$ Q_3$ is displayed.
$ Q_s=Q_{s-1}\Box K_2$ .
min rank is same over all fields of char 2 or order > 5
Reference:[AIM], [ISU]

$ T_m$     $ m$th supertriangle
Order : $ \frac 1 2 m(m+1)$
mr : $ \frac 1 2 m(m-1)$
M :$ m$
field independent :Yes
ξ :$ m$
ω :3
δ :$ n-7$ if $ m\ge 4$
cc : $ \frac 1 2 m(m-1)$
Diameter :$ m-1$
Z :$ m$
Notes :$ T_3$ is shown.
Reference: [AIM]

$ W_n$     wheel on $ n$ vertices
Order :$ n$
mr :$ n-3$
M :3
field independent :no (see notes)
ξ :3
ω :3
δ :3
cc :$ n-1$
Diameter :2
maxinducedpath :$ n-3$
Z :3
α : $ \lfloor \frac {n-1} 2\rfloor$
Notes :$ W_5$ is displayed.
$ W_n=C_{n-1}\vee K_1$.
mr $ ^{Z_2}(W_6)=4>3=$mr$ (W_6)$.
References: [H]; [BFH3, Thm 3.16] for $ \xi$.

$ N_s$     $ s$th necklace
Order :$ 4s$
mr :$ 3s-2$
M :$ s+2$
field independent :yes
ω :3
δ :3
cc :$ 3s$
Diameter : $ \lfloor\frac {3s} 2\rfloor$
maxinducedpath :$ 3s-2$
Z :$ s+2$
Notes :$ N_s$, the necklace with $ s$ diamonds is a 3-regular graph that can be constructed from a $ 3s$-cycle by appending $ s$ extra vertices. Each "extra" vertex is adjacent to 3 sequential cycle vertices. [ISU]

$ K_m\cup K_{1,k}$     $ m,k$ -pineapple ( $ k\ge 2, m\ge 3$ )
Order :$ m+k$
mr :$ 3$
M :$ k+m-3$
field independent :yes
ω :$ m$
δ :1
cc :$ k+1$
Diameter :2
maxinducedpath :2
Z :$ k+m-3$
α :$ k+1$
Notes : $ K_4\cup K_{1,3}$ is shown.

    Moebius ladder
Order :$ 2m$
mr :$ 2m-4$
M :4
field independent :no (see notes)
ξ :4
ω :2
δ :3
cc :$ 3m$ (= # edges)
Z :4
Notes :5th Möbius ladder is shown.
For this graph, minimum rank over $ R$ is 6 and over $ Z_2$ is 8.
Reference: [AIM], [ISU]

$ T$     tree
mr : $ =\vert T\vert-\Delta(T)$
M : $ =\Delta(T)=P(T)$
field independent :yes
ξ :2 (for $ T$ not a path)
ω :2
δ :1
cc :$ \vert T\vert-1$
Z :$ =M(T)$
Notes : $ \Delta(G) =\max\{p-q$ : there is a set of $ q$ vertices whose deletion leaves $ p$ paths}$ .$
$ P(T)$ = path cover number.
References: [JLD], [JS], [FH], [CDHMP], [AIM], [BFH3].

    unicyclic graph
mr : $ \vert G\vert-P(G)+\eta(G)$
M : $ P(G)-\eta(G)$
field independent :yes
Notes :$ \eta(G)=0$ unless the trimmed form of $ G$ is an $ m$ -sun ( $ =C_m\circ K_1$ ) with $ m>3$ and odd, in which case $ \eta(G)=1$ .

Reference: [BFH2], [FH], [ISU].


    polygonal path
mr :$ \vert G\vert-2$
M :2
field independent :yes
ξ :2
δ :2
Z :2
Notes :This is also called a 2-connected partial linear 2-tree, a linear singly edge articulated cycle (LSEAC) graph, and has been called a linear 2-tree (even though it need not be a 2-tree). It can be defined as a 2-connected graph G that can be embedded in the plane such that the graph obtained from the dual of G after deleting the vertex corresponding to the infinite face is a path. Reference: [HvdH07]

    claw-free block-clique (1-chordal) graph
mr := cc($ G$ )
M : $ =\vert G\vert-{\rm mr}(G)$
field independent :yes
cc :# of blocks
Z :$ =M(G)$
Notes :For the block-clique graph $ G$ shown,
mr($ G$ )=4.
This result requires claw-free or equivalently no vertex in more than 2 blocks.
A claw-free block-clique is the line graph of a tree.
reference: [AIM]

$ \mathstrut\overline{\mathstrut C_n}$     complement of $ n$-cycle
Order : $ n\qquad (n\ge 5)$
mr :3
M :$ n-3$
field independent :no (see notes)
ω : $ \lfloor\frac n 2\rfloor$
δ :$ n-3$
Diameter :2
maxinducedpath :3
Z :$ n-3$
α :2
Notes : $ \overline{C_6}=K_3\Box K_2$ is shown.
$ mr^{Z_2}(K_3\Box K_2)=4>3=mr(K_3\Box K_2).$
Reference: [AIM]

$ \overline T$     complement of a tree
Order :$ n$
mr :3 if $ n\ge 4$ and $ T\ne K_{1,n-1}$
M :$ n-3$ if $ n\ge 4$ and $ T\ne K_{1,n-1}$
field independent :no (see notes)
maxinducedpath :3 if $ n\ge 4,T\ne K_{1,n-1}$
Z : $ =M(\overline{T})$
α :2
Notes :G1205, which is the complement of G284, is shown.
mr(G1205)=3, mr$ ^{Z_2}$(G1205) = 4
$ {\rm mr}(\overline{K_{1,n-1}})=1$.
Reference: [AIM], [ISU]

    complement of a 2-tree
Order : $ n\qquad (n\ge 3)$
mr :see notes
field independent :no (see notes)
Notes :A 2-tree is obtained from a $ K_3$ by adding 0 or more vertices one at a time, where each added vertex is adjacent to two vertices already adjacent to each other.

If $ H$ is a 2-tree, then

$\displaystyle {\rm mr}({\overline H})=\left\{\begin{array}{ll}
0 & \mbox{ if }...
...x{ and $H$ does not have a vertex of degree } \vert H\vert-1.\end{array}\right.$

G840 is a linear 2-tree; its complement is G700.
mr(G700)=4, mr$ ^{Z_2}$ (G700)=5
Reference: [H2], [ISU]

$ L(K_n)$     line graph of complete graph
Order : $ \frac {n(n-1)} 2$
mr :$ n-2$
M : $ \frac {n(n-1)} 2 - n +2$
field independent :no (see notes)
δ :$ 2n-4$
Diameter :2
Z : $ \frac {n(n-1)} 2-n+2$
Notes :$ L(K_5)$ is shown
mr $ ^{Z_2}(L(K_5))=4>3=$ mr$ (L(K_5))$
Reference: [AIM], [ISU]

$ L(T)$     line graph of a tree
Order :$ \vert T\vert-1$
mr :$ \vert T\vert$ - number of pendent vertices of $ T$
M :number of pendent vertices of $ T$ - 1
field independent :yes
ω :maximum degree of vertex of $ T$
cc :$ \vert T\vert$ - number of pendent vertices of $ T$
Z :number of pendent vertices of $ T$ - 1
Notes :Reference: [AIM]

$ P_s\Box P_t$     Cartesian product of two paths
Order :$ st$
mr : $ (s-1)t\qquad (t\le s)$
M : $ t \qquad (t\le s)$
field independent :see notes
ω :2
δ :2
cc := # of edges
Diameter :$ s+t-2$
Z : $ t \qquad (t\le s)$
Notes : $ P_4\Box P_3$ is shown
mr( $ P_s\Box P_s$) is field independent. Reference: [AIM], [ISU]

$ K_s \Box P_t$     Cartesian product of complete graph and path
Order :$ st$
mr :$ s(t-1)$
M :$ s$
field independent :no (see notes)
ξ :$ s$
ω :$ s$
δ :$ s$
cc :$ st+t$
Diameter :$ t$
maxinducedpath : $ 2t-1 (s\ge 3)$
Z :$ s$
α :$ t$
Notes : $ K_3 \Box P_2$ is displayed.
mr $ ^{Z_2}(K_3 \Box P_2)=4>$
3=mr $ (K_3 \Box P_2)$
References: [AIM]

$ C_s\Box P_t$     Cartesian product of a cycle and a path
Order :$ st$
mr : $ st-\min\{s,2t\}$
M : $ \min\{s,2t\}$
field independent :no (see notes)
ω :2 ($ s\ge 4$)
δ :3
cc := # of edges (if $ s\ge 4$)
Diameter : $ \lfloor \frac s 2\rfloor+t-1$
Z : $ \min\{s,2t\}$
Notes : $ C_5\Box P_2$ is shown.
mr $ ^{Z_2}(C_3 \Box P_2)=4>$
3=mr $ (C_3 \Box P_2)$
Reference: [AIM]

$ K_s \Box K_t$     cartesian product of two complete graphs
Order :$ st$
mr :$ s+t-2$
M :$ st-s-t+2$
field independent :no (see notes)
ω :$ \max(s,t)$
δ :$ s+t-2$
Z :$ st-s-t+2$
Notes : $ K_3\Box K_3$ is shown.
mr $ ^{Z_2}(K_3 \Box K_2)=4>$
3=mr $ (K_3 \Box K_2)$
Reference: [AIM]

$ C_s\Box K_t (s\ge 4)$     Cartesian product of a cycle and a complete graph
Order :$ st$
mr :$ (s-2)t$
M :$ 2t$
field independent :no (see notes)
ω :$ t$
δ :$ t+1$
Z :$ 2t$
Notes : $ C_4\Box K_3$ is shown.
mr $ ^{Z_2}(C_4\Box K_2)=5>4=$ mr $ (C_4\Box K_2)$
Reference: [AIM], [ISU]

$ P_s \boxtimes P_t$     strong product of two paths
Order :$ st$
mr : $ (s-1)(t-1)$
M :$ s+t-1$
field independent :no (see notes)
ω :4
δ :3
cc : $ (s-1)(t-1)$
Diameter : $ \max(s,t)-1$
Z :$ s+t-1$
Notes : $ P_3 \boxtimes P_3$ is shown.
$ mr^{Z_2}(P_3\boxtimes P_3)=6>4=mr(P_3\boxtimes P_3)$
minimum rank same for all fields except $ Z_2$
Reference: [AIM],[ISU]

$ K_t\circ K_s$     corona of $ K_t$ by $ K_s$ ($ t\ge 2$ )
Order :$ st+t$
mr :$ t+1$
M :$ st-1$
field independent :yes
ω : $ \max(t,s+1)$
δ :$ s$
cc :$ t+1$
Diameter :3
maxinducedpath :3
Z :$ st-1$
α :$ t$
Notes : $ K_5\circ K_1$ is shown
References: [AIM]

$ C_t\circ K_1$     corona of $ C_t$ with $ K_1$ ($ t$ -sun)
Order :$ 2t$
mr : $ 2t-\lfloor \frac t 2 \rfloor$ (for $ t>3$ )
M : $ \lfloor \frac t 2 \rfloor$ (for $ t>3$ )
field independent :yes
ω :2 (for $ t>3$ )
δ :1
cc :$ 2t$ (for $ t>3$ )
Diameter : $ \lfloor \frac t 2 \rfloor +2$
maxinducedpath :$ t$
Z : $ \lceil \frac t 2\rceil$
α :$ t$
Notes : $ C_5\circ K_1$ is displayed.
$ Z(C_5\circ K_1)=3>2=M(C_5\circ K_1).$
mr( $ C_3\circ K_1$ )=4.
References: [BFH04], [BFH05], [AIM], [ISU]