## DIMACS TR: 2001-45

## On the components of NEPS of connected bipartite graphs

### Authors: Dragan Stevanovic

**
ABSTRACT
**

Back in 1983, D.~Cvetkovi\'c posed the conjecture that
the components of NEPS of connected bipartite graphs
are almost cospectral.
In 2000, we showed that this conjecture does not hold
for infinitely many bases of NEPS,
and we posed a necessary condition on the base of NEPS
for NEPS to have almost cospectral components.
At the same time,
D.~Cvetkovi\'c posed weaker version of his original conjecture
which claims that each eigenvalue of NEPS is also
the eigenvalue of each component of NEPS.

Here we prove this weaker conjecture,
give an upper bound on the multiplicity
of an eigenvalue of NEPS as an eigenvalue of its component,
give new sufficient condition for the almost cospectrality
of components of NEPS of connected bipartite graphs,
and characterize the bases of NEPS which satisfy this condition.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-45.ps.gz

DIMACS Home Page