Abstract

In this talk we consider edge-connectivity properties of connected graphs whose automorphism group has two orbits of the same size, called double-orbit graphs. The edge-connectivity of a connected graph is the minimum size of a set of edges whose deletion disconnects the graph. The edge-connectivity of a graph is naturally limited by its minimum degree, thus a graph is called maximally edge-connected if its edge-connectivity is equal to its minimum degree. A maximally edge-connected graph is super edge-connected if, in addition, every disconnecting set of edges of minimum size isolates a vertex. The restricted edge-connectivity of a connected graph is the minimum size of a set of edges whose deletion disconnects the graph but does not isolate any vertex. The restricted edge-connectivity of a graph is limited by the minimum size of a set of edges whose deletion isolates an edge but not any vertex. A graph reaching this limit is called lambda'-optimal.

We will characterize when double-orbit graphs are maximally edge-connected and super edge-connected. We also obtain a sufficient condition for certain double-orbit graphs to be lambda'-optimal. Furthermore, by applying our results we obtain some results on vertex/edge-transitive bipartite graphs, mixed Cayley graphs and half vertex-transitive graphs.

Tuesday, September 11, 2012

3:00– 4:00 P.M.

372 Science and Engineering Building

(Refreshments at 2:30-3:00 PM in the kitchen area adjacent to 368 SEB)