Cellular bipartite graphs
type: Item
instance of: scholarly article
title: Cellular bipartite graphs
zbMATH Open document ID: 0848.05054
author: Hans-Jürgen Bandelt
author: Victor Chepoi
published in: European Journal of Combinatorics
publication date: 1996-10-01T00:00:00Z
review text: Graphs that are obtained from single edges and even cycles by successive amalgamations are called cellular graphs. Especially cellular bipartite graphs are investigated in this paper. Since graphs with their shortest-path metrics are particular instances of finite metric spaces, these investigations are done from a metric point of view. A particular class of finite so-called \(\ell_1\)-spaces is formed by the totally decomposable spaces, in which the summands in an \(\ell_1\)-decomposition obey a certain compatibility rule. In this paper, it is shown that the bipartite graphs with totally decomposable metric have a convenient decomposition scheme, the ingredients of which are gated amalgamation as a fundamental operation and even cycles and single edges as building stones. Here the connection to cellular graphs is given. The main results are three theorems: (a) It is shown that for a bipartite graph \(G\) with at least two vertices six conditions are equivalent, for instance: (1) the metric of \(G\) is totally decomposable, and (4) \(G\) is a cellular graph (Theorem 1). (b) Every cellular bipartite graph with at least two vertices has either two pendant vertices or a pendant gated cycle, where a gated cycle of length \(k\) is said to be pendant in \(G\) if it includes a path of length \({k \over 2}-2\), all vertices of which have degree 2 in \(G\) (Theorem 2). (c) Every cellular bipartite graph either is indecomposable or possesses a gated cutset that is a tree (a cutset \(R\) of a connected graph is any subgraph for which \(G-R\) is disconnected) (Theorem 3). For cellular bipartite graphs \(G\) the authors also obtain a kind of Euler formula, namely for such a graph \(G\) with \(n\) vertices, \(m\) edges, and \(g\) gated cycles holds \(n - m + g = 1\) (Corollary 1). Further, by application of the proofs of Theorems 1 and 2 and especially with the help of an elimination scheme of Theorem 2, it can be shown that cellular bipartite graphs can be recognized by a quadra…
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 871009
zbMATH Keywords: even cycles
zbMATH Keywords: cellular graphs
zbMATH Keywords: decomposition
zbMATH Keywords: bipartite graph
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
full work available at URL: eujc.1996.0011
OpenAlex ID: W2035070241
DOI: 10.1006/EUJC.1996.0011
description: scientific article; zbMATH DE number 871009