Another DeLaVina Idea

A follow-up thought from Ermelinda DeLaVina: “This morning I had this thought for another (maybe slight easier to compute) lower bound for the difficult graph J?`FBo{fdb?.

Let H be the subgraph induced by the non-maximum degree vertices. Then alpha(G) >= Residue(H).

This is another instance of “the corollary sometimes gives a better bound”.

Proof: Let S be any subset of vertices of G, and G[S] the subgraph induced by S. Then alpha(G) >= alpha(G[S]) >= Residue(G[S]).

When S is the set of non-maximum degree vertices, Residue(G) and Residue(G[S]) are non-comparable. To see this take J?`FBo{fdb?, and  a large enough complete graph with one edge subdivided, for instance.

It would be interesting if one could find an easily computed set that so that its residue is never worse than residue of the graph.”

In this case, alpha(G[S])=4, which is exactly the independence number of the difficult graph.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s