Connectivity functions and polymatroids

DOI10.1016/J.AAM.2016.06.004zbMATH Open1352.05045arXiv1605.01455OpenAlexW2963451339MaRDI QIDQ730631FDOQ730631

Authors: Susan Jowett, Songbao Mo, Geoff Whittle 

Publication date: 28 December 2016

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Abstract: A {em connectivity function on} a set $E$ is a function $lambda:2^{E}ightarrowmathbbR$ such that $lambda(emptyset)=0$, that $lambda(X)=lambda(E-X)$ for all $XsubseteqE$ and that $lambda(XcapY)+lambda(XcupY)leqlambda(X)+lambda(Y)$ for all $X,YsubseteqE$. Graphs, matroids and, more generally, polymatroids have associated connectivity functions. We introduce a notion of duality for polymatroids and prove that every connectivity function is the connectivity function of a self-dual polymatroid. We also prove that every integral connectivity function is the connectivity function of a half-integral self-dual polymatroid.

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

Recommendations

• Recognising graphic and matroidal connectivity functions
• On the connectivity function of a matroid
• Connectivity of submodular functions
• scientific article; zbMATH DE number 850300
• Duality in Polymatroids and Set Functions

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• Graph minors. X: Obstructions to tree-decomposition
• Title not available (Why is that?)
• The branchwidth of graphs and their cycle matroids
• Tangles, tree-decompositions and grids in matroids
• Tangles, trees, and flowers
• Matroids having the same connectivity function
• On the connectivity function of a matroid
• Duality in Polymatroids and Set Functions
• Computing with Tangles

Cited In (6)

• A characterization of extendable connectivity functions
• Recognising graphic and matroidal connectivity functions
• Submodular functions and rooted trees
• Connectivity of submodular functions
• A new polynomial for polymatroids
• A splitter theorem for 3-connected 2-polymatroids

This page was built for publication: Connectivity functions and polymatroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q730631)