The super connectivity of the pancake graphs and the super laceability of the star graphs (Q557901)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The super connectivity of the pancake graphs and the super laceability of the star graphs |
scientific article |
Statements
The super connectivity of the pancake graphs and the super laceability of the star graphs (English)
0 references
30 June 2005
0 references
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.
0 references
Hamiltonian connected
0 references
Hamiltonian laceable
0 references
connectivity
0 references
0 references