Induced subgraph and eigenvalues of some signed graphs

Abstract

AbstractHao 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 [Formula: see text]-vertex induced subgraph of n-dimensional hypercube Qn has maximum degree at least [Formula: see text] by proving that Qn has just two distinct adjacency eigenvalues [Formula: see text] and [Formula: see text] with a signature. In this paper, we consider the eigenvalues of signed Cartesian product of bipartite graph [Formula: see text] and hypercube Qn, signed Cartesian product of complete graph Km and hypercube Qn which contain Huang’s result when [Formula: see text] or m = 2. Let f(G) be the minimum of the maximum degree of an induced subgraph of G on [Formula: see text] vertices where [Formula: see text] 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 [Formula: see text] where 2-ary n-cube is Qn. In this paper, we show that every [Formula: see text]-vertex induced subgraph of [Formula: see text] has maximum degree at least [Formula: see text] ([Formula: see text]) by proving that [Formula: see text] has two eigenvalues which are either [Formula: see text] or [Formula: see text] with a signature.

Keywords

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