Many very small graphs have a non-empty KE part

Any graph can be broken up into 2 subgraphs, one of which is Konig-Egervary (KE) and the other of which has the property that non-empty independent sets have more neighbors. Following a conjecture of Fajtlowicz, Carl Yerger has shown that almost all graphs have an empty KE part. Many very small graphs have a non-empty KE part. These graphs are “reducible”: calculating the independence number for them efficiently reduces to the problem of calculating the independence number of a proper subgraph. Here’s the data:

there are 11 graphs with 4 vertices
there are 10 graphs with non-empty KE component

there are 34 graphs with 5 vertices
there are 25 graphs with non-empty KE component

there are 156 graphs with 6 vertices
there are 124 graphs with non-empty KE component

there are 1044 graphs with 7 vertices
there are 616 graphs with non-empty KE component

there are 12346 graphs with 8 vertices
there are 7065 graphs with non-empty KE component

there are 274668 graphs with 9 vertices
there are 90034 graphs with non-empty KE component

Advertisements

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