Super-Connectivity and Hyper-Connectivity of Vertex Transitive Bipartite Graphs

摘要

A graph is said to be super-connected if every minimum vertex cut isolates a vertex. A graph is said to be hyper-connected if the deletion of each minimum vertex cut creates exactly two components, one of which is an isolated vertex. In this note, we proved that a vertex transitive bipartite graph is not super-connected if and only if it is isomorphic to the lexicographic product of a cycle C n (n ≥ 6) by a null graph N m . We also characterized non-hyper-connected vertex transitive bipartite graphs.