Zapiski Nauchnykh Seminarov POMI
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



Zap. Nauchn. Sem. POMI:
Year:
Volume:
Issue:
Page:
Find






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


Zapiski Nauchnykh Seminarov POMI, 2018, Volume 475, Pages 41–92 (Mi znsl6685)  

On the structure of a 3-connected graph. 2

D. V. Karpovab

a St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences, St. Petersburg, Russia
b St. Petersburg State University, Mathematics and Mechanics Faculty, St. Petersburg, Russia
References:
Abstract: In this paper, the structure of relative disposition of $3$-vertex cutsets in a $3$-connected graph is studied. All such cutsets are divided into structural units — complexes of flowers, of cuts, of single cutsets and trivial complexes. The decomposition of the graph by a complex of each type is described in detail.
It is proved that for any two complexes ${\mathcal C}_1$ and ${\mathcal C}_2 $ of a $3$-connected graph $G$ there is a unique part of decomposition of $G$ by ${\mathcal C}_1$, that contains ${\mathcal C}_2 $. The relative disposition of complexes is described with the help of a hypertree ${\mathcal T}(G)$ — a hypergraph, any cycle of which is a subset of a certain hyperedge. It is also proved that each nonempty part of decomposition of $G$ by the set of all its $3$-vertex cutsets is either a part of decomposition of $G$ by one of the complexes or corresponds to a hyperedge of ${\mathcal T}(G)$.
This paper can be considered as a continuation of studies begun in the joint paper by D.V. Karpov and A.V. Pastor On the structure of a $3$-connected graph published in 2011.
Key words and phrases: connectivity, $3$-connected graph, cutset.
Funding agency Grant number
Ministry of Education and Science of the Russian Federation 14.Z50.31.0030
Received: 29.11.2018
Document Type: Article
UDC: 519.173.1
Language: Russian
Citation: D. V. Karpov, “On the structure of a 3-connected graph. 2”, Combinatorics and graph theory. Part X, Zap. Nauchn. Sem. POMI, 475, POMI, St. Petersburg, 2018, 41–92
Citation in format AMSBIB
\Bibitem{Kar18}
\by D.~V.~Karpov
\paper On the structure of a 3-connected graph.~ 2
\inbook Combinatorics and graph theory. Part~X
\serial Zap. Nauchn. Sem. POMI
\yr 2018
\vol 475
\pages 41--92
\publ POMI
\publaddr St.~Petersburg
\mathnet{http://mi.mathnet.ru/znsl6685}
Linking options:
  • https://www.mathnet.ru/eng/znsl6685
  • https://www.mathnet.ru/eng/znsl/v475/p41
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Записки научных семинаров ПОМИ
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024