Publication details
Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs
| Authors | |
|---|---|
| Year of publication | 2012 |
| Type | Article in Periodical |
| Magazine / Source | RANDOM STRUCTURES & ALGORITHMS |
| Citation | |
| Doi | http://dx.doi.org/10.1002/rsa.20471 |
| Keywords | cubic graphs; random graphs; large girth; edge-cut |
| Description | We show that for every cubic graph Gwith sufficiently large girth there exists a probability distribution on edge-cuts in Gsuch that each edge is in a randomly chosen cut with probability at least 0.88672. This implies that Gcontains an edge-cut of size at least 1.33008n, where nis 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.33008n- o(n). (c) 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 |