The super connectivity of the pancake graphs and the super laceability of the star graphs (Q557901)

A \(k\)-container \(C(u,v)\) of a graph \(G\) is a set of \(k\)-disjoint paths joining \(u\) to \(v\). A \(k\)-container \(C(u,v)\) of \(G\) is a \(k^*\)-container if it contains all the vertices of \(G\). A graph \(G\) is \(k^*\)-connected if there exists a \(k^*\)-container between any two distinct vertices. Let \(k(G)\) be the connectivity of \(G\). A graph \(G\) is super connected if \(G\) is \(i^*\)-connected for all \(i\) between 1 and \(k(G)\). A bipartite graph \(G\) is \(k^*\)-laceable if there exists a \(k^*\)-container between any two vertices from different parts of \(G\). A bipartite graph \(G\) is super laceable if \(G\) is \(i^*\)-laceable for all \(i\) between 1 and \(k(G)\). It is proved that the \(n\)-dimensional pancake graph \(P_n\) is super connected if and only if \(n\) is not equal to 3 and the \(n\)-dimensional star graph \(S_n\) is super laceable if and only if \(n\) is not equal to 3.