Even minus Even Horizontal

Let v be a vertex of a connected graph G. Let Even be the number of vertices at even distance from v in G. Let EvenH be the number of edges induced by this same set of vertices. Fajtlowicz observed (in Written on the Wall) that this in a lower bound for the independence number. Now take the max over all vertices. It is easy to see, because distances can be computed efficiently, that this invariant can be computed efficiently.

In the case of the last difficult graph, this invariant is 3, the independence number. If we can find an upper bound that gives 3, then we can predict the independence number of this graph.

For more information and results about this invariant, see Michelle Grigsby’s MS thesis.


3 thoughts on “Even minus Even Horizontal

  1. Pingback: Characterizing graphs where alpha = even-minus-even-horizontal | The Independence Number Project

  2. Pingback: More Even Minus Even Horizontal | The Independence Number Project

  3. Pingback: Solutions and Problems | The Independence Number Project

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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