A convexity lemma and expansion procedures for bipartite graphs
type: Item
instance of: scholarly article
title: A convexity lemma and expansion procedures for bipartite graphs
zbMATH Open document ID: 0918.05085
author: Wilfried Imrich
author: Sandi Klavžar
published in: European Journal of Combinatorics
publication date: 1999-08-24T00:00:00Z
review text: Consider the hierarchy \(\text{H}\subset\text{M} \subset\text{PC}\) where H is the class of Hamming graphs, M the class of median graphs and PC the class of partial cubes. The best-known algorithms for recognizing whether a graph \(G\) is a member of the classes H, M and PC have respectively time complexity \(O(m)\), \(O(mn^{1/2})\) and \(O(mn)\) where \(m\) (resp. \(n\)) denotes the number of edges (resp. vertices) of \(G\). Using expansion procedures, the authors introduce the class AM of almost-median graphs and the class PM of semi-medians graphs. If we add the class ACC of so-called acyclic cubical complexes introduced recently, we obtain the following hierarchy: \(\text{H}\subset \text{ACC} \subset\text{M} \subset\text{AM}\subset \text{PM} \subset\text{PC}\). The authors begin with a convexity lemma which they then use to exhibit a new algorithm of complexity \(O(mn)\) for recognizing median graphs. The class PM is characterized and a new characterization of M by forbidden subgraphs is given.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1234997
zbMATH Keywords: recognition
zbMATH Keywords: bipartite graphs
zbMATH Keywords: Hamming graphs
zbMATH Keywords: median graphs
zbMATH Keywords: partial cubes
zbMATH Keywords: algorithms
zbMATH Keywords: complexity
zbMATH Keywords: expansion procedures
zbMATH Keywords: acyclic cubical complexes
zbMATH Keywords: convexity lemma
MaRDI profile type: Publication
Wikidata QID: Q60962152
OpenAlex ID: W2063958901
DBLP publication ID: journals/ejc/ImrichK98
DOI: 10.1006/EUJC.1998.0229
Recommended article: Convexity in Graphs and Hypergraphs
Recommended article: Q4529443
Recommended article: Convex Partitions of Graphs
Recommended article: Q3346357
Recommended article: On the bipartiteness constant and expansion of Cayley graphs
Recommended article: A convexity upper bound for the number of maximal bicliques of a bipartite graph
Recommended article: On the extension of bipartite to parity graphs
Recommended article: Q3789606
Recommended article: Bandwidth of Convex Bipartite Graphs and Related Graphs
description: scientific article; zbMATH DE number 1234997