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, 2019, Volume 488, Pages 143–167 (Mi znsl6916)  

On vertices of degree $6$ of minimally and contraction critically $6$-connected graph

A. V. Pastorab

a St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences
b Peter the Great St. Petersburg Polytechnic University
References:
Abstract: In this paper, we research vertices of degree $6$ of minimally and contraction critically $6$-connected graph, i.e. a $6$-connected graph that will loose $6$-connectivity after removing or contracting of any edge. We prove the following theorem. If $x$ and $z$ are adjacent vertices of degree $6$ of such a graph and no other vertex of degree 6 is adjacent to $x$ or $z$ then $x$ and $z$ have at least $4$ common neighbors. Moreover, in this case we give a detailed description of the neighborhood of the set $\{x,z\}$. Also, we construct an infinite series of examples of minimally and contraction critically $6$-connected graphs, for which a fraction of vertices of degree $6$ is ${11\over17}$.
Key words and phrases: $k$-connectivity, minimally $k$-connected graph, contraction critically $k$-connected graph.
Funding agency Grant number
Ministry of Education and Science of the Russian Federation 14.Z50.31.0030
Received: 25.11.2019
Document Type: Article
UDC: 519.173.1
Language: Russian
Citation: A. V. Pastor, “On vertices of degree $6$ of minimally and contraction critically $6$-connected graph”, Combinatorics and graph theory. Part XI, Zap. Nauchn. Sem. POMI, 488, POMI, St. Petersburg, 2019, 143–167
Citation in format AMSBIB
\Bibitem{Pas19}
\by A.~V.~Pastor
\paper On vertices of degree $6$ of minimally and contraction critically $6$-connected graph
\inbook Combinatorics and graph theory. Part~XI
\serial Zap. Nauchn. Sem. POMI
\yr 2019
\vol 488
\pages 143--167
\publ POMI
\publaddr St.~Petersburg
\mathnet{http://mi.mathnet.ru/znsl6916}
Linking options:
  • https://www.mathnet.ru/eng/znsl6916
  • https://www.mathnet.ru/eng/znsl/v488/p143
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Записки научных семинаров ПОМИ
    Statistics & downloads:
    Abstract page:106
    Full-text PDF :17
    References:22
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024