Maximum edge‐cuts in cubic graphs with large girth and in random cubic graphs
František Kardoš, Daniel Král͏̌, Jan Volec · Random Structures and Algorithms · 2012
Abstract We show that for every cubic graph G with sufficiently large girth there exists a probability distribution on edge‐cuts in G such that each edge is in a randomly chosen cut with probability at least 0.88672. This implies that G contains an edge‐cut of size at least 1.33008 n , where n is the number of vertices of G , and has fractional cut covering number at most 1.127752. The lower bound on the size of maximum edge‐cut also applies to random cubic graphs. Specifically, a random n ‐vertex cubic graph a.a.s. contains an edge‐cut of size 1.33008 n ‐ o ( n ). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012