Characterization of digraphs with three complementarity eigenvalues

DOI10.1007/S10801-023-01218-6MaRDI QIDQ6098209zbMATH OpenOpenAlexFDO

Authors Diego Bravo, Florencia Cubría, Marcelo Fiori, Vilmar Trevisan

Publication date 13 June 2023

Published in Journal of Algebraic Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

complementarity eigenvaluesdigraphspectral graph theory

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75) Eigenvalues, singular values, and eigenvectors (15A18)

Abstract: Given a digraph D, the complementarity spectrum of the digraph is defined as the set of complementarity eigenvalues of its adjacency matrix. This complementarity spectrum has been shown to be useful in several fields, particularly in spectral graph theory. The differences between the properties of the complementarity spectrum for (undirected) graphs and for digraphs, makes the study of the latter of particular interest, and characterizing strongly connected digraphs with a small number of complementarity eigenvalues is a non trivial problem. Recently, strongly connected digraphs with one and two complementarity eigenvalues have been completely characterized. In this paper we study strongly connected digraphs with exactly three elements in the complementarity spectrum, ending with a complete characterization. This leads to a structural characterization of general digraphs having three complementarity eigenvalues.

Review text

Spectral graph theory probes the relation among structural graph attributes and the spectral decomposition of some matrices associated with the graph. One of the tasks considered in this area was the characterization of a graph by its spectrum. Lately, the concept of complementarity eigenvalues for matrices has become the central point of attraction. It has been noted that this complementarity spectrum permits distinguishing more graphs than the usual eigenvalues, so a question that arises naturally is whether a graph is found by its complementarity eigenvalues. That is, whether only connected isomorphic graphs share their complementarity spectra. This question remains open as of today. It is worth pointing out that there exist examples of non-isomorphic digraphs with the same complementarity spectrum. But, several questions concerning digraph characterization through the complementarity spectrum remain unanswered. The authors of this paper address the problem of characterizing all the strongly connected digraphs with exactly three complementarity eigenvalues.

Recommendations

• Complementarity spectrum of digraphs
• Complementarity eigenvalue analysis of connected graphs
• The non-negative spectrum of a digraph
• Determining graphs by the complementary spectrum
• Digraphs with few eigenvalues

Cites work

• A new method for solving second-order cone eigenvalue complementarity problems
• A note on the spectral characterization of strongly connected bicyclic digraphs
• Complementarity eigenvalue analysis of connected graphs
• Complementarity spectrum of digraphs
• Complementary eigenvalues of graphs
• Cone-constrained eigenvalue problems: Theory and algorithms
• Digraphs with few eigenvalues
• Eigenvalue analysis of equilibrium processes defined by linear complementarity conditions
• Finite-Dimensional Variational Inequalities and Complementarity Problems
• GRAPHS WITH A SMALL NUMBER OF DISTINCT EIGENVALUES
• scientific article; zbMATH DE number 740754 (Why is no real title available?)
• scientific article; zbMATH DE number 3222645 (Why is no real title available?)
• scientific article; zbMATH DE number 3417498 (Why is no real title available?)
• Spectra of graphs
• Spektren endlicher Grafen
• The directional instability problem in systems with frictional contacts.

Cited in

(6)

• Complementarity eigenvalue analysis of connected graphs
• Complementarity spectrum of digraphs
• On cardinality of complementarity spectra of connected graphs
• Extremizing first eigenvalue of 3-colored digraphs made with given blocks
• Geometric and spectral analysis on weighted digraphs
• Some families of digraphs determined by the complementarity spectrum

This page was built for publication: Characterization of digraphs with three complementarity eigenvalues

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