The super-connectivity of the Kneser graph KG(n,3)

MaRDI QIDQ5080914zbMATH OpenFDO

Authors Yulan Chen, Weigen Yan, Yuqing Lin

Publication date 31 May 2022

Full work available at URL https://arxiv.org/abs/2103.10041, http://ajc.maths.uq.edu.au/pdf/82/ajc_v82_p201.pdf

zbMATH Keywords

Kneser graphsuper vertex cut

Mathematics Subject Classification ID

Connectivity (05C40)

Abstract: A vertex cut $S$ of a connected graph $G$ is a subset of vertices of $G$ whose deletion makes $G$ disconnected. A super vertex cut $S$ of a connected graph $G$ is a subset of vertices of $G$ whose deletion makes $G$ disconnected and there is no isolated vertex in each component of $G-S$. The super-connectivity of graph $G$ is the size of the minimum super vertex cut of $G$. Let $KG(n,k)$ be the Kneser graph whose vertices set are the $k$-subsets of $1,cdots,n$, where $k$ is the number of labels of each vertex in $G$. We aim to show that the conjecture from Boruzanli and Gauci cite{EG19} on the super-connectivity of Kneser graph $KG(n,k)$ is true when $k=3$.

Recommendations

• The super-connectivity of Kneser graphs
• On the super connectivity of direct product of graphs
• On super i‐connected graphs
• The super-connectivity of Johnson graphs
• The super-connectivity of double generalized Petersen graphs

Cites work

• Conditional connectivity
• Connectivity of transitive graphs
• Hamiltonian uniform subset graphs
• On restricted connectivities of permutation graphs
• The super-connectivity of Kneser graphs

Cited in

(4)

• The super-connectivity of Kneser graphs
• On the \(p\)-restricted edge connectivity of the bipartite Kneser graph \(H(n,k)\)
• The super-connectivity of Johnson graphs
• On the super (edge)-connectivity of generalized Johnson graphs

This page was built for publication: The super-connectivity of the Kneser graph \(KG(n,3)\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5080914)