On the super (edge)-connectivity of generalized Johnson graphs

The paper studies the super edge connectivity of generalized Johnson graphs. It is shown that the Kneser graph \(G(n,k,0)\) is super-\(\kappa\) for \(n\ge2k+1\) and \(k\ge2\), where \(\kappa\) is the connectivity of the graph. It is well-known that when \(n\ge2k\), \(G(n,k,0)\) is a regular graph and each node has exactly \(\binom{n-k}{k}\) neighbors. Moreover, for \(n\ge2k+1\) and \(k\ge2\), the Kneser graph \(G(n,k,0)\) is super-\(\lambda\) and super-\(\lambda'\), where \(\lambda\) is the edge-connectivity and \(\lambda'(G(n,k,0))=2\binom{n-k}{k}-2\). In the same regime, the cyclic edge-connectivity \(\lambda_c\) of \(G(n,k,0)\) is also derived. It is shown that \(G(n,k,0)\) is super-\(\lambda_c\) for \(n\ge2k+1\) and \(k\ge2\). Analogously, the paper also shows that \(G(n,k,1)\) is super edge-connective and super restricted edge-connective.

Recommendations

Cites work

This page was built for publication: On the super (edge)-connectivity of generalized Johnson graphs

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