2023/03/17 by Díaz, Roberto C., Julio, Ana I.
#05C50 #05C76 #15A18 #15B57 #65F18 #Combinatorics (math.CO) #FOS: Mathematics #Spectral Theory (math.SP)
paper · doi:10.48550/arxiv.2303.09739
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 i≠ j, 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 \vert C\vert≥ 2 of independent vertices sharing the same set S of \vert S\vert neighbors. Let G be a connected graph on n vertices with a cluster (C, S) and H be a graph of order \vert C\vert. 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 \vert C\vert=n-k and \vert S\vert=r≤ k, as well as, for the graph G(Kn-k), being G as before. In particular, when G is a graph obtained from Kn by deleting a single edge ek∈ E(Kn), 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.