|
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
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.
Received: 25.11.2019
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
Linking options:
https://www.mathnet.ru/eng/znsl6916 https://www.mathnet.ru/eng/znsl/v488/p143
|
Statistics & downloads: |
Abstract page: | 106 | Full-text PDF : | 17 | References: | 22 |
|