Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs

Details Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs

2011-08-31

arxiv.org/abs/1108.6280v3

Mathematics

Combinatorics

Scientific paper

We show that for every cubic graph G with sufficiently large girth there exists a probability distribution on edge-cuts of 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.33008n, where n is the number of vertices of G, and has fractional cut covering number at most 1.12776. 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.

Affiliated with

Also associated with

No associations

Rating

Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-626221