On the existence of non-golden signed graphs

Maurizio Brunetti

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 Sx(Γ, C)={|xrxs| | rs ∈ E(C)}. In this paper we show that non-golden bicyclic graphs with frustration index 1 exist for each n≥5.

Keywords


Signed Graph; Bicyclic Graph; Laplacian; Least Eigenvalue; Theta-Graph

Full Text:

PDF


DOI: http://dx.doi.org/10.1478/AAPP.96S2A2

Copyright (c) 2018 Maurizio Brunetti

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.