On the density of nearly regular graphs with a good edge-labelling

Details On the density of nearly regular graphs with a good edge-labelling On the density of nearly regular graphs with a good edge-labelling

2011-10-11

arxiv.org/abs/1110.2391v1

Mathematics

Combinatorics

5 pages

Scientific paper

A good edge-labelling of a simple graph is a labelling of its edges with real numbers such that, for any ordered pair of vertices (u,v), there is at most one nondecreasing path from u to v. Say a graph is good if it admits a good edge-labelling, and is bad otherwise. Our main result is that any good n-vertex graph whose maximum degree is within a constant factor of its average degree (in particular, any good regular graph) has at most n^{1+o(1)} edges. As a corollary, we show that there are bad graphs with arbitrarily large girth, answering a question of Bode, Farzad and Theis. We also prove that for any Delta, there is a g such that any graph with maximum degree at most Delta and girth at least g is good.

Affiliated with

Also associated with

No associations

Rating

On the density of nearly regular graphs with a good edge-labelling 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 On the density of nearly regular graphs with a good edge-labelling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the density of nearly regular graphs with a good edge-labelling will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-472135