Diameter of the NEPS of bipartite graphs
type: Item
instance of: scholarly article
title: Diameter of the NEPS of bipartite graphs
zbMATH Open document ID: 0966.05025
DOI: 10.1016/S0012-365X(00)00160-6
author: Richard A. Brualdi
author: J. Shen
published in: Discrete Mathematics
publication date: 2001-08-20T00:00:00Z
review text: The authors study the graph \(G=\text{NEPS}(G_1, G_2,\dots, G_n;{\mathcal B})\) (non-complete, extended \(p\)-sum), where (1) \(G_1,G_2,\dots, G_n\) are simple graphs with nonempty vertex sets; (2) \({\mathcal B}\) is a nonempty set of nonzero binary \(n\)-tuples with some property; (3) the vertex set of \(G\) is \(V(G_1)\times V(G_2)\times\cdots\times V(G_n)\); and (4) the edge set of \(G\) is defined in the paper. Assume that each of the graphs \(G_i\) is connected and bipartite. The authors prove that if the graph \(G=\text{NEPS}(G_1,\dots, G_n;{\mathcal B})\) is connected, then \(G\) has a diameter which does not exceed the sum of the diameters of \(G_i\). Moreover, they characterize the case of equality.
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 1565955
zbMATH Keywords: bipartite graphs
zbMATH Keywords: distance
zbMATH Keywords: diameter
reviewed by: Ferdinand Gliviak
MaRDI profile type: Publication
full work available at URL: s0012-365x(00)00160-6
OpenAlex ID: W1978583477
Wikidata QID: Q127740908
description: scientific article; zbMATH DE number 1565955