First Conjecture Module Testing Run

Here’s the first run of conjectured lower bounds for the independence number of a graph. We started only with the difficult graph J?`FBo{fdb?. We generate conjectures that are:

1) true for all the graphs that are stored in the database, and where

2) a conjecture is only added if it gives a better value (here, conjectured lower bound) than any of the other conjectures.

This means that there can never be more conjectures than there are stored graphs. The first timeout for the program is if there is a conjecture that gives the exact value for independence number for each of the user-supplied graphs (otherwise, there is a hard-coded timeout magic number for stopping time).

Ryan Pepper, always great at finding counterexamples, contributed most of the counterexamples here. Patrick found the rest. After a counterexample was found, it was added to the program. Hence, there is no way the program can make the same false conjecture on the next round.

We interpreted the conjectures as being true for all connected graphs. Of course, for the purposes of INP the class we interpreted over could have been much smaller (just the class of graphs having the same properties that we know J?`FBo{fdb? has).

Round 1.

Graphs: J?`FBo{fdb?

Conjectured lower bounds:  2*diameter

Counterexample: P2

Round 2.

Graphs: J?`FBo{fdb?, P2

Conjectured lower bounds:  a) diameter^2, b) average_distance^2

Counterexample: P3 is a counterexample to (a)

Round 3.

Graphs: J?`FBo{fdb?, P2, P3

Conjectured lower bounds:  a) annihilation-diameter, b) average_distance^2, c) diameter

Counterexample: P4 to (c)

Round 4.

Graphs: J?`FBo{fdb?, P2, P3, P4

Conjectured lower bounds:  a) annihilation-diameter, b) average_distance^2, c) radius, d) residue (Note: these last two are famous conjectures of Fajtlowicz’s Grafitti program)

Counterexample: K6 to (a)

Round 5.

Graphs: J?`FBo{fdb?, P2, P3, P4, K6

Conjectured lower bounds:  a) average_distance, b) radius*residue-diameter, c) radius, d) residue (Note: the first one is also a famous conjectures of Fajtlowicz’s Grafitti program)

Counterexample: C4* to (b). C4*is C4 with a triangle amalgamated to each vertex (so n(C4*)=12).

Round 6.

Graphs: J?`FBo{fdb?, P2, P3, P4, K6, C4*

Conjectured lower bounds:  a) average_distance, b) 2*residue-diameter, c) radius, d) residue

Counterexample: S4 is a counterexample to (b). S4 is the star on 4 vertices.

Round 7.

Graphs: J?`FBo{fdb?, P2, P3, P4, K6, C4*, S4

Conjectured lower bounds:  a) average_distance, b) order-Max_degree-diameter, c) radius, d) residue

Counterexample: K6-K6 is a counterexample to (b). K6-K6 is two complete graphs on 6 vertices joined by an edge.

Round 8.

Graphs: J?`FBo{fdb?, P2, P3, P4, K6, C4*, S4, K6-K6

Conjectured lower bounds:  a) average_distance, b) cvetkovic-min_degree-order, c) radius, d) residue

Counterexample: K3,3 is a counterexample to (b).

Round 9.

Graphs: J?`FBo{fdb?, P2, P3, P4, K6, C4*, S4, K6-K6, K3,3

Conjectured lower bounds:  a) average_distance, b) cvetkovic-diameter, c) radius, d) residue

Counterexample: K4,4 is a counterexample to (b).

Round 10.

Graphs: J?`FBo{fdb?, P2, P3, P4, K6, C4*, S4, K6-K6, K3,3, K4,4

Conjectured lower bounds:  a) average_distance, b) radius, c) residue, d) sqrt(szeged_index)/max_degree, e) sqrt(szeged_index/diameter)/min_degree(G)

Counterexample: C5 is a counterexample to (d), K4+pendant is a counterexample to (e).

Round 11.

Graphs: J?`FBo{fdb?, P2, P3, P4, K6, C4*, S4, K6-K6, K3,3, K4,4, C5, K4+pendant

Conjectured lower bounds:  a) average_distance, b) radius, c) residue, d) -2*diameter+order-min_degree, e) szeged_index/(matching_number*size)

Counterexample: K7+pendant is a counterexample to (d)

Round 12.

Graphs: J?`FBo{fdb?, P2, P3, P4, K6, C4*, S4, K6-K6, K3,3, K4,4, C5, K4+pendant, K7+pendant

Conjectured lower bounds:  a) average_distance, b) radius, c) residue, d) -(girth-cvetkovic- annihilation_number)/diameter, e) szeged_index/(matching_number*size)

Counterexample: K6,6 is a counterexample to (d)

Round 13.

Graphs: J?`FBo{fdb?, P2, P3, P4, K6, C4*, S4, K6-K6, K3,3, K4,4, C5, K4+pendant, K7+pendant, K6,6

Conjectured lower bounds:  ?

Counterexample: ?

And that’s where things stand at the moment.

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