On certain classes of fractional matchings. (English) Zbl 0545.90099
Summary: An f-matching in an undirected graph X is defined as a set of vertex disjoint edges and odd cycles. In particular we consider f-matchings which saturate the maximum possible number of vertices and contain a maximum number of vertex disjoint edges. The main result is that in this case different possible f-matchings in X with these properties contain the same number of triangles, pentagons and so on. This means that maximizing the set of vertex disjoint edges in the f-matchings determines the number of cycles of length 3 (i.e. triangles), 5,..., \((2n+1)\). The problem is stated as a linear programming problem called fractional matching problem in a graph X.
MSC:
| 90C35 | Programming involving graphs or networks |
| 90C05 | Linear programming |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
References:
| [1] | Balas, E., Integer and fractional matchings, Mgmt. Sc. Res. Report No. 426 (1979), Carnegie-Mellon University, to appear in Annals Discrete Math |
| [2] | Balinski, M. L., On maximum matching, minimum covering and their connections, (Kuhn, H. W., Proc. Princeton Symposium on Mathematical Programming (1970), Princeton Univ. Press: Princeton Univ. Press Princeton, NJ), 303-312 · Zbl 0228.05122 |
| [3] | Mühlbacher, K., F-factors of graphs: A generalized matching problem, Inform. Process. Lett., 8, 4, 204-214 (1979) · Zbl 0426.05043 |
| [4] | Mühlbacher, J.; Steinparz, F., Canonical factors, (Pape, U., Discrete Structures, Proc. 5th Conf. on Graph Theoretic Concepts in Comp. Sci. (1980), Carl Hanser Verlag: Carl Hanser Verlag München), 93-104 · Zbl 0457.68068 |
| [5] | Nemhauser, G. L.; Trotter, L. E., Vertex packings: structural properties and algorithms, Math. Programming, 8, 232-248 (1975) · Zbl 0314.90059 |
| [6] | Nemhauser, G. L.; Trotter, L. E., Properties of vertex packings and independence system polyhedra, Math. Programming, 6, 48-61 (1974) · Zbl 0281.90072 |
| [7] | Uhry, J. P., Sur le problem du couplage maximal, R.A.I.R.O., 13-20 (1975) · Zbl 0357.90071 |
| [8] | Tutte, W. T., The factors of graphs, Canad. J. Math., 4, 314-328 (1952) · Zbl 0049.24202 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
