Fractional arboricity, strength, and principal partitions in graphs and matroids (Q1208447)

Let \(G\) be a graph with edge set \(E(G)\) having at least one link and being loopless. For any subset \(F\) of \(E(G)\) let \(\omega(G-F)\) denote the number of components of \(G-F\). Following \textit{W. H. Cunningham} [J. Assoc. Comput. Mach. 32, 549-561 (1985; Zbl 0629.90034)], the function \(\eta(G)=\min_{F\subseteq E(G)}| F|/(\omega(G-F)-\omega(G))\), where the minimum is taken over all subsets \(F\) of \(E(G)\) such that \(\omega(G-F)\) is at least \(\omega(G)+1\), is said to be the strength of \(G\). And moreover, following \textit{C. Payan} [Eur. J. Comb. 7, 263-270 (1986; Zbl 0663.05051)], the function \(\gamma(G)=\max_{H\subseteq G}| E(H)|/(| V(H)|-\omega(H))\), where \(H\) runs over all subgraphs of \(G\) having at least one link, is said to be the fractional arboricity of \(G\). It is easy to see that both these functions can be defined in terms of a matroid, as well. In the paper under review, the discussion centers around the following two main problems. First, the graphs and matroids \(G\) for which \(\gamma(G)=\eta(G)\) are characterized, the values \(\gamma\) and \(\eta\) are computed for certain graphs, and a recent result of \textit{P. Erdős} is generalized in terms of \(\eta\). Second, it is shown how the two functions \(\gamma\) and \(\eta\) can be used to describe the principal partition of a matroid. This concept was first defined for graphs and used for the analysis of electrical networks by \textit{G. Kishi} and \textit{Y. Kajitani} [Electron. Comm. Japan 51A (5), 35- 42 (1968)], by \textit{M. Iri} [ibid. 51A (5), 18-25 (1968)], and by \textit{T. Ohtsuki}, \textit{Y. Ishizaki} and \textit{H. Watanabe} [ibid. 51A (6), 33-40 (1968)], and then it was generalized for matroids by \textit{J. Bruno} and \textit{L. Weinberg} [Linear Algebra Appl. 4, 17-54 (1971; Zbl 0317.05021)].