Cvetkovic better than Lovasz

I ran some independence number upper bound conjectures as a test – I included only Lovasz’ theta number in the “upper bound theory” for alpha. I was surprised to see conjectures involving Cvetkovic’s bound (the minimum of the numbers of nonnegative and nonpositive eigenvalues). Ordinarily Lovasz is always a better bound. But the conjectures, if things were working right, showed that there must be some graph in the database where Cvetkovic was lower than Lovasz. It turned out to be the Clebsch Graph!

Here Cvetkovic = alpha = 5, while the Lovasz number is 6.

Here are the graphs the program currently knows, along with values for the independence numbers, Lovasz theta number and Cvetkovic’s bound. You can see how amazing the Lovasz number is as an alpha bound. (The graphs and invariants can be hound in our master graph theory file.)

Complete graph alpha = 1, lozasz = 1.0, cvetkovic = 1

Complete graph alpha = 1, lozasz = 1.0, cvetkovic = 1

Complete graph alpha = 1, lozasz = 1.0, cvetkovic = 1

c6ee alpha = 2, lozasz = 2.0, cvetkovic = 3

c5chord alpha = 2, lozasz = 2.0, cvetkovic = 3

Dodecahedron alpha = 8, lozasz = 8.541, cvetkovic = 11

c8chorded alpha = 3, lozasz = 3.0, cvetkovic = 4

c8chords alpha = 4, lozasz = 4.0, cvetkovic = 4

Clebsch graph alpha = 5, lozasz = 6.0, cvetkovic = 5

Cycle graph alpha = 2, lozasz = 2.0, cvetkovic = 3

prismy alpha = 4, lozasz = 4.0, cvetkovic = 4

c24 alpha = 9, lozasz = 10.404, cvetkovic = 11

c26 alpha = 11, lozasz = 11.377, cvetkovic = 11

Bucky Ball alpha = 24, lozasz = 26.833, cvetkovic = 30

c6xc6 alpha = 18, lozasz = 18.0, cvetkovic = 23

holton_mckay alpha = 10, lozasz = 10.838, cvetkovic = 12

sixfour alpha = 4, lozasz = 4.0, cvetkovic = 5

Petersen graph alpha = 4, lozasz = 4.0, cvetkovic = 4

Path Graph alpha = 1, lozasz = 1.0, cvetkovic = 1

Tutte Graph alpha = 19, lozasz = 20.615, cvetkovic = 21

non_ham_over alpha = 4, lozasz = 4.0, cvetkovic = 4

throwing alpha = 4, lozasz = 4.0, cvetkovic = 5

throwing2 alpha = 4, lozasz = 4.0, cvetkovic = 5

throwing3 alpha = 4, lozasz = 4.0, cvetkovic = 6

kratsch_lehel_muller alpha = 6, lozasz = 6.0, cvetkovic = 6

Star graph alpha = 3, lozasz = 3.0, cvetkovic = 3 Bull graph alpha = 3, lozasz = 3.0, cvetkovic = 3

Chvatal graph alpha = 4, lozasz = 4.893, cvetkovic = 6

Desargues Graph alpha = 10, lozasz = 10.0, cvetkovic = 10

Diamond Graph alpha = 2, lozasz = 2.0, cvetkovic = 2

Flower Snark alpha = 9, lozasz = 9.472, cvetkovic = 10

Frucht graph alpha = 5, lozasz = 5.0, cvetkovic = 6

Hoffman-Singleton graph alpha = 15, lozasz = 15.0, cvetkovic = 21

House Graph alpha = 2, lozasz = 2.0, cvetkovic = 3

House Graph alpha = 2, lozasz = 2.0, cvetkovic = 2

Octahedron alpha = 2, lozasz = 2.0, cvetkovic = 4

Thomsen graph alpha = 3, lozasz = 3.0, cvetkovic = 5

Pappus Graph alpha = 9, lozasz = 9.0, cvetkovic = 11

Grotzsch graph alpha = 5, lozasz = 5.0, cvetkovic = 5

Gray graph alpha = 27, lozasz = 27.0, cvetkovic = 35

Heawood graph alpha = 7, lozasz = 7.0, cvetkovic = 7

Herschel graph alpha = 6, lozasz = 6.0, cvetkovic = 7

Schläfli graph alpha = 3, lozasz = 3.0, cvetkovic = 7

Coxeter Graph alpha = 12, lozasz = 12.485, cvetkovic = 13

Brinkmann graph alpha = 7, lozasz = 8.342, cvetkovic = 9

Tutte-Coxeter graph alpha = 15, lozasz = 15.0, cvetkovic = 20

Robertson Graph alpha = 7, lozasz = 7.441, cvetkovic = 8

Folkman Graph alpha = 10, lozasz = 10.0, cvetkovic = 15

Balaban 10-cage alpha = 35, lozasz = 35.0, cvetkovic = 36

Tietze Graph alpha = 5, lozasz = 5.0, cvetkovic = 6

Sylvester Graph alpha = 12, lozasz = 13.5, cvetkovic = 17

Szekeres Snark Graph alpha = 21, lozasz = 22.537, cvetkovic = 24

Moebius-Kantor Graph alpha = 8, lozasz = 8.0, cvetkovic = 8

ryan alpha = 8, lozasz = 8.0, cvetkovic = 13

inp alpha = 4, lozasz = 4.107, cvetkovic = 5

c4c4 alpha = 4, lozasz = 4.0, cvetkovic = 5 regular_non_trans alpha = 3, lozasz = 3.0, cvetkovic = 3

bridge alpha = 2, lozasz = 2.0, cvetkovic = 2

z1 alpha = 2, lozasz = 2.0, cvetkovic = 2 Meredith Graph alpha = 34, lozasz = 34.489, cvetkovic = 45

 

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