RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 1989 Volume 1, Issue 3, Pages 129–138 (Mi dm932)

This article is cited 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.

UDC: 519.1

Received: 21.02.1989



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024