Signed graphs with maximal index

DOI10.1016/J.DISC.2021.112463MaRDI QIDQ2032887zbMATH OpenOpenAlexFDO

Authors Arezoo Majidi, E. Ghorbani

Publication date 14 June 2021

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2101.01503

zbMATH Keywords

indexspectral radiussigned graphSeidel matrix

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Extremal problems in graph theory (05C35) Signed and weighted graphs (05C22)

Abstract: The index of a signed graph is the largest eigenvalue of its adjacency matrix. For positive integers $n$ and $mle{n}^2/4$, we determine the maximal index of complete signed graphs with $n$ vertices and $m$ negative edges. This settles (the corrected version of) a conjecture by Koledin and Stani'c (2017).

Recommendations

• Signed complete graphs with maximum index
• Connected signed graphs of fixed order, size, and number of negative edges with maximal index
• Signed graphs with maximum nullity two
• Signed graphs with stable maximum nullity at most two
• Signed graphs with small positive index of inertia
• Signed bicyclic graphs with minimal index
• Graphs with maximum Laplacian and signless Laplacian Estrada index
• The index of signed graphs with forbidden subgraphs
• Graphoidal signed graphs
• scientific article; zbMATH DE number 6315767

Cites work

• Connected signed graphs of fixed order, size, and number of negative edges with maximal index
• Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Lifts, discrepancy and nearly optimal spectral gap
• Open problems in the spectral theory of signed graphs
• Signed complete graphs with maximum index
• Spectra of graphs

Cited in

(14)

• Extremal spectral results related to spanning trees of signed complete graphs
• Connected signed graphs of fixed order, size, and number of negative edges with maximal index
• The largest eigenvalue of \(\mathcal{C}_k^-\)-free signed graphs
• The maximum index of signed complete graphs
• Minimizing the least Laplacian eigenvalue of signed complete graphs
• Unbalanced signed graphs with extremal spectral radius or index
• The index of signed graphs with forbidden subgraphs
• Maximizing the indices of a class of signed complete graphs
• On the spectral radius of unbalanced signed bipartite graphs
• Signed bicyclic graphs with minimal index
• Signed complete graphs with maximum index
• Minimizing the least eigenvalue of unbalanced signed unicyclic graphs with given girth or pendant vertices
• Ordering signed graphs with large index
• Complete signed graphs with largest maximum or smallest minimum eigenvalue

This page was built for publication: Signed graphs with maximal index

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2032887)