DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): 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

PDF
Close