Gülnaz Boruzanlı Ekinci ; John Baptist Gauci - The super-connectivity of Johnson graphs

dmtcs:5600 - Discrete Mathematics & Theoretical Computer Science, April 14, 2020, vol. 22 no. 1 - https://doi.org/10.23638/DMTCS-22-1-12
The super-connectivity of Johnson graphsArticle

Authors: Gülnaz Boruzanlı Ekinci ; John Baptist Gauci

    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$.


    Volume: vol. 22 no. 1
    Section: Graph Theory
    Published on: April 14, 2020
    Accepted on: February 26, 2020
    Submitted on: June 26, 2019
    Keywords: Mathematics - Combinatorics,05C40, 94C15, 05D05

    Consultation statistics

    This page has been seen 646 times.
    This article's PDF has been downloaded 310 times.