Name
Abstract | ||
|---|---|---|
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 η( G ) = min F ⊆ E ( G ) ∣ F ∣/(ω( G − F ) − ω( G )), where the minimum is taken over all subsets F of E ( G ) such that ω( G − F ), the number of components of G − F , is at least ω( 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 γ( G ) = max H ⊆ G ∣ E ( H )∣/(∣ V ( H )∣ − ω( H )), where H runs over all subgraphs of G having at least one link. Connected graphs G for which γ( G ) = η( G ) were used by A. Ruciński and A. Vince in 1986 while studying random graphs. We characterize the graphs and matroids G for which γ( G ) = η( G ). The values of γ and η are computed for certain graphs, and a recent result of Erdös (that if each edge of G lies in a C 3 , then ∣ E ( G )∣≥ 3 2 (∣ V ( G )∣ − 1)) is generalized in terms of η. 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 1971, and their generalization was refined independently by N. Tomizawa (1976) and by H. Narayanan and M.N. Vartak (1974, 1981). Here we demonstrate that γ and η are 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. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1016/0166-218X(92)90002-R | Discrete Applied Mathematics |
Keywords | Field | DocType |
fractional arboricity,principal partition | Matroid,Strength of a graph,Graph,Discrete mathematics,Combinatorics,Random graph,Connectivity,Partition (number theory),Arboricity,Mathematics,Branch-decomposition | Journal |
Volume | Issue | ISSN |
40 | 3 | Discrete Applied Mathematics |
Citations | PageRank | References |
34 | 3.01 | 4 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul A. Catlin | 1 | 514 | 66.29 |
| Jerrold W. Grossman | 2 | 138 | 21.94 |
| Arthur M Hobbs | 3 | 71 | 19.33 |
| Hong-Jian Lai | 4 | 631 | 97.39 |