A tight relation between series-parallel graphs and bipartite distance hereditary graphs

DOI10.26493/2590-9770.1396.3C7zbMATH Open1502.05210arXiv1511.03100OpenAlexW3134695014WikidataQ113213292 ScholiaQ113213292MaRDI QIDQ5045248FDOQ5045248

Authors: Massimiliano Caramia, Jean-François Mascari, Nicola Apollonio, Paolo G. Franciosa 

Publication date: 4 November 2022

Published in: The Art of Discrete and Applied Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1511.03100

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

zbMATH Keywords

binary matroidsseries-parallel graphsbipartite distance hereditary graphs

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Structural characterization of families of graphs (05C75)

Cites Work

• Title not available (Why is that?)
• Graph minors. X: Obstructions to tree-decomposition
• Enumeration and limit laws for series-parallel graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph Classes: A Survey
• Integrality properties of edge path tree families
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Title not available (Why is that?)
• A Combinatorial Model for Series-Parallel Networks
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• Distance-hereditary graphs
• On a characterization of Gauss codes
• Rank-width and vertex-minors
• Domination, independent domination, and duality in strongly chordal graphs
• Combinatorial optimization. Packing and covering
• Totally-Balanced and Greedy Matrices
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• Title not available (Why is that?)
• Local complementation and interlacement graphs
• Topology of series-parallel networks
• Primal-dual approximation algorithms for integral flow and multicut in trees
• On the excluded minors for the matroids of branch-width \(k\)
• The branchwidth of graphs and their cycle matroids
• Title not available (Why is that?)
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• Interlace polynomials
• Distance Hereditary Graphs and the Interlace Polynomial
• Finding edge-disjoint paths in partial \(k\)-trees
• On Integer Multiflow Maximization
• A characterization of circle graphs
• On the realization of double occurrence words
• A new proof of the Gauss interlace conjecture
• Tutte polynomials computable in polynomial time
• Series - parallel graphs and depth-first search trees
• Title not available (Why is that?)
• On the Galois lattice of bipartite distance hereditary graphs
• On computing the Galois lattice of bipartite distance hereditary graphs

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)