Signed Complete Graphs with Maximum Index

Abstract

Let Γ = (G, σ) be a signed graph, where G is the underlying simple graph and σ E(G) → {−, +} is the sign function on the edges of G. The adjacency matrix of a signed graph has −1 or +1 for adjacent vertices, depending on the sign of the edges. It was conjectured that if is a signed complete graph of order n with k negative edges, k ---lt--- n − 1 and has maximum index, then negative edges form K1,k. In this paper, we prove this conjecture if we confine ourselves to all signed complete graphs of order n whose negative edges form a tree of order k + 1. A [1, 2]-subgraph of G is a graph whose components are paths and cycles. Let Γ be a signed complete graph whose negative edges form a [1, 2]-subgraph. We show that the eigenvalues of Γ satisfy the following inequalities:

Keywords

• signed graph
• complete graph
• index
• 05c22
• 05c50