New results about the Inverse Eigenvalue Problem of a Graph

All graphs considered are simple and undirected. The Inverse Eigenvalue Problem of a Graph [Formula: see text] (IEP-G) aims to find all possible spectra for matrices whose [Formula: see text]entry, for [Formula: see text], is nonzero precisely when [Formula: see text] is adjacent to [Formula: see text]. A cluster in a graph [Formula: see text] is a pair of vertex subsets [Formula: see text], where [Formula: see text] is a maximal set of cardinality [Formula: see text] of independent vertices sharing the same set [Formula: see text] of [Formula: see text] neighbors. Let [Formula: see text] be a connected graph on [Formula: see text] vertices with a cluster [Formula: see text] and [Formula: see text] be a graph of order [Formula: see text]. Let [Formula: see text] be the connected graph obtained from [Formula: see text] and [Formula: see text] when the edges of [Formula: see text] are added to the edges of [Formula: see text] by identifying the vertices of [Formula: see text] with the vertices in [Formula: see text]. 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 [Formula: see text] is a graph of order [Formula: see text] having a clique of order [Formula: see text] and a cluster [Formula: see text], where [Formula: see text] and [Formula: see text], as well as, for the graph [Formula: see text], being [Formula: see text] as before. In particular, when [Formula: see text] is a graph obtained from [Formula: see text] by deleting a single edge [Formula: see text], 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.