Connectivity functions and polymatroids

DOI10.1016/J.AAM.2016.06.004MaRDI QIDQ730631zbMATHOpenAlexFDO

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
• Publication:4866324
• Duality in Polymatroids and Set Functions

Cites work

• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• Computing with Tangles
• Duality in Polymatroids and Set Functions
• Graph minors. X: Obstructions to tree-decomposition
• 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

(6)

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

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)