![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
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 -vertex induced subgraph of n-dimensional hypercube Qn has maximum degree at least
by proving that Qn has just two distinct adjacency eigenvalues
and
with a signature. In this paper, we consider the eigenvalues of signed Cartesian product of bipartite graph
and hypercube Qn, signed Cartesian product of complete graph Km and hypercube Qn which contain Huang’s result when
or m = 2. Let f(G) be the minimum of the maximum degree of an induced subgraph of G on
vertices where
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
where 2-ary n-cube is Qn. In this paper, we show that every
-vertex induced subgraph of
has maximum degree at least
(
) by proving that
has two eigenvalues which are either
or
with a signature.
1. Introduction
All graphs in this paper are undirected and simple. A signed graph is a graph
with vertex set V and edge set E, together with a function
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
-matrix
where
if vi and vj are adjacent, and 0 otherwise. For an unsigned graph G, we use
to denote the maximum degree of it. Let A be a square matrix and
are its pairwise distinct eigenvalues with multiplicities
The set of eigenvalues with multiplicities of A will be denoted by
Denote the Cartesian product of two graphs G and H by with
and two vertices (u1, v1) and (u2, v2) are adjacent if and only if either u1 = u2 and
or v1 = v2 and
It is known that the hypercube Qn can be constructed iteratively by Cartesian product, that is, Q1=k2 and for
Motivated by this fact, in this paper, we consider the Cartesian product of bipartite graph
and hypercube
complete graph Km and hypercube
In 2019, Huang [Citation7] proved the Sensitivity Conjecture by considering the eigenvalues of signed hypercube.
Theorem 1.1
(Huang [Citation7], 2019). For every integer . The hypercube Qn with a signature has just two distinct adjacency eigenvalues
and
. The maximum degree of every
-vertex induced subgraph of Qn is at least
The eigenvalues of signed graphs have been widely studied. Signed graphs with two (distinct) eigenvalues have been widely considered in [Citation3, Citation6, Citation8, Citation10, Citation11].
In this paper, the eigenvalues of the signed Cartesian product of bipartite graph and hypercube Qn, complete graph Km and hypercube Qn, which generalize Huang’s result when
or m = 2.
The study of starts from a 1988 paper by Chung, Füredi, Graham, and Seymour [Citation1]. Dong [Citation2] studied
where H(n, k) is the Hamming graph. We study this question for 4-ary n-cube
In this paper, we show that every
-vertex induced subgraph of
has maximum degree at least
(
) by proving that
has two eigenvalues which are either
or
with a signature.
2. Preliminaries
Lemma 2.1
(Cauchy’s Interlace Theorem [Citation9], 2005). Let A be a symmetric n × n matrix, and B be a m × m principle submatrix of A, for some . If the eigenvalues of A are
, and the eigenvalues of B are
, then for all
Cauchy’s Interlace Theorem is a direct consequence of the Courant-Fischer-Weylmin-max principle [Citation1].
Lemma 2.2
(Huang [Citation7], 2019). Suppose H is an m-vertex undirected graph, and A is a symmetric matrix whose entries are in and whose rows and columns are indexed by V(H), and whenever u and v are non-adjacent in H,
. Then,
Lemma 2.3
(Hong et al. [Citation5], 2020). Let be a connected signed graph of order n with k nonnegative adjacency eigenvalues
. If H is an
-vertex induced subgraph of G, then
Lemma 2.4
(Hou et al. [Citation6]). Let G be a d-regular graph and be the adjacency matrix of a signed graph
. If
then
is even for any two distinct vertices u and v of G.
3. Cartesian product of graphs
In the following, we denote by A1 the adjacency matrix of a signed graph and define a sequence of symmetric square matrices iteratively as follows:
Note that A2 is the adjacency matrix of
with a signature and
is the adjacency matrix of
with a signature.
Proposition 3.1.
If
where
are pairwise different, then for
Proof.
We proceed by induction on n. For n = 1,
Thus the result holds for n = 1.
Suppose we have
So
By the induction hypothesis, the Theorem is proved. □
Proposition 3.2.
Let be a complete bipartite graph and Km be a complete graph. Then
From Propositions 3.1 and 3.2, we study the case of A1 being the adjacent matrices of a bipartite graph or a complete graph.
Proposition 3.3.
Let A1 be the adjacency matrix of a bipartite graph . For
, we have
Proposition 3.4.
Let A1 be the adjacency matrix of complete graph Km. For , we have
Following from Lemma 2.3, the maximum degree of the induced subgraph with half of their order and plus 1 vertices of or
are present as the following two propositions.
Proposition 3.5.
For , let H be an arbitrary
-vertex induced subgraph of
, then
Proposition 3.6.
For , let H be an arbitrary
-vertex induced subgraph of
, then
From the above four Propositions, Huang’s result in Theorem 1.1 can be deduced when or m = 2.
4. k-Ary n-cubes
For positive integer n, let and
The k-ary n-cube
(
and
) is a graph with vertex set
Two vertices
and
are adjacent if and only if there exists an integer j with
such that
and ul = vl for every
Obviously,
is a cycle of length k,
is an n-dimensional hypercube Qn,
is n-regular if k = 2 or 2n-regular if
For every let
be a subgraph of
induced by the vertices labeled by
It is clear that each
is isomorphic to
for
With suitable labeling of vertices, the adjacent matrix of with one negative edge can be represented as
For We define a sequence of symmetric square matrices iteratively as follows:
Clearly, An is the adjacent matrix of with a signature.
Theorem 4.1.
For
Proof.
Note that and
By induction,
Therefore, the eigenvalues of An are either
or
Since
we know that An has exactly half of the eigenvalues being
and the rest being
□
For note that
is the only common neighbor of
and
So for
has just two distinct eigenvalues
and
if and only if k = 4 by Lemma 2.3.
Theorem 4.2.
For , let H be an arbitrary
-vertex induced subgraph of
, then
. Moreover,
Proof.
Let and
By definition of
V0 and V1 are two independent sets of
and
Since
is 2n-regular,
Note that
By Lemma 2.3,
Since the arbitrarity of H,
□
The inequality of holds for n = 1. It is easy to check that
For general n,
maybe linear on n. For a k-regular graph G with high symmetry, the best lower bound of f(G) is
by the above spectral method of signed graph.
5. Concluding remarks
The eigenvalues of signed graph has been widely studied. Let
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
Examining the trace of the square of the signed adjacency matrix, Gregory [Citation4] proved the following.
Theorem 5.1.
If is a signed graph, then
where
is the average degree of G. Equality happens if and only if G is k-regular and
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 be a symmetric weighing matrix of weight k, define
then B is a symmetric weighing matrix of weight k + 1 and a signed adjacency matrix of an
-regular graph. By our construction in Section 4, define
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
References
- Chung, F., Füredi, Z., Graham, R, Seymour, P. (1988). On induced subgraphs of the cube. J. Comb. Theory, Ser. A. 49(1): 180–187.
- Dong, D. (2021). On induced subgraphs of the Hamming graph. J. Graph Theory 96(1): 160–166.
- Ghasemian, E, Fath-Tabar, G. H. (2017). On signed graphs with two distinct eigenvalues. Filomat. 31(20): 6393–6400.
- D. A, G. (2012). Spectra of signed adjacency matrices, Queens-R.M.C. Discrete Mathematics Seminar, February 27. Available at: https://pdfs.semanticscholar.org/eb2e/078a4a4d8dcfeed9e86417e17ecbb91696e0.pdf.
- Hong, Z.-M., Lai, H.-J, Liu, J. (2021). Induced subgraphs of product graphs and a generalization of Huangs theorem. J. Graph Theory. 98(2): 285–308.
- Hou, Y., Tang, Z, Wang, D. (2019). On signed graphs with just two distinct adjacency eigenvalues. Discrete Math. 342(12): 111615.
- Huang, H. (2019). Induced graphs of the hypercube and a proof of the Sensitivity Conjecture. Ann. Math. 190: 949–955.
- Kee, J. M, Smyth, C. (2007). Integer symmetric matrices having all their eigenvalues in the interval [-2, 2]. J. Algebra. 317(1): 260–290.
- Fisk, S. (2005). A very short proof of Cauchys interlace theorem for eigenvalues of Hermitian matrices. Amer. Math. Monthly. 112(2): 118.
- Ramezani, F. (2022). Some regular signed graphs with only two distinct eigenvalues. Linear Multilinear Algebra. 70(3): 517–530.
- Stanić, Z. (2020). Spectra of signed graphs with two eigenvalues. Appl. Math. Comput. 364: 124627.