Maximum Average Degree of a graph

[ncohen]

The maximum average degree of a graph is the maximum, over all subgraphs H of a graph G, of average_degree(H).

This can be computed in polynomial time ( though I do not know of any practical way to do it ) and could be used, for example, as a certificate for negative answers in #7528.

Apply:

1. #8364
2. #8166
3. #2203
4. ​trac_7529.patch

Even applying in this order, you might get some fuzz. But that's OK and is not as bad as a hunk failure.

[ncohen]

After some thinking, is was easy to write it through Linear Programming :-)

I also wrote a pretty elementary average_degree function, that I had been missing for some time !

Nathann

[ncohen]

For an explanation of the Linear Program used to solve this problem, see the LP chapter from : ​http://code.google.com/p/graph-theory-algorithms-book/

Nathann

[wdj]

This installs fine on 4.4.2.a0, passes sage -testall both before and after installing glpk (except for unrelated failures).

Also, the docs look good and I tested it on other examples and it works as claimed:

sage: g = graphs.RandomGNP(20,.3) 
sage: h = graphs.RandomGNP(20,.2) 
sage: j = g+h
sage: j.density()
49/390
sage: h.density()
3/19
sage: g.density()
34/95
sage: RR(g.density())
0.357894736842105
sage: RR(h.density())
0.157894736842105
sage: j.maximum_average_degree()
34/5
sage: h.average_degree()
3
sage: g.average_degree()
34/5

[ncohen]

Thaaaaaaank you so much !!! The other LP tickets are just applications of the following thing : if a graph has maximum average degree strictly less than 2 ( so 2-epsilon in the code, or 1-epsilon as it is sometimes divided) then it is acyclic -> a forest !!

So this ticket really is they key to all others ! When I found how to solve this one I knew how to write the others, so there shouldn't be any surprise in them :-)

Thank you again !!

Nathann

[bascorp2]

​print pictures

[wdj]

Replying to bascorp2:

​print pictures

This looks like spam but I didn't try the link.