Sunday, September 16, 2007

Random graph labelings

OK. Here's what I think I maybe've got:

Let G be the random graph G(n,M) on n vertices and M edges. Then RS(G) = O(M*\delta(G)).

Proof (outline): Set the implied constant in the big-O notation as k, to be determined later.

Base Case: M = 0; trivial.

For M>0, choose a vertex v with degree \delta(G), and remove an edge incident to it to obtain the graph G'. Then, by the IH, RS(G') \leq k*(M-1)*(\delta(G)-1) = k*M*\delta(G)-(kM+k\delta(G)-1). For suitable k (I suspect), the probability that there exists some number in [0, kM+k\delta(G)-1] which we can add to the label on v so that the labeling remains range-relaxed graceful is 1.

...Yeah. I guess I hope that this is workable? I dunno though. Eh.

No comments: