Opened 11 years ago

Closed 11 years ago

# Maximum Average Degree of a graph

Reported by: Owned by: ncohen rlm major sage-4.4.4 graph theory sage-4.4.4.alpha0 Nathann Cohen David Joyner N/A

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:

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

### comment:1 Changed 11 years ago by ncohen

• Status changed from new to needs_review

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

### comment:2 Changed 11 years ago by 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

### comment:3 Changed 11 years ago by wdj

• Status changed from needs_review to positive_review

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
```

### comment:4 Changed 11 years ago by 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

### comment:5 Changed 11 years ago by mvngu

• Authors set to Nathann Cohen
• Description modified (diff)
• Reviewers set to David Joyner