|
This article is cited in 3 scientific papers (total in 3 papers)
Matroid decompositions of graphs
R. I. Tyshkevich
Abstract:
A graph $G$ is called M-graph, if it satisfies one of the following conditions: 1) $G$ is a simple graph, every connected component of which is a complete graph; 2) $G$ is obtained from a graph described in 1) or from the empty set as a result of joining the dominating vertices with loops. It has been proved that every graph can be represented in the form of an intersection of $M$-graphs such that each of its sets of independent vertices is independent in some component. The minimal number $m(G)$ of components in such representations is called the matroidal number of the graph $G$. If $G=G_1\cap G_2\cap\dots\cap G_m$ is a representation of that kind and $IG$ is the set for which all independent subsets of vertices of the graph $G$ and the empty set serve as elements then
$$
IG=IG_1\cup IG_2\cup\dots\cup IG_m,
$$
where $(VG,IG\sb k)$ is a matroid with the system of independent sets $IG_k$. Here $VG$ is the set of vertices of the graph $G$. The parameter $m(G)$ is equal to the minimal number of matroids, into the set-theoretic union of which the independence system $IG$ can be decomposed. The structure of graphs with $m(G)$ bounded by a constant has been described. The value $m(G)$ for splittable graphs has been found.
Received: 21.02.1989
Citation:
R. I. Tyshkevich, “Matroid decompositions of graphs”, Diskr. Mat., 1:3 (1989), 129–138
Linking options:
https://www.mathnet.ru/eng/dm932 https://www.mathnet.ru/eng/dm/v1/i3/p129
|
Statistics & downloads: |
Abstract page: | 459 | Full-text PDF : | 216 | First page: | 1 |
|