# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

# Discussiones Mathematicae Graph Theory

Article in press

Authors:

S. Akbari, S. Dalvandi, F. Heydari and M. Maghasedi

Title:

Signed complete graphs with maximum index

Source:

Discussiones Mathematicae Graph Theory

Received: 2019-06-04, Revised: 2019-11-26, Accepted: 2019-11-26, https://doi.org/10.7151/dmgt.2276

Abstract:

Let $\Gamma=(G,\sigma)$ be a signed graph, where $G$ is the underlying simple graph and $\sigma : E(G) \longrightarrow \lbrace -,+\rbrace$ 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 $\Gamma$ is a signed complete graph of order $n$ with $k$ negative edges, $k<n-1$ and $\Gamma$ has maximum index, then negative edges form $K_{1,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 $\Gamma$ be a signed complete graph whose negative edges form a $[1,2]$-subgraph. We show that the eigenvalues of $\Gamma$ satisfy the following inequalities: $$-5 \leq \lambda_n \leq \cdots \leq \lambda_2 \leq 3.$$

Keywords:

signed graph, complete graph, index