Some signed graphs whose eigenvalues are main

作者:

Highlights:

• Let G be a graph. For a subset X of V (G), the switching σ of G is the signed graph Gσ obtained from G by reversing the signs of all edges between X and V (G) ∖ X. Let A(Gσ) be the adjacency matrix of Gσ. An eigenvalue of A(Gσ) is called a main eigenvalue if it has an eigenvector the sum of whose entries is not equal to zero. Two switching equivalent graphs share the same spectrum, while they may have different main eigenvalues. Akbari et al. (2021) conjectured that let G≠K2,K4∖{e}. Then there exists a switching σsuch that all eigenvalues of Gσ are main. Let Sn,k be the graph obtained from the complete graph Kn−r by attaching r pendent edges at some vertex of Kn−r. In this paper we prove that there exists a switching σ such that all eigenvalues of Gσ are main when G is a complete multipartite graph, or G is a harmonic tree, or G is a Sn,k. These results partly confirm a conjecture of Akbari et al.

摘要

•Let G be a graph. For a subset X of V (G), the switching σ of G is the signed graph Gσ obtained from G by reversing the signs of all edges between X and V (G) ∖ X. Let A(Gσ) be the adjacency matrix of Gσ. An eigenvalue of A(Gσ) is called a main eigenvalue if it has an eigenvector the sum of whose entries is not equal to zero. Two switching equivalent graphs share the same spectrum, while they may have different main eigenvalues. Akbari et al. (2021) conjectured that let G≠K2,K4∖{e}. Then there exists a switching σsuch that all eigenvalues of Gσ are main. Let Sn,k be the graph obtained from the complete graph Kn−r by attaching r pendent edges at some vertex of Kn−r. In this paper we prove that there exists a switching σ such that all eigenvalues of Gσ are main when G is a complete multipartite graph, or G is a harmonic tree, or G is a Sn,k. These results partly confirm a conjecture of Akbari et al.

论文关键词:Signed graph,Adjacency matrix,Main eigenvalue,Switching

论文评审过程:Received 12 October 2021, Revised 7 February 2022, Accepted 9 February 2022, Available online 23 February 2022, Version of Record 23 February 2022.

论文官网地址:https://doi.org/10.1016/j.amc.2022.127014