Fractional arboricity, strength, and principal partitions in graphs and matroids
type: Item
instance of: scholarly article
title: Fractional arboricity, strength, and principal partitions in graphs and matroids
zbMATH Open document ID: 0773.05033
DOI: 10.1016/0166-218X(92)90002-R
author: Paul A. Catlin
author: Jerrold W. Grossman
author: Arthur M. Hobbs
author: Hong-Jian Lai
published in: Discrete Applied Mathematics
publication date: 1993-05-16T00:00:00Z
review text: 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)].
reviewed by: J.Libicher
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 166451
zbMATH Keywords: strength
zbMATH Keywords: fractional arboricity
zbMATH Keywords: matroid
zbMATH Keywords: principal partition
MaRDI profile type: Publication
cites work: Q5422499
cites work: PRINCIPAL PARTITION AND PRINCIPAL MINORS OF A MATROID, WITH APPLICATIONS†
cites work: The principal minors of a matroid
cites work: The reduction of graph families closed under contraction
cites work: Optimal attack and reinforcement of a network
cites work: Lehmans switching game and a theorem of Tutte and Nash-Williams
cites work: Connectivity and edge-disjoint spanning trees
cites work: Q5812325
cites work: A Solution of the Shannon Switching Game
cites work: Q3934403
cites work: Edge-Disjoint Spanning Trees of Finite Graphs
cites work: Decomposition of Finite Graphs Into Forests
cites work: Graphes équilibrés et arboricité rationnelle. (Balanced graphs and rational arboricity)
cites work: Strongly balanced graphs and random graphs
cites work: Q3309631
cites work: On the Problem of Decomposing a Graph into n Connected Factors
cites work: Activities on circuit theory in Japan
cites work: Q4111952
full work available at URL: 0166-218x(92)90002-r
OpenAlex ID: W2074890468
Recommended article: Q4529265
Recommended article: Q4734775
Recommended article: Submodular functions and electrical networks
Recommended article: Q3203035
Recommended article: Fractional Vertex Arboricity of Graphs
Recommended article: Strength and fractional arboricity of complementary graphs
Recommended article: The principal partition of a pair of graphs and its applications
Recommended article: Q5752609
Recommended article: Brick partitions of graphs
Recommended article: Maps of matroids with applications
description: scientific article; zbMATH DE number 166451