
<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>This paper relates the connectivity of submodular functions \(f\) to that of certain submodular functions which are derived from \(f\). Here the function \(f\) on \(S\) is submodular if \(f(A)+f(B)\geq f(A\cup B)+f(A\cap B)\) for all subsets \(A\) and \(B\) of \(S\). The connectivity function \(c_ f\) of the submodular function \(f\) on \(S\) is defined by \(c_ f(A)=f(A)+f(S-A)- f(S)-f(0)\) for all subsets \(A\) of \(S\). The authors defined \(\overline c_ f\) to be minimum value that \(c_ f\) takes on nonempty proper subsets of \(S\) unless \(| S|\leq 1\). One of the two main results of this paper generalizes Tutte's result to submodular functions. This shows that if for a subset \(A\) of the ground set \(S\) we have \(c_ f(A)<2\overline c_ f\) then at least one of the operations of delection of \(A\) from \(f\) and of contraction of \(A\) from \(f\) is connected. In the second section of this paper is introduced and investigated a new operation on submodular functions which does correspond to contraction in graphs.
Discrete Mathematics and Combinatorics, Combinatorial aspects of matroids and geometric lattices, connectivity function, submodular function, Theoretical Computer Science
Discrete Mathematics and Combinatorics, Combinatorial aspects of matroids and geometric lattices, connectivity function, submodular function, Theoretical Computer Science
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
