Threshold graphs are graphs whose node set can be partitioned into a clique and an independent set, with the additional property that for each pair of nodes, one’s neighborhood is a subset of the other’s neighborhood. Threshold graphs have been well-studied in graph theory, but not much is known about multigraphs that are underlying threshold. Proper threshold graphs are those in which all nodes in the independent set have the same degree. In this paper, we present a formula for the eigenvalues of a particular class of multigraphs that are underlying proper threshold.
A graph \(\mathit{G}\) is a finite, nonempty set of objects called vertices (nodes) together with a (possibly empty) set of unordered pairs of distinct vertices of \(\mathit{G}\) called edges. The degree of a node is the number of edges incident on it, and a graph \(\mathit{G}\) is a regular graph if all of its nodes have the same degree. A multigraph has no loops, but may have multiple edges and is defined formally by specifying a graph \(\mathit{G}\) and assigning a multiplicity to each edge of \(\mathit{G}\). Any graph theory notation not defined here can be found in [1], and an introduction to matrices associated with graphs can be found at [2].
We define the multigraphs under consideration as follows:
Definition 1.1 (Split graphs and threshold graphs). (a) If the node set \(V\) of a graph \(G\) is the disjoint union of sets \(U\) and \(W\), where \(U\) is an independent set in \(G\) and the subgraph of \(G\) induced by \(W\) is complete, then \(G\) is called a split graph. The nodes in \(U\) are referred to as cone nodes, or simply as cones.
(b) Let \(N(a)\) be the neighborhood of node \(a\). If for any nodes \(a, b\) in a split graph \(G\), \(\deg(a)\,\le\,\deg(b)\) implies \(N(a)-\{b\}\,\subseteq\,N(b)-\{a\},\) then \(G\) is called a threshold graph.
(c) Let \(m(\{a,b\})\) denote the number of edges between nodes a and b. Let \(M\) be a multigraph with \(G\) in (2) as its underlying simple graph, such that \(m(a,c)\,\le\,m(b,c)\) for any \(c\,\in\,N(a)\) and \(c\,\in\,N(b)\), with \(N(a)-\{b\}\,\subseteq\,N(b)-\{a\}.\) We will refer to such a multigraph as an MT graph and consider only those graphs in which the multiple edges all have same multiplicity \(\mu\) and occur only between clique nodes.
Threshold graphs have degree sequence \(\mathbf{d}(G)=(v_{1}^{(n_{1})},v_{2}^{(n_{2})},…,v_{s}^{(n_{s})})\), where \(v_{i}\leqslant v_{i+1}\) for \(i=1,…,s-1\), and \(n_i\) is the multiplicity of \(v_i\) in the degree sequence. Since s is the total number of unique degree sequence terms, we say the (multi)graph has an even degree set if s is even, and an odd degree set if s is odd.
In Figure 1, the graph has 14 nodes with a clique of order 11 and 3 cones, denoted \(TG_{14;8^2,7}\), and degree sequence \(\Pi\,=\,(7,8^{2},10^{3},12,13^{7})\).
Based on the fact that the neighborhood nesting relationship is a defining property of the threshold graph, we apply the same property to the multithreshold discussion, but in the multiset sense. In other words, if one node dominates another (has a higher degree) then it must have a larger neighborhood and be adjacent to every node at least as many times.
If a threshold graph has all cone nodes of equal degree, it is a proper threshold graph. When every edge within the clique has multiplicity \(\mu\), we denote these multigraphs \(MT_{{n;{{(v_1)}}^{c}}}^{(\mu)}\), where \(n\) indicates the total number of nodes where every edge within the clique has multiplicity \(\mu\) and \({v_1}^c\) indicates c cones of degree \({v_1}\). In this paper, all the cone nodes are adjacent to all but one node in the clique, which means that \(s\) is an even number (i.e., there are an even number of degree sequence terms in the underlying simple graphs). These multigraphs are denoted \(MT_{{n;{{(k-1)}}^{c}}}^{(\mu)}\), where \(k\) is the order of the clique and \((k-1)^c\) indicates \(c\) cones of degree \(k-1\). The threshold graph in Figure 2 has clique of order 9 and 3 cones, each of degree 8. Its degree sequence is \(\Pi\,=\,(8^{(4)},11^{(8)}).\) If the clique has all edges of multiplicity \(\mu\,=\,3\), the notation is \(MT_{{12;{{8}}^{3}}}^{(3)}\) and the degree sequence is \(\Pi\,=\,(8^{(3)},24^{(1)},27^{(3)})\).
If a proper threshold graph has some clique nodes that are not incident on multiedges, and the cones are adjacent only to the nodes in the multiclique , we have \(MT_{{n;{K_{v_1}}^{(n_1)}}}^{(\mu)}.\)
Definition 1.2. The adjacency matrix of a multigraph \(M\), denoted \(\mathit{A}(M)\), or simply \(\mathit{A}\,=\,(a_{ij})\), is defined by:
\[ a_{ij}=\begin{cases} 0,\ \text{if}\ i=j\\ m_{ij},\ \text{if}\ i\neq j,\ \text{where}\ m_{ij}\ \text{is the number of edges between nodes i and j.} \end{cases} \]The eigenvalues of \(\mathit{A}\) are called the eigenvalues of \(M\). If all eigenvalues of \(M\) are integers, then \(M\) is said to be integral.
Note that simple threshold graphs are defined by their degree sequences, which are uniquely realized by the threshold graph. However, this is not the case for multigraphs that are underlying threshold. Figure 4 depicts a multigraph with the same degree sequence as \(MT_{{8;{K_{4}}^{(2)}}}^{(5)}\) but without the neighborhood nesting, and not isomorphic to it.
The adjacency matrix of simple graphs has been well-studied, and they have many nice results because they are 0-1 matrices. However, adjacency matrices of multigraphs are not limited only to two entries. Here, we explore the characteristic polynomials and eigenvalues of the adjacency matrices of MT graphs. We note that in simple graphs, the coefficient of the \(\alpha^{n-2}\) term is the negative of the number of edges in the graph. We prove an analogous result for multigraphs.
Proposition 2.1. Let \(MT_{n;(k-1)^c}^{(\mu)}\) be an MT graph on a total of \(e\) edges. Suppose its characteristic polynomial in \(\alpha\) is given by
\[ \sum_{i=1}^{n}a_i\alpha^i. \]Then the coefficient of \(\alpha^{n-c}\) is
\[ a_{n-c}=c\big((n-c)-1\big)+\binom{n-c}{2}\mu^2. \]Proof. Consider the principal \(2\times2\) minors of the adjacency matrix of an MT graph that meets the assumptions of this proposition.
For these multigraphs, the only possible such minors are \(\begin{vmatrix}0&0\\0&0\end{vmatrix}\) which has \(\binom{n}{2}-e\) instances, \(\begin{vmatrix}0&1\\1&0\end{vmatrix}\), which has as many instances as the number of edges between the clique and the independent set, and \(\begin{vmatrix}0&\mu\\\mu&0\end{vmatrix}\), which has \(\binom{n-c}{2}\) instances. Thus \[a_{n-c}\,=\,0-\binom{n}{2}+e-\mu^2\left(\binom{n-c}{2}\right)\,=\,c((n-c)-1)+\binom{n-c}{2}\mu^2.\] \(\square\)
Our next theorem gives the adjacency spectra of the underlying proper threshold multigraphs having \(c\) cones and clique of order \(k\), each cone node of degree \(k-1\), and each clique edge of multiplicity \(\mu\), \(MT_{n;(k-1)^c}^{\mu}\). In other words, only one cone node is not adjacent to any clique nodes, and it is adjacent to all of the other clique nodes with multiplicity one.
Theorem 2.2. For multigraphs that are underlying proper threshold \(MT_{n;(k-1)^c}^{\mu}\), where \(\mu\) is the multiplicity of edges in the multiclique, the characteristic polynomial in \(\alpha\) is, in factored form,
\[ (-\alpha)^{c}\,(-(\alpha+\mu))^{k-2}\,\bigl(-\alpha^2+\mu(k-2)\alpha+(k-1)(c+\mu^2)\bigr). \]We remark that the above result can be generalized for any edge multiplicity incident on the clique node that is not adjacent to any of the cones. We denote this multigraph by \(MT_{n;(k-1)^c}^{\mu,z}\), where the \(k-1\) clique nodes adjacent to cones form a multiclique of multiplicity \(\mu\), and the one clique node not adjacent to cones is adjacent to the multiclique nodes with multiplicity \(z\).
Proof. The characteristic polynomial of the general adjacency matrix for \(MT_{n;(k-1)^c}^{\mu}\) is:
\[ \lvert\mathit{A}-\alpha\mathit{I}\rvert= \begin{vmatrix} -\alpha&0&\dots&0&1&1&1&\dots&1&0\\ 0&-\alpha&0&\dots&1&1&1&\dots&1&0\\ \vdots&0&-\alpha&0&\vdots&1&\dots&1&\dots&0\\ 0&0&\dots&\ddots&1&\dots&\vdots&1&\dots&0\\ 1&1&\dots&1&-\alpha&\mu&\mu&\dots&\mu&z\\ \vdots&1&\dots&1&\mu&-\alpha&\mu&\dots&\mu&z\\ \vdots&1&\dots&1&\mu&\vdots&-\alpha&\mu&\dots&z\\ \vdots&1&\dots&1&\mu&\dots&\mu&\ddots&\vdots&z\\ 1&1&\dots&1&\mu&\dots&\mu&\mu&-\alpha&z\\ 0&0&\dots&0&z&\dots&z&\dots&z&-\alpha \end{vmatrix} = \begin{vmatrix} M_{11}&M_{12}\\ M_{12}^{T}&M_{22} \end{vmatrix}, \]where \(M_{11}\) is \(c\times c\), \(M_{12}\) is \(c\times k\), \(M_{12}^T\) is \(k\times c\) and \(M_{22}\) is \(k\times k\). The proof proceeds by using elementary row operations to create an upper triangular matrix. We perform these in stages, noting that \(M_{11}\) is already in proper form.
Our first series of row operations transforms \(M_{12}\) into a submatrix having all zeros. Also, \(R_i\) represents row \(i\) of matrix \(\mathit{A}\).
Row operations–series 1: To each of the rows \(R_{c+1},R_{c+2},…,R_{c+k-1}\), add \(\frac{1}{\alpha}R_1,\frac{1}{\alpha}R_2,…,\frac{1}{\alpha}R_c\) to obtain the matrix:
\[ \begin{vmatrix} -\alpha&0&\dots&0&1&1&1&\dots&1&0\\ 0&-\alpha&0&\dots&1&1&1&\dots&1&0\\ \vdots&0&-\alpha&0&\vdots&1&\dots&1&\dots&0\\ 0&0&\dots&\ddots&1&\dots&\vdots&1&\dots&0\\ 0&0&\dots&0&A&B&B&\dots&B&z\\ \vdots&0&\dots&0&B&A&B&\dots&B&z\\ \vdots&0&\dots&0&B&\vdots&A&B&\dots&z\\ \vdots&0&\dots&0&B&\dots&B&\ddots&\vdots&z\\ 0&0&\dots&0&B&\dots&B&B&A&z\\ 0&0&\dots&0&z&\dots&z&\dots&z&-\alpha \end{vmatrix}, \]where \(A\,=\,\dfrac{c}{\alpha}-\alpha\) and \(B\,=\,\dfrac{c}{\alpha}+\mu\). The operations also will affect \(M_{22}\).
Row operations–series 2: The remainder of the row operations transform \(M_{22}\) into an upper triangular submatrix.
To each of the rows \(R_{c+1},R_{c+2},…,R_{c+k-1}\), add \(\frac{-B}{\mu}R_{c+k}\) (i.e., the bottom row) to obtain the matrix:
\[ \begin{vmatrix} -\alpha&0&\dots&0&1&1&1&\dots&1&0\\ 0&-\alpha&0&\dots&1&1&1&\dots&1&0\\ \vdots&0&-\alpha&0&\vdots&1&\dots&1&\dots&0\\ 0&0&\dots&\ddots&1&\dots&\vdots&1&\dots&0\\ 0&0&\dots&0&C&0&0&\dots&0&D\\ 0&0&\dots&0&0&C&0&\dots&0&D\\ \vdots&0&\dots&0&0&0&C&0&\dots&D\\ \vdots&0&\dots&0&0&\dots&0&\ddots&\vdots&D\\ 0&0&\dots&0&0&\dots&0&0&C&D\\ 0&0&\dots&0&z&\dots&z&\dots&z&-\alpha \end{vmatrix}, \]where \(C\,=\,A-B\,=-\alpha-\mu\) and \(D\,=\,\dfrac{B\alpha}{\mu}+z\).
Row operations-series 3: To the bottom row \(R_{c+k}\), add \(-\frac{z}{C}R_{c+1},-\frac{z}{C}R_{c+2},…,-\frac{z}{C}R_{c+k-1}\) to obtain the matrix:
\[ \begin{vmatrix} -\alpha&0&\dots&0&1&1&1&\dots&1&0\\ 0&-\alpha&0&\dots&1&1&1&\dots&1&0\\ \vdots&0&-\alpha&0&\vdots&1&\dots&1&\dots&0\\ 0&0&\dots&\ddots&1&\dots&\vdots&1&\dots&0\\ 0&0&\dots&0&C&0&0&\dots&0&D\\ 0&0&\dots&0&0&C&0&\dots&0&D\\ \vdots&0&\dots&0&0&0&C&0&\dots&D\\ \vdots&0&\dots&0&0&\dots&0&\ddots&\vdots&D\\ 0&0&\dots&0&0&\dots&0&0&C&D\\ 0&0&\dots&0&0&\dots&0&\dots&0&E \end{vmatrix}, \]where
\[ \begin{aligned} E\,=&(k-1)D-\alpha\\ =&(k-1)\left(z+\dfrac{B}{z}\right)\alpha-\alpha\\ =&\left(\dfrac{k-1}{\mu+\alpha}\right)(z^2+\mu\alpha+c)-\alpha\dfrac{\mu+\alpha}{\mu+\alpha}\\ =&\dfrac{-\alpha^2+\mu(k-2)\alpha+(k-1)(c+z^2)}{\mu+\alpha}. \end{aligned} \]Thus,
\[ \begin{aligned} \lvert\mathit{A}-\alpha\mathit{I}\rvert\,=&(-\alpha)^c\times (-(\alpha+\mu)^{k-1})\times\left(\dfrac{-\alpha^2+\mu(k-2)\alpha+(k-1)(c+z^2)}{\mu+\alpha}\right)\\ =&(-\alpha)^c\,(-(\alpha+\mu))^{k-2}\,(-\alpha^2+\mu(k-2)\alpha+(k-1)(c+z^2)). \end{aligned} \]\(\square\)
Remark 2.3. If we consider the more general multigraph \(MT_{n;(k-1)^c}^{\mu,z}\), where \(z\) is as described above, the same proof yields the characteristic polynomial in factored form
\[ (-\alpha)^{c}\,(-(\alpha+\mu))^{k-2}\,\bigl(-\alpha^2+\mu(k-2)\alpha+(k-1)(c+z^2)\bigr). \]In the previous section, we proved that the spectrum for \(MT_{n;(k-1)^c}^{\mu}\) multigraphs includes the roots of the quadratic \(-\alpha^2+\mu(k-2)\alpha+(k-1)(c+\mu^2)\), where \(\mu\) is the multiplicity of the multiedges in the clique, \(k\) is the order of the clique, and \(c\) is the number of cones. Since the other \(n-2\) eigenvalues are integers, when the roots of the quadratic are integers, the multigraphs are integral.
There is an infinite set of \(MT_{n;(k-1)^c}^{\mu}\) multigraphs that are integral. By the quadratic formula, \(-\alpha^2+\mu(k-2)\alpha+(k-1)(c+\mu^2)\) has roots
\[ \dfrac{-\mu(k-2)\,\pm\,\sqrt{h}}{-2}, \]where \(h\,=\,(\mu(k-2))^2+4(k-1)(c+\mu^2)\,=\,k^2\mu^2+4c(k-1)\) (*). In order for the fraction to be an integer, the numerator must be an even number, i.e., the parity of the two terms in the numerator must be the same. Thus, if the discriminant is an odd (even) perfect square, we need to establish that \(\mu(k-2)\) also is odd (even).
Theorem 3.1. All multigraphs \(MT_{n;(k-1)^c}^{\mu}\) for which \(h\) (as described above) are integral if and only if \(h\) is a perfect square.
Proof. We begin by establishing that, if \(h\) is a perfect square, the roots of the quadratic are integers if and only if \((k-2)\mu\) and \(h\) have the same parity. We first prove that if \((k-2)\mu\) is even, then \(h\) is even, \(h\,=\,(\mu(k-2))^2+4(k-1)(c+\mu^2)\).
Case 1. \(\mu\) is odd and \(k\) is even. Let \(\mu=2x+1\) and \(k=2y\), where \(x,y\in\mathbb{Z}\). Then
\[ h=((2y-2)(2x+1))^2+4(2y-1)(c+(2x+1)^2)=4\big(c(2y-1)+(2xy+y)^2\big), \]so \(h\) is even.
Case 2. \(\mu\) is even and \(k\) is even. Let \(\mu=2x\) and \(k=2y\). Then
\[ h=((2y-2)(2x))^2+4(2y-1)(c+(2x)^2)=16x^2(y-1)^2+4c(2y-1), \]so \(h\) is even.
Case 3. \(\mu\) is even and \(k\) is odd. Let \(\mu=2x\) and \(k=2y+1\). Then
\[ h=((2y-1)(2x))^2+4(2y)(c+4x^2)=4x^2(2y-1)^2+8y(c+4x^2), \]so \(h\) is even.
Thus, if \(\mu(k-2)\) is even, then \(h\) is even.
We now prove that if \(\mu(k-2)\) is odd, then \(h\) is odd. Since \(\mu(k-2)\) is odd, both \(\mu\) and \(k-2\) are odd, say, \(\mu=2x+1\) and \(k=2y+1\). Then \(h=((2y-1)(2x+1))^2+4(2y)(c+(2x+1)^2).\) The first term is odd squared, hence odd, and the second term is divisible by \(4\), hence even. Therefore, \(h\) is odd. Thus, if \(\mu(k-2)\) is odd, then \(h\) is odd. Therefore, \(h\) and \(\mu(k-2)\) have the same parity. Since \(h\) and \(\sqrt{h}\) have the same parity when \(h\) is a perfect square, it follows that when \(h\) is a perfect square, \(\sqrt{h}\) and \(\mu(k-2)\) have the same parity. Thus, the two eigenvalues given in (*) are integers if and only if \(h\) is a perfect square. Since this holds for all \(MT_{n;(k-1)^c}^{\mu}\) multigraphs where \(h\) is a perfect square, we obtain the desired result from Theorem 2.2 without further effort. \(\square\)
While proper MT graphs have been studied for their Laplacian and adjacency matrices, they have not been studied for other matrices associated with graphs and multigraphs, such as the Seidel matrix. In addition, underlying threshold graphs with the multiple edges housed in the clique have not been studies for non-proper cases, i.e. differing independent set degrees.
The authors would like to acknowledge support from the College of Arts & Sciences Dean’s Undergraduate STEM Research Grant, which receives some support from the New Jersey’s Office of the Secretary of Higher Education.