FRACTIONAL ARBORICITY, STRENGTH, AND PRINCIPAL PARTITIONS IN GRAPHS AND MATROIDS

In a 1983 paper, D. Gusfield introduced a function which is called (following W.H. Cunningham, 1985) the strength of a graph or matroid. In terms of a graph G with edge set E(G) and at least one link, this is the function eta(G) = min(F subset-or-equal-to E(G) Absolute value of F/(omega(G - F) - omega(G)), where the minimum is taken over all subsets F of E(G) such that omega(G - F), the number of components of G - F, is at least omega(G) + 1. In a 1986 paper, C. Payan introduced the fractional arboricity of a graph or matroid. In terms of a graph G with edge set E(G) and at least one link this function is gamma(G) = max(H subset-or-equal-to G \E(H)\/(\V(H)\ - omega(H)), where H runs over all subgraphs of G having at least one link. Connected graphs G for which gamma(G) = eta(G) were used by A. Rucinski and A. Vince in 1986 while studying random graphs. We characterize the graphs and matroids G for which gamma(G) = eta(G). The values of gamma and eta are computed for certain graphs, and a recent result of Erdos (that if each edge of G lies in a C3, then \E(G)\ greater-than-or-equal-to 3/2(\V(G)\ - 1)) is generalized in terms of eta. The principal partition of a graph was introduced in 1967 by G. Kishi and Y. Kajitani, by T. Ohtsuki, Y. Ishizaki, and H. Watanabe, and by M. Iri (all of these were published in 1968). It has been used since then for the analysis of electrical networks in which the two Kirchhoff laws and Ohm's law hold, because it often allows the currents and voltage drops in the network to be completely computed with fewer measurements than are required for either of the Kirchhoff laws used alone. J. Bruno and L. Weinberg generalized the principal partition to matroids in 197 1, and their generalization was refined independently by N. Tomizawa (1976) and by H. Narayanan and M.N. Vartak (1974,1981). Here we demonstrate that gamma and eta arc closely related to the principal partition and can be used to give a simple definition of both the principal partition and the more recent refinements of it.