The super-connectivity of Johnson graphs

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, tw...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-04
Main Authors: Ekinci, Gülnaz Boruzanlı, Gauci, John Baptist
Format: Article
Language:English
Subjects:
Apexes
Connectivity
Graph theory
Graphs
Integers
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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\).
ISSN:2331-8422
DOI:10.48550/arxiv.1906.06488