Induced subgraph and eigenvalues of some signed graphs

Abstract

Hao Huang proved the Sensitivity Conjecture in [Induced graphs of the hypercube and a proof of the Sensitivity Conjecture, Annals of Mathematics, 190 (2019), 949-955] by signed graph spectral method. The main result of that paper is every $(2^{n-1}+1)$-vertex induced subgraph of n-dimensional hypercube Q_n has maximum degree at least $\sqrt{n}$ by proving that Q_n has just two distinct adjacency eigenvalues $\sqrt{n}$ and $-\sqrt{n}$ with a signature. In this paper, we consider the eigenvalues of signed Cartesian product of bipartite graph $K_{a,b}$ and hypercube Q_n, signed Cartesian product of complete graph K_m and hypercube Q_n which contain Huang’s result when $a=b=1$ or m = 2. Let f(G) be the minimum of the maximum degree of an induced subgraph of G on $\alpha (G)+1$ vertices where $\alpha (G)$ is the independent number of G. Huang also asked the following question: Given a graph G with high symmetry, what can we say about f(G)? We study this question for k-ary n-cubes $Q_n^k,$ where 2-ary n-cube is Q_n. In this paper, we show that every $(2^{2n-1}+1)$-vertex induced subgraph of $Q_n^4$ has maximum degree at least $\sqrt{2n}$ ($f(Q_n^4)\ge \sqrt{2n}$) by proving that $Q_n^4$ has two eigenvalues which are either $\sqrt{2n}$ or $-\sqrt{2n}$ with a signature.

Keywords:

• Hypercube
• signed graph
• Cartesian product
• eigenvalue
• k-ary n-cubes

1. Introduction

All graphs in this paper are undirected and simple. A signed graph $\Gamma =(G,\sigma )$ is a graph $G=(V,E),$ with vertex set V and edge set E, together with a function $\sigma :E\to \{+1,-1\}$ assigning a positive or negative sign to each edge. The (unsigned) graph G is said to be the underlying graph of Γ, while the function σ is called the signature of Γ. The adjacency matrix of Γ is defined to be a $(0,\pm 1)$-matrix $A(\Gamma )=(a_{ij}^{\sigma }),$ where $a_{ij}^{\sigma }=\sigma (v_i{v}_j)$ if v_i and v_j are adjacent, and 0 otherwise. For an unsigned graph G, we use $\Delta (G)$ to denote the maximum degree of it. Let A be a square matrix and ${\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_s$ are its pairwise distinct eigenvalues with multiplicities $k_1,k_2,\cdots ,k_s.$ The set of eigenvalues with multiplicities of A will be denoted by $$\mathit{Spec}(A)=\left(\begin{array}{cccc}{\lambda }_1& {\lambda }_2& \cdots & {\lambda }_s\\ k_1& k_2& \cdots & k_s\end{array}\right).$$

Denote the Cartesian product of two graphs G and H by $G\square H$ with $V(G\square H)=V(G)\times V(H)$ and two vertices (u₁, v₁) and (u₂, v₂) are adjacent if and only if either u₁ = u₂ and $v_1{v}_2\in E(H),$ or v₁ = v₂ and $u_1{u}_2\in E(G).$ It is known that the hypercube Q_n can be constructed iteratively by Cartesian product, that is, Q₁=k₂ and for $n\ge 2,Q_n=Q_1\square Q_{n-1}.$ Motivated by this fact, in this paper, we consider the Cartesian product of bipartite graph $K_{a,b}$ and hypercube $Q_{n-1},$ complete graph K_m and hypercube $Q_{n-1}.$

In 2019, Huang [7] proved the Sensitivity Conjecture by considering the eigenvalues of signed hypercube.

Theorem 1.1

(Huang [7], 2019). For every integer $n\ge 1$. The hypercube Q_n with a signature has just two distinct adjacency eigenvalues $\sqrt{n}$ and $-\sqrt{n}$. The maximum degree of every $(2^{n-1}+1)$-vertex induced subgraph of Q_n is at least $\sqrt{n}.$

The eigenvalues of signed graphs have been widely studied. Signed graphs with two (distinct) eigenvalues have been widely considered in [3, 6, 8, 10, 11].

In this paper, the eigenvalues of the signed Cartesian product of bipartite graph $K_{a,b}$ and hypercube Q_n, complete graph K_m and hypercube Q_n, which generalize Huang’s result when $a=b=1$ or m = 2.

The study of $f(Q_n)$ starts from a 1988 paper by Chung, Füredi, Graham, and Seymour [1]. Dong [2] studied $f(H(n,k))$ where H(n, k) is the Hamming graph. We study this question for 4-ary n-cube $Q_n^4.$ In this paper, we show that every $(2^{2n-1}+1)$-vertex induced subgraph of $Q_n^4$ has maximum degree at least $\sqrt{2n}$ ($f(Q_n^4)\ge \sqrt{2n}$) by proving that $Q_n^4$ has two eigenvalues which are either $\sqrt{2n}$ or $-\sqrt{2n}$ with a signature.

2. Preliminaries

Lemma 2.1

(Cauchy’s Interlace Theorem [9], 2005). Let A be a symmetric n × n matrix, and B be a m × m principle submatrix of A, for some $m\le n$. If the eigenvalues of A are ${\lambda }_1\ge {\lambda }_2\cdots \ge {\lambda }_n$, and the eigenvalues of B are ${\mu }_1\ge {\mu }_2\cdots \ge {\mu }_n$, then for all $1\le i\le m,$ $${\lambda }_i\ge {\mu }_i\ge {\lambda }_{i+n-m}.$$

Cauchy’s Interlace Theorem is a direct consequence of the Courant-Fischer-Weylmin-max principle [1].

Lemma 2.2

(Huang [7], 2019). Suppose H is an m-vertex undirected graph, and A is a symmetric matrix whose entries are in $\{0,\pm 1\}$ and whose rows and columns are indexed by V(H), and whenever u and v are non-adjacent in H, $A_{u,v}=0$. Then, $$\Delta (H)\ge {\lambda }_1:={\lambda }_1(A).$$

Lemma 2.3

(Hong et al. [5], 2020). Let $\Gamma =(G,\sigma )$ be a connected signed graph of order n with k nonnegative adjacency eigenvalues ${\lambda }_1(\Gamma )\ge {\lambda }_2(\Gamma )\ge \cdots \ge {\lambda }_k(\Gamma )\ge 0$. If H is an $(n-k+1)$-vertex induced subgraph of G, then $\Delta (H)\ge \lceil {\lambda }_k(\Gamma )\rceil .$

Lemma 2.4

(Hou et al. [6]). Let G be a d-regular graph and $A_{\sigma }$ be the adjacency matrix of a signed graph $\Gamma =(G,\sigma )$. If $A_{\sigma }^2=dI$ then $|N(u)\cap N(v)|$ is even for any two distinct vertices u and v of G.

3. Cartesian product of graphs

In the following, we denote by A₁ the adjacency matrix of a signed graph $\Gamma =(G,\sigma )$ and define a sequence of symmetric square matrices iteratively as follows: $$A_{n+1}=\left(\begin{array}{cc}{A}_n& I\\ I& -A_n\end{array}\right)(n\ge 1).$$ Note that A₂ is the adjacency matrix of $G\square K_2$ with a signature and $A_{n+1}$ is the adjacency matrix of $G\square Q_n$ with a signature.

Proposition 3.1.

If $$\mathit{Spec}(A_1^2)=\left(\begin{array}{cccc}{\mu }_1^2& {\mu }_2^2& \cdots & {\mu }_s^2\\ k_1& k_2& \cdots & k_s\end{array}\right),$$ where ${\mu }_1^2>{\mu }_2^2>\cdots >{\mu }_s^2$ are pairwise different, then for $n\ge 1,$ $$\mathit{Spec}(A_{n+1})=\left(\begin{array}{ccccccc}\sqrt{{\mu }_1^2+n}& -\sqrt{{\mu }_1^2+n}& \sqrt{{\mu }_2^2+n}& -\sqrt{{\mu }_2^2+n}& \cdots & \sqrt{{\mu }_s^2+n}& -\sqrt{{\mu }_s^2+n}\\ k_1{2}^{n-1}& k_1{2}^{n-1}& k_2{2}^{n-1}& k_2{2}^{n-1}& \cdots & k_s{2}^{n-1}& k_s{2}^{n-1}\end{array}\right).$$

Proof.

We proceed by induction on n. For n = 1, $$\begin{array}{cc}|\lambda I-A_2|\hfill & =\left|\begin{array}{cc}\lambda I-A_1& -I\\ -I& \lambda I+A_1\end{array}\right|\hfill \\ \hfill & =\left|\right(\lambda I-A_1\left)\right(\lambda I+A_1)-I|\hfill \\ \hfill & =\left|\right({\lambda }^2-1)I-A_1^2|\hfill \\ \hfill & ={({\lambda }^2-1-{\mu }_1^2)}^{k_1}\cdots {({\lambda }^2-1-{\mu }_s^2)}^{k_s}\hfill \\ \hfill & ={(\lambda -\sqrt{{\mu }_1^2+1})}^{k_1}{(\lambda +\sqrt{{\mu }_1^2+1})}^{k_1}\cdots {(\lambda -\sqrt{{\mu }_s^2+1})}^{k_s}{(\lambda +\sqrt{{\mu }_s^2+1})}^{k_s}.\hfill \end{array}$$ Thus the result holds for n = 1.

Suppose $n\ge 2,$ we have $$\mathit{Spec}(A_n)=\left(\begin{array}{ccccc}\sqrt{{\mu }_1^2+n-1}& -\sqrt{{\mu }_1^2+n-1}& \cdots & \sqrt{{\mu }_s^2+n-1}& -\sqrt{{\mu }_s^2+n-1}\\ k_1{2}^{n-2}& k_1{2}^{n-2}& \cdots & k_s{2}^{n-2}& k_s{2}^{n-2}\end{array}\right).$$ So $$\begin{array}{cc}\hfill & |\lambda I-A_{n+1}|\hfill \\ \hfill & =\left|\begin{array}{cc}\lambda I-A_n& -I\\ -I& \lambda I+A_n\end{array}\right|\hfill \\ \hfill & =|(\lambda I-A_n)(\lambda I+A_n)-I|\hfill \\ \hfill & =|({\lambda }^2-1)I-A_n^2|\hfill \\ \hfill & ={({\lambda }^2-1-({\mu }_1^2+n-1))}^{k_1{2}^{n-1}}\cdots {({\lambda }^2-1-({\mu }_s^2+n-1))}^{k_s{2}^{n-1}}\hfill \\ \hfill & ={(\lambda -\sqrt{{\mu }_1^2+n})}^{k_1{2}^{n-1}}{(\lambda +\sqrt{{\mu }_1^2+n})}^{k_1{2}^{n-1}}\cdots {(\lambda -\sqrt{{\mu }_s^2+n})}^{k_s{2}^{n-1}}{(\lambda +\sqrt{{\mu }_s^2+n})}^{k_s{2}^{n-1}}.\hfill \end{array}$$

By the induction hypothesis, the Theorem is proved. □

Proposition 3.2.

Let $K_{a,b}$ be a complete bipartite graph and K_m be a complete graph. Then $\mathit{Spec}(A(K_{a,b}))=\left(\begin{array}{ccc}\sqrt{ab}& -\sqrt{ab}& 0\\ 1& 1& a+b-2\end{array}\right),$ $\mathit{Spec}(A(K_m))=\left(\begin{array}{cc}m-1& -1\\ 1& m-1\end{array}\right).$

From Propositions 3.1 and 3.2, we study the case of A₁ being the adjacent matrices of a bipartite graph or a complete graph.

Proposition 3.3.

Let A₁ be the adjacency matrix of a bipartite graph $K_{a,b}$. For $n\ge 1$, we have $$\mathit{Spec}(A_{n+1})=\{\begin{array}{c}\left(\begin{array}{cccc}\sqrt{n+ab}& \sqrt{n}& -\sqrt{n}& -\sqrt{n+ab}\\ 2^n& (a+b-2)2^{n-1}& (a+b-2)2^{n-1}& 2^n\end{array}\right),a+b\ge 3;\\ \left(\begin{array}{cc}\sqrt{n+1}& -\sqrt{n+1}\\ 2^n& 2^n\end{array}\right),a=b=1.\end{array}$$

Proposition 3.4.

Let A₁ be the adjacency matrix of complete graph K_m. For $n\ge 1$, we have $$\mathit{Spec}(A_{n+1})=\{\begin{array}{c}\left(\begin{array}{cccc}\sqrt{{(m-1)}^2+n}& \sqrt{n+1}& -\sqrt{n+1}& -\sqrt{{(m-1)}^2+n}\\ 2^{n-1}& 2^{n-1}(m-1)& 2^{n-1}(m-1)& 2^{n-1}\end{array}\right),m\ge 3;\\ \left(\begin{array}{cc}\sqrt{n+1}& -\sqrt{n+1}\\ 2^n& 2^n\end{array}\right),m=2.\end{array}$$

Following from Lemma 2.3, the maximum degree of the induced subgraph with half of their order and plus 1 vertices of $K_{a,b}\square Q_n$ or $K_m\square Q_n$ are present as the following two propositions.

Proposition 3.5.

For $n\ge 1$, let H be an arbitrary $(2^{n-1}(a+b)+1)$-vertex induced subgraph of $K_{a,b}\square Q_n$, then $$\Delta (H)\ge \{\begin{array}{c}\sqrt{n},a+b\ge 3;\hfill \\ \sqrt{n+1},a=b=1.\hfill \end{array}$$

Proposition 3.6.

For $n\ge 1$, let H be an arbitrary $(m{2}^{n-1}+1)$-vertex induced subgraph of $K_{a,b}\square Q_n$, then $$\Delta (H)\ge \sqrt{n+1}$$

From the above four Propositions, Huang’s result in Theorem 1.1 can be deduced when $a=b=1$ or m = 2.

4. k-Ary n-cubes

For positive integer n, let $[n]=\{1,2,\cdots ,n\}$ and ${[n]}_0=\left\{0\right\}\cup [n].$ The k-ary n-cube $Q_n^k$ ($k\ge 2$ and $n\ge 1$) is a graph with vertex set $\{u_1{u}_2\cdots u_n|0\le u_i\le k-1,1\le i\le n\}.$ Two vertices $u_1{u}_2\cdots u_n$ and $v_1{v}_2\cdots v_n$ are adjacent if and only if there exists an integer j with $1\le j\le n,$ such that $u_j=v_j\pm 1(\mathit{mod}k)$ and u_l = v_l for every $l\in [n]\setminus \left\{j\right\}.$ Obviously, $Q_1^k$ is a cycle of length k, $Q_n^2$ is an n-dimensional hypercube Q_n, $Q_n^k$ is n-regular if k = 2 or 2n-regular if $k\ge 3.$

For every $i\in {[3]}_0,$ let $Q_n^4[i]$ be a subgraph of $Q_n^4$ induced by the vertices labeled by $u_1{u}_2\cdots u_{n-1}i.$ It is clear that each $Q_n^4[i]$ is isomorphic to $Q_{n-1}^4[i]$ for $0\le i\le 3.$

With suitable labeling of vertices, the adjacent matrix of $Q_1^4\cong C_4$ with one negative edge can be represented as $$A_1=\left(\begin{array}{cccc}0& -1& 0& 1\\ -1& 0& 1& 0\\ 0& 1& 0& 1\\ 1& 0& 1& 0\end{array}\right).$$

For $n\ge 2,$ We define a sequence of symmetric square matrices iteratively as follows: $$A_n=\left(\begin{array}{cccc}{A}_{n-1}& I& 0& I\\ I& -A_{n-1}& I& 0\\ 0& I& A_{n-1}& -I\\ I& 0& -I& -A_{n-1}\end{array}\right).$$

Clearly, A_n is the adjacent matrix of $Q_n^4$ with a signature.

Theorem 4.1.

For $n\ge 1,\mathit{Spec}(A_n)=\left(\begin{array}{cc}\sqrt{2n}& -\sqrt{2n}\\ 2^{2n-1}& 2^{2n-1}\end{array}\right).$

Proof.

Note that $A_1^2=2I$ and $A_n^2=A_{n-1}^2+2I.$ By induction, $A_n^2=2nI.$ Therefore, the eigenvalues of A_n are either $\sqrt{2n}$ or $-\sqrt{2n}.$ Since $Tr[A_n]=0,$ we know that A_n has exactly half of the eigenvalues being $\sqrt{2n}$ and the rest being $-\sqrt{2n}.$ □

For $k\ge 3,$ note that $00\cdots 01$ is the only common neighbor of $00\cdots 00$ and $00\cdots 02.$ So for $k\ge 3,Q_n^k$ has just two distinct eigenvalues $\sqrt{2n}$ and $-\sqrt{2n}$ if and only if k = 4 by Lemma 2.3.

Theorem 4.2.

For $n\ge 1$, let H be an arbitrary $(2^{2n-1}+1)$-vertex induced subgraph of $Q_n^4$, then $\Delta (H)\ge \sqrt{2n}$. Moreover, $f(Q_n^4)\ge \sqrt{2n}.$

Proof.

Let $V_0=\{u_1{u}_2\cdots u_n|u_1+u_2+\cdots u_n=0(\mathit{mod}2)\}$ and $V_1=\{u_1{u}_2\cdots u_n|u_1+u_2+\cdots u_n=1(\mathit{mod}2)\}.$ By definition of $Q_n^4,$ V₀ and V₁ are two independent sets of $Q_n^4$ and $V(Q_n^4)=V_0\cup V_1.$ Since $Q_n^4$ is 2n-regular, $\alpha (Q_n^4)=\frac{|V(Q_n^4)|}{2}.$ Note that $|V(H)|=\frac{|V(Q_n^4)|}{2}+1=\alpha (Q_n^4)+1.$ By Lemma 2.3, $\Delta (H)\ge \sqrt{2n}.$ Since the arbitrarity of H, $f(Q_n^4)\ge \sqrt{2n}.$ □

The inequality of $f(Q_n^4)\ge \sqrt{2n}$ holds for n = 1. It is easy to check that $f(Q_2^4)=3>\sqrt{4}=2.$ For general n, $f(Q_n^4)$ maybe linear on n. For a k-regular graph G with high symmetry, the best lower bound of f(G) is $\sqrt{2k}$ by the above spectral method of signed graph.

5. Concluding remarks

The eigenvalues of signed graph $\Gamma =(G,\sigma )$ has been widely studied. Let $\rho (\Gamma )=\rho (G,\sigma )=\max \left\{\right|\lambda |:\lambda isan\mathit{eigenvalue}of\Gamma \}$ be the spectral radius of Γ. A weighing matrix of weight k and order n is a square n × n matrix W with 0, 1, -1, entries satisfying $W{W}^T=k{I}_n.$ Examining the trace of the square of the signed adjacency matrix, Gregory [4] proved the following.

Theorem 5.1.

If $\Gamma =(G,\sigma )$ is a signed graph, then $$\rho (\Gamma )\ge k,$$ where $\sqrt{k}$ is the average degree of G. Equality happens if and only if G is k-regular and $A(\Gamma )$ is a symmetric weighing matrix of weight k.

Huangs method can be also used to produce infinite families of regular graphs and signed adjacency matrices attaining equality in Theorem 5.1. If Γ is a k-regular signed graph with $A=A(\Gamma )$ be a symmetric weighing matrix of weight k, define $$B=\left(\begin{array}{cc}A& I\\ I& -A\end{array}\right),$$ then B is a symmetric weighing matrix of weight k + 1 and a signed adjacency matrix of an $(k+1)$-regular graph. By our construction in Section 4, define $$C=\left(\begin{array}{cccc}A& I& 0& I\\ I& -A& I& 0\\ 0& I& A& -I\\ I& 0& -I& -A\end{array}\right),$$ then C is a symmetric weighing matrix of weight 2k and a signed adjacency matrix of an 2k-regular graph.

Disclosure statement

No potential conflict of interest was reported by the author.

Additional information

Funding

The research is supported by Anhui Provincial Natural Science Foundation (No. 2108085MA02) and University Natural Science Research Project of Anhui Province (No. KJ2020A0001).