The super-connectivity of Johnson graphs
Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 1
Voir la notice de l'article provenant de la source Episciences
For positive integers $n,k$ and $t$, the uniform subset graph $G(n, k, t)$ has all $k$-subsets of $\{1,2,\ldots, n\}$ as vertices and two $k$-subsets are joined by an edge if they intersect at exactly $t$ elements. The Johnson graph $J(n,k)$ corresponds to $G(n,k,k-1)$, that is, two vertices of $J(n,k)$ are adjacent if the intersection of the corresponding $k$-subsets has size $k-1$. A super vertex-cut of a connected graph is a set of vertices whose removal disconnects the graph without isolating a vertex and the super-connectivity is the size of a minimum super vertex-cut. In this work, we fully determine the super-connectivity of the family of Johnson graphs $J(n,k)$ for $n\geq k\geq 1$.
@article{DMTCS_2020_22_1_a10,
author = {Ekinci, G\"ulnaz Boruzanl{\i} and Gauci, John Baptist},
title = {The super-connectivity of {Johnson} graphs},
journal = {Discrete mathematics & theoretical computer science},
publisher = {mathdoc},
volume = {22},
number = {1},
year = {2020-2021},
doi = {10.23638/DMTCS-22-1-12},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-12/}
}
TY - JOUR AU - Ekinci, Gülnaz Boruzanlı AU - Gauci, John Baptist TI - The super-connectivity of Johnson graphs JO - Discrete mathematics & theoretical computer science PY - 2020-2021 VL - 22 IS - 1 PB - mathdoc UR - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-12/ DO - 10.23638/DMTCS-22-1-12 LA - en ID - DMTCS_2020_22_1_a10 ER -
%0 Journal Article %A Ekinci, Gülnaz Boruzanlı %A Gauci, John Baptist %T The super-connectivity of Johnson graphs %J Discrete mathematics & theoretical computer science %D 2020-2021 %V 22 %N 1 %I mathdoc %U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-12/ %R 10.23638/DMTCS-22-1-12 %G en %F DMTCS_2020_22_1_a10
Ekinci, Gülnaz Boruzanlı; Gauci, John Baptist. The super-connectivity of Johnson graphs. Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 1. doi: 10.23638/DMTCS-22-1-12
Cité par Sources :