Connectivity functions and polymatroids

详细信息    查看全文

• 作者：Susan Jowett¹ ; ^{swoppit@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Songbao Mo ^{songbao.mo@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Geoff Whittle ; ² ; ^{geoff.whittle@vuw.ac.nz" class="auth_mail" title="E-mail the corresponding author}
• 关键词：05B35
• 刊名：Advances in Applied Mathematics
• 出版年：2016
• 出版时间：October 2016
• 年：2016
• 卷：81
• 期：Complete
• 页码：1-12
• 全文大小：285 K

文摘

A connectivity function on a set E   is a function class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0196885816300483&_mathId=si1.gif&_user=111111111&_pii=S0196885816300483&_rdoc=1&_issn=01968858&md5=c1ee432887e501bc7d9ac6860a18f5c3" title="Click to view the MathML source">λ:2^E→Rclass="mathContainer hidden">class="mathCode">$\lambda :2^E\to \mathbb{R}$ such that class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0196885816300483&_mathId=si2.gif&_user=111111111&_pii=S0196885816300483&_rdoc=1&_issn=01968858&md5=e6540a26e9a1c0a2742e17b6433eb3e4" title="Click to view the MathML source">λ(∅)=0class="mathContainer hidden">class="mathCode">$\lambda (\varnothing )=0$, that class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0196885816300483&_mathId=si3.gif&_user=111111111&_pii=S0196885816300483&_rdoc=1&_issn=01968858&md5=ad68e983f5bcf59bf607cac5896ed0ee" title="Click to view the MathML source">λ(X)=λ(E−X)class="mathContainer hidden">class="mathCode">$\lambda (X)=\lambda (E-X)$ for all class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0196885816300483&_mathId=si127.gif&_user=111111111&_pii=S0196885816300483&_rdoc=1&_issn=01968858&md5=ce43be0227d30a6e7edec00999993e6f" title="Click to view the MathML source">X⊆Eclass="mathContainer hidden">class="mathCode">$X\subseteq E$ and that class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0196885816300483&_mathId=si5.gif&_user=111111111&_pii=S0196885816300483&_rdoc=1&_issn=01968858&md5=9e8d896a2ea8dea53adb1b0cd0200c55" title="Click to view the MathML source">λ(X∩Y)+λ(X∪Y)≤λ(X)+λ(Y)class="mathContainer hidden">class="mathCode">$\lambda (X\cap Y)+\lambda (X\cup Y)\le \lambda (X)+\lambda (Y)$ for all class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0196885816300483&_mathId=si6.gif&_user=111111111&_pii=S0196885816300483&_rdoc=1&_issn=01968858&md5=b3ce3719ed7e129c60616bde0104fc0a" title="Click to view the MathML source">X,Y⊆Eclass="mathContainer hidden">class="mathCode">$X,Y\subseteq E$. 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.