Construction of matroidal families by partly closed sets |
| |
Authors: | Manfred Walter |
| |
Institution: | Institut für Statistik und Mathematische Wirtschaftstheorie, Universität Karlsruhe, Kollegium am Schloβ, Bau III, West Germany |
| |
Abstract: | A matroidal family of graphs is a set ≠Ø of connected finite graphs such that for every finite graph G the edge sets of those subgraphs of G which are isomorphic to some element of are the circuits of a matroid on the edge set of G. In 9], Schmidt shows that, for n?0, ?2n<r?1, n, , the set is a graph with β(G)=nα(G)+r and α(G )>, and is minimal with this property (with respect to the relation ?))} is a matroidal family of graphs. He also describes a method to construct new matroidal families of graphs by means of so-called partly closed sets. In this paper, an extension of this construction is given. By means of s-partly closed subsets of , s?r, we are able to give sufficient and necessary conditions for a subset of to yield a matroidal family of graphs when joined with the set of all graphs which satisfy: If , then H?G. In particular, it is shown that is not a matroidal family of graphs for r?2. Furthermore, for n?0, 1?2n<r, n, , the set of bipartite elements of can be used to construct new matroidal families of graphs if and only if s?min(n+r, 1). |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|