A tight relation between series-parallel graphs and bipartite distance hereditary graphs
From MaRDI portal
Publication:5045248
Abstract: Bandelt and Mulder's structural characterization of Bipartite Distance Hereditary graphs asserts that such graphs can be built inductively starting from a single vertex and by repeatedly adding either pending vertices or twins (i.e., vertices with the same neighborhood as an existing one). Dirac and Duffin's structural characterization of 2-connected series-parallel graphs asserts that such graphs can be built inductively starting from a single edge by adding either edges in series or in parallel. In this paper we prove that the two constructions are the same construction when bipartite graphs are viewed as the fundamental graphs of a graphic matroid. We then apply the result to re-prove known results concerning bipartite distance hereditary graphs and series-parallel graphs, to characterize self-dual outer-planar graphs and, finally, to provide a new class of polynomially-solvable instances for the integer multi commodity flow of maximum value.
Recommendations
- Bipartite almost distance-hereditary graphs
- scientific article; zbMATH DE number 844157
- On the Galois lattice of bipartite distance hereditary graphs
- On the Galois Lattice of Bipartite Distance Hereditary Graphs
- Distance-hereditary and strongly distance-hereditary graphs
- Graph classes between parity and distance-hereditary graphs
- scientific article; zbMATH DE number 1222095
- On an extension of distance-hereditary graphs
- On an extension of distance hereditary graphs
- SOME PROPERTIES OF BINARY SERIES-PARALLEL GRAPHS
Cites work
- A characterization of circle graphs
- A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
- A Combinatorial Model for Series-Parallel Networks
- A new proof of the Gauss interlace conjecture
- A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
- Combinatorial optimization. Packing and covering
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Distance Hereditary Graphs and the Interlace Polynomial
- Distance-hereditary graphs
- Domination, independent domination, and duality in strongly chordal graphs
- Enumeration and limit laws for series-parallel graphs
- Finding edge-disjoint paths in partial \(k\)-trees
- Graph Classes: A Survey
- Graph minors. X: Obstructions to tree-decomposition
- scientific article; zbMATH DE number 420868 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 3681808 (Why is no real title available?)
- scientific article; zbMATH DE number 16298 (Why is no real title available?)
- scientific article; zbMATH DE number 53949 (Why is no real title available?)
- scientific article; zbMATH DE number 3534506 (Why is no real title available?)
- scientific article; zbMATH DE number 1445310 (Why is no real title available?)
- Integrality properties of edge path tree families
- Interlace polynomials
- Local complementation and interlacement graphs
- On a characterization of Gauss codes
- On computing the Galois lattice of bipartite distance hereditary graphs
- On Integer Multiflow Maximization
- On the excluded minors for the matroids of branch-width \(k\)
- On the Galois lattice of bipartite distance hereditary graphs
- On the realization of double occurrence words
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Rank-width and vertex-minors
- Series - parallel graphs and depth-first search trees
- The branchwidth of graphs and their cycle matroids
- The edge-disjoint paths problem is NP-complete for series-parallel graphs
- Topology of series-parallel networks
- Totally-Balanced and Greedy Matrices
- Tutte polynomials computable in polynomial time
This page was built for publication: A tight relation between series-parallel graphs and bipartite distance hereditary graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5045248)
