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 determine all possible spectra of 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 let [Formula: see text] be a graph of order [Formula: see text]. Denote by [Formula: see text] the connected graph obtained from [Formula: see text] by adding the edges of [Formula: see text] to [Formula: see text], identifying the vertices of [Formula: see text] with the vertices in [Formula: see text]. In this paper, we construct a symmetric matrix associated with a complete graph that satisfies several interesting properties. This result is applied to obtain new sufficient conditions for the IEP-G when [Formula: see text] is a graph of order [Formula: see text] containing 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], where [Formula: see text] is as above. In particular, when [Formula: see text] is obtained from [Formula: see text] by deleting a single edge [Formula: see text], we establish a necessary and sufficient condition for the IEP-G. Several illustrative examples are given. The constructive nature of our results generates algorithmic procedures that always allow one to compute a solution matrix.