ISSN:
1439-6912
Keywords:
05 C 70
;
05 C 75
;
94 B 60
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract A subsetJ of edges of a connected undirected graphG=(V, E) is called ajoin if |C∩J|≤|C|/2 for every circuitC ofG. Answering a question of P. Solé and Th. Zaslavsky, we derive a min-max formula for the maximum cardinality μ of a joint ofG. Namely, μ=(φ+|V|−1)/2 where φ denotes the minimum number of edges whose contraction leaves a factor-critical graph. To study these parameters we introduce a new decomposition ofG, interesting for its own sake, whose building blocks are factor-critical graphs and matching-covered bipartite graphs. We prove that the length of such a decomposition is always φ and show how an optimal join can be constructed as the union of perfect matchings in the building blocks. The proof relies on the Gallai-Edmonds structure theorem and gives rise to a polynomial time algorithm to construct the optima in question.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01202790
