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

zbMATH Open1490.05138arXiv2103.10041MaRDI QIDQ5080914FDOQ5080914

Authors: Yulan Chen, Weigen Yan, Yuqing Lin 

Publication date: 31 May 2022

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

Full work available at URL: https://arxiv.org/abs/2103.10041

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

zbMATH Keywords

Kneser graphsuper vertex cut

Mathematics Subject Classification ID

Connectivity (05C40)

Cites Work

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

Cited In (4)

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

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)