Decomposition of wheel-and-parachute-free balanced bipartite graphs
type: Item
instance of: scholarly article
title: Decomposition of wheel-and-parachute-free balanced bipartite graphs
zbMATH Open document ID: 0832.05063
DOI: 10.1016/0166-218X(94)00148-7
author: Yanyan Li
published in: Discrete Applied Mathematics
publication date: 1996-02-08T00:00:00Z
review text: The main notions of the paper are the notions of wheel and parachute. A cycle in a graph is called a hole if no two nonconsecutive nodes of it are adjacent. A wheel \((H, x)\) is defined to be the subgraph induced by a hole \(H\) and a node \(x\) not belonging to \(H\) but having at least three neighbours in \(H\). The definition of parachute is too lengthy to reproduce it here. In a drawing the parachute resembles a plane version of a usual one. A bipartite graph is called balanced if it does not contain a hole of length \(4k+ 2\). The paper is devoted to balanced bipartite graphs that contain neither a wheel nor a parachute as an induced subgraph.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 806410
zbMATH Keywords: wheel
zbMATH Keywords: parachute
zbMATH Keywords: hole
zbMATH Keywords: bipartite graph
zbMATH Keywords: balanced
zbMATH Keywords: induced subgraph
reviewed by: Mikhail Ostrovskii
MaRDI profile type: Publication
cites work: Characterizations of totally balanced matrices
cites work: Balanced matrices
cites work: A sufficient condition for a matrix to be totally unimodular
cites work: Structural properties and decomposition of linear balanced matrices
cites work: Structural properties and recognition of restricted and strongly unimodular matrices
cites work: Odd cycles and matrices with integrality properties
cites work: A Combinatorial Decomposition Theory
cites work: Perfect Elimination and Chordal Bipartite Graphs
cites work: Q3328583
cites work: Totally-Balanced and Greedy Matrices
cites work: Decomposition of regular matroids
cites work: Alpha-balanced graphs and matrices and GF(3)-representability of matroids
cites work: On a Class of Totally Unimodular Matrices
full work available at URL: 0166-218x(94)00148-7
OpenAlex ID: W2050059784
description: scientific article; zbMATH DE number 806410