Connectivity functions and polymatroids

DOI10.1016/J.AAM.2016.06.004MaRDI QIDQ730631zbMATH OpenOpenAlexFDO

Authors Susan Jowett, Songbao Mo, Geoff Whittle

Publication date 28 December 2016

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

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

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

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.

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

Cites work

• Computing with Tangles
• Duality in Polymatroids and Set Functions
• Graph minors. X: Obstructions to tree-decomposition
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• Matroids having the same connectivity function
• On the connectivity function of a matroid
• Tangles, tree-decompositions and grids in matroids
• Tangles, trees, and flowers
• The branchwidth of graphs and their cycle matroids

Cited in

(7)

• A characterization of extendable connectivity functions
• Connectivity of submodular functions
• Recognising graphic and matroidal connectivity functions
• Submodular functions and rooted trees
• A splitter theorem for 3-connected 2-polymatroids
• Duality in Polymatroids and Set Functions
• A new polynomial for 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)