Bounding the largest eigenvalue of signed graphs

Abstract

In this study we derive certain upper bounds for the largest eigenvalue (called the index and denoted λ 1 ) of a signed graph. In particular, we prove the following upper bound: λ 12 ≤max⁡{d i m i −n i :1≤i≤n}, where d i is the vertex degree of i, m i =[Formula presented]∑ j∼i d j and n i =∑j∼i(|N iσ(ij) ∩N j |−||N iσ(ij) ∩N jσ(ij) |−|N iσ(ij) ∩N j−σ(ij) ||), with N i ,N i+ and N i− denoting the neighbourhood, the positive neighbourhood and the negative neighbourhood of a vertex i. In our proofs we use standard techniques transferred from the field of (unsigned, simple) graphs. Using the fact that all switching equivalent signed graphs share the same spectrum, we derive some more sophisticated bounds.