New results about the Inverse Eigenvalue Problem of a Graph

arXiv2303.09739MaRDI QIDQ6429904FDOQ6429904

Authors: Roberto C. Díaz, Ana I. Julio 

Publication date: 16 March 2023

Abstract: All graphs considered are simple and undirected. The Inverse Eigenvalue Problem of a Graph $G$ (IEP-G) aims to find all possible spectra for matrices whose $(i,j)-$entry, for $ieqj$, is nonzero precisely when $i$ is adjacent to $j$. A cluster in a graph $G$ is a pair of vertex subsets $(C,S)$, where $C$ is a maximal set of cardinality $vertCvertgeq2$ of independent vertices sharing the same set $S$ of $vertSvert$ neighbors. Let $G$ be a connected graph on $n$ vertices with a cluster $(C,S)$ and $H$ be a graph of order $vertCvert$. Let $G(H)$ be the connected graph obtained from $G$ and $H$ when the edges of $H$ are added to the edges of $G$ by identifying the vertices of $H$ with the vertices in $C$. In this paper, we construct a symmetric matrix with associated complete graph, which satisfies some interesting properties. This result is applied to obtain new sufficient conditions on the IEP-G, when $G$ is a graph of order $n$ having a clique of order $k$ and a cluster $(C,S)$, where $vertCvert=n-k$ and $vertSvert=rleqk$, as well as, for the graph $G(K_{n-k})$, being $G$ as before. In particular, when $G$ is a graph obtained from $K_n$ by deleting a single edge $e_{k}inE(K_n)$, we establish a necessary and sufficient condition on the IEP-G. Several illustrative example are given. The constructive nature of our results generate algorithmic procedures that always allow one to compute a solution matrix.

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Hermitian, skew-Hermitian, and related matrices (15B57) Graph operations (line graphs, products, etc.) (05C76) Numerical solutions to inverse eigenvalue problems (65F18)

This page was built for publication: New results about the Inverse Eigenvalue Problem of a Graph

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