When can the components of NEPS of connected bipartite graphs be almost cospectral?
The non-complete extended \(p\)-sum (NEPS) with basis \(B (\subset\{0,1\}^n)\) of graphs \(G_1,\dots, G_n\) has the vertex set \(V(G_1)\times\cdots\times V(G_n)\) with vertices \((u_1,\dots, u_n)\) and \((v_1,\dots, v_n)\) being adjacent if and only if there exists \((\beta_1,\dots, \beta_n)\in B\) such that \(u_i\) is adjacent to \(v_i\) in \(G_i\) whenever \(\beta_i= 1\) and \(u_i= v_i\) otherwise. The author disproves the conjecture by the reviewer [Publ. Inst. Math., Nouv. Ser. 33(47), 29-33 (1983; Zbl 0522.05068)] that components of the NEPS of connected bipartite graphs are almost cospectral (cospectral up to the multiplicity of eigenvalue \(0\)). Some new necessary and sufficient conditions for NEPS of bipartite graphs to be itself bipartite are derived.
scientific article; zbMATH DE number 1462174
scientific article