On the existence of non-golden signed graphs

Abstract

A signed graph is a pair Γ=(G,σ), where G=(V(G), E(G)) is a graph and σ: E(G) → {+1, -1} is the sign function on the edges of G. For a signed graph we consider the least eigenvalue λ(Γ) of the Laplacian matrix defined as L(Γ)=D(G)-A(Γ), where D(G) is the matrix of vertices degrees of G and A(Γ) is the signed adjacency matrix. An unbalanced signed bicyclic graph is said to be golden if it is switching equivalent to a graph Γ satisfying the following property: there exists a cycle C in Γ and a  λ(Γ)-eigenvector x such that the unique negative edge pq of  Γ belongs to C and detects the minimum of the set S_x(Γ, C)={|x_rx_s| | rs ∈ E(C)}. In this paper we show that non-golden bicyclic graphs with frustration index 1 exist for each n≥5.