Diskretnaya Matematika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Diskretnaya Matematika, 1989, Volume 1, Issue 3, Pages 129–138 (Mi dm932)  

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
Bibliographic databases:
UDC: 519.1
Language: Russian
Citation: R. I. Tyshkevich, “Matroid decompositions of graphs”, Diskr. Mat., 1:3 (1989), 129–138
Citation in format AMSBIB
\Bibitem{Tys89}
\by R.~I.~Tyshkevich
\paper Matroid decompositions of graphs
\jour Diskr. Mat.
\yr 1989
\vol 1
\issue 3
\pages 129--138
\mathnet{http://mi.mathnet.ru/dm932}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=1044245}
\zmath{https://zbmath.org/?q=an:0721.05048}
Linking options:
  • https://www.mathnet.ru/eng/dm932
  • https://www.mathnet.ru/eng/dm/v1/i3/p129
  • This publication is cited in the following 3 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретная математика
    Statistics & downloads:
    Abstract page:459
    Full-text PDF :216
    First page:1
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024