Geodesic
On vertices of degree $6$ of minimally and contraction critically $6$-connected graph
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part XI, Tome 488 (2019), pp. 143-167 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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}$. 
@article{ZNSL_2019_488_a6,
     author = {A. V. Pastor},
     title = {On vertices of degree $6$ of minimally and contraction critically $6$-connected graph},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {143--167},
     year = {2019},
     volume = {488},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2019_488_a6/}
}
TY  - JOUR
AU  - A. V. Pastor
TI  - On vertices of degree $6$ of minimally and contraction critically $6$-connected graph
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2019
SP  - 143
EP  - 167
VL  - 488
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2019_488_a6/
LA  - ru
ID  - ZNSL_2019_488_a6
ER  - 
%0 Journal Article
%A A. V. Pastor
%T On vertices of degree $6$ of minimally and contraction critically $6$-connected graph
%J Zapiski Nauchnykh Seminarov POMI
%D 2019
%P 143-167
%V 488
%U http://geodesic.mathdoc.fr/item/ZNSL_2019_488_a6/
%G ru
%F ZNSL_2019_488_a6
A. V. Pastor. On vertices of degree $6$ of minimally and contraction critically $6$-connected graph. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part XI, Tome 488 (2019), pp. 143-167. http://geodesic.mathdoc.fr/item/ZNSL_2019_488_a6/

[1] D. V. Karpov, “Bloki v $k$-svyaznykh grafakh”, Zap. nauchn. semin. POMI, 293, 2002, 59–93 | Zbl

[2] D. V. Karpov, “Razdelyayuschie mnozhestva v $k$-svyaznom grafe”, Zap. nauchn. semin. POMI, 340, 2006, 33–60 | Zbl

[3] D. V. Karpov, “Derevo razrezov i minimalnyi $k$-svyaznyi graf”, Zap. nauchn. semin. POMI, 427, 2014, 22–40

[4] D. V. Karpov, A. V. Pastor, “O strukture $k$-svyaznogo grafa”, Zap. nauchn. semin. POMI, 266, 2000, 76–106

[5] S. A. Obraztsova, “O lokalnoi strukture $5$ i $6$-svyaznykh grafov”, Zap. nauchn. semin. POMI, 381, 2010, 88–96

[6] S. A. Obraztsova, “O lokalnoi strukture $9$ i $10$-svyaznykh grafov”, Zap. nauchn. semin. POMI, 391, 2011, 157–197

[7] S. A. Obraztsova, A. V. Pastor, “O lokalnoi strukture 7 i 8-svyaznykh grafov”, Zap. nauchn. semin. POMI, 381, 2010, 97–111

[8] S. A. Obraztsova, A. V. Pastor, “O vershinakh stepeni $k$ minimalnykh i minimalnykh otnositelno styagivaniya $k$-svyaznykh grafov: verkhnie otsenki”, Zap. nauchn. semin. POMI, 391, 2011, 198–210

[9] A. V. Pastor, “O razbienii trekhsvyaznogo grafa na tsiklicheski reberno-chetyrekhsvyaznye komponenty”, Zap. nauchn. semin. POMI, 450, 2016, 109–150

[10] K. Ando, S. Fujita, K. Kawarabayashi, “Minimally contraction-critically $6$-connected graphs”, Discrete Mathematics, 312:3 (2012), 671–679 | DOI | MR | Zbl

[11] K. Ando, T. Iwase, “The number of vertices of degree $5$ in a contraction-critically $5$-connected graph”, Discrete Mathematics, 311 (2011), 1925–1939 | DOI | MR | Zbl

[12] K. Ando, C. Qin, “Some structural properties of minimally contraction-critically $5$-connected graphs”, Discrete Mathematics, 311 (2011), 1084–1097 | DOI | MR | Zbl

[13] M. Fontet, “Graphes 4-essentiels”, C. R. Acad. Se. Paris, serie A, 287 (1978), 289–290 | MR | Zbl

[14] R. Halin, “A theorem on $n$-connected graphs”, J. Comb. Theory, 7 (1969), 150–154 | DOI | MR | Zbl

[15] W. Hohberg, “The decomposition of graphs into $k$-connected components”, Discr. Math., 109 (1992), 133–145 | DOI | MR | Zbl

[16] M. Li, X. Yuan, J. Su, “The number of vertices of degree $7$ in a contraction-critical $7$-connected graph”, Discrete Mathematics, 308 (2008), 6262–6268 | DOI | MR | Zbl

[17] W. Mader, “Ecken Vom Gard $n$ in minimalen $n$-fach zusammenhangenden Graphen”, Arch. Math. (Basel), 23 (1972), 219–224 (German) | DOI | MR | Zbl

[18] W. Mader, “Zur Struktur minimal $n$-fach zusammenhängender Graphen”, Abh. Math. Sem. Univ. Hamburg, 49 (1979), 49–69 (German) | DOI | MR | Zbl

[19] N. Martinov, “A recursive characterization of the $4$-connected graphs”, Discrete Mathematics, 84 (1990), 105–108 | DOI | MR | Zbl

[20] W. T. Tutte, “A theory of $3$-connected graphs”, Indag. Math., 23 (1961), 441–455 | DOI | MR

[21] Q. Zhao, C. Qin, X. Yuan, M. Li, “Vertices of degree 6 in a contraction-critical 6 connected graph”, J. Guangxin Norm. Univ., 25:2 (2005), 38–43 | MR