When can the components of NEPS of connected bipartite graphs be almost cospectral?
type: Item
instance of: scholarly article
title: When can the components of NEPS of connected bipartite graphs be almost cospectral?
zbMATH Open document ID: 0953.05044
DOI: 10.1016/S0024-3795(00)00061-6
author: Dragan Stevanović
published in: Linear Algebra and its Applications
publication date: 2000-08-29T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 1462174
zbMATH Keywords: non-complete extended \(p\)-sum
zbMATH Keywords: connected bipartite graphs
zbMATH Keywords: cospectral
reviewed by: Dragoš Cvetković
MaRDI profile type: Publication
cites work: Q5648382
cites work: Q3672040
cites work: Q4796614
cites work: Eigenspaces of graphs
cites work: When is NEPS of graphs connected?
Recommended article: On the components of NEPS of connected bipartite graphs
Recommended article: Cospectrality of complete bipartite graphs
Recommended article: On the construction of cospectral nonisomorphic bipartite graphs
Recommended article: Spectral characterizations of two families of nearly complete bipartite graphs
Recommended article: On the spectral radius of bipartite graphs which are nearly complete
Recommended article: Cospectrality of multipartite graphs
Recommended article: Constructing cospectral bipartite graphs
Recommended article: A connection between ordinary and Laplacian spectra of bipartite graphs
Recommended article: Spectral bisection of graphs and connectedness
Recommended article: On the largest eigenvalues of bipartite graphs which are nearly complete
description: scientific article; zbMATH DE number 1462174