Connected signed graphs of fixed order, size, and number of negative edges with maximal index

Abstract

In this paper we focus on connected signed graphs of fixed number of vertices, positive edges and negative edges that maximize the largest eigenvalue (also called the index) of their adjacency matrix. In the first step we determine these signed graphs in the set of signed generalized theta graphs. Concerning the general case, we use the eigenvector techniques for getting some structural properties of resulting signed graphs. In particular, we prove that positive edges induce nested split subgraphs, while negative edges induce double nested signed subgraphs. We observe that our concept can be applied when considering balancedness of signed graphs (the property that is extensively studied in both mathematical and non-mathematical context).

Keywords:

• Signed graph
• adjacency matrix
• largest eigenvalue
• small perturbations
• nested graph

AMS Subject Classifications:

• 05C50

Acknowledgements

This work was partially supported by Serbian Ministry of Education, Science and Technological Development [project number 174012] and [project number 174033].

Notes

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by the National Natural Science Foundation of China [grant number 11101027], [grant number 11371193]; the Fundamental Research Funds for the Central Universities of China [grant number 2015JBM107]; the Beijing Higher Education Young Elite Teacher Project [grant number YETP0573].