24th Cumberland Conference on Combinatorics, Graph Theory, and Computing
24th Cumberland Conference on Combinatorics, Graph Theory, and Computing
Connectivity and edge-connectivity of a graph measure the number of vertices or edges that must be deleted to disconnect it but do not give a refined enough measure of the “global (edge) connectedness” of the graph. To measure this, average connectivity and average edge connectivity have been introduced. We prove a relationship between the average connectivity and the matching number in all graphs. We also give the best lower bound for the average edge-connectivity over $n$-vertex connected cubic graphs, and we characterize the graphs where equality holds. In addition, we show that this family has the fewest perfect matchings among cubic graphs that have perfect matchings.