The first 24 bounds for the annihilation number were conjectured by Graffiti in about 2 and a half hour run. Three of these bounds are obvious but they are included here as examples of Invariant Interpolation Problems of the Second Kind (see IP1 - IP3 below).

Conjectures of this run were tested against an initial database of almost 200 graphs and then I used the interactive version of Graffiti to add to this database counterexamples to a few, perhaps as many as ten, early, conjectures most of which were clearly suggested by the sorting patterns. In particular one might say that I was not working on refuting these conjectures apart from perhaps two or three of them; even in those cases, I did not really have to work on counterexamples since the sorting patterns were quite clear. In principle they could be completely automated with early ideas of the Autograph version of Graffiti. Similarly as it was the case with Pepper's counterexample to conjecture 1009 other examples at this stage refuted several conjectures. The initial database of 200 previous counterexamples was limited to the current educational version of Graffiti. Most examples were very simple because I had to use coding sequence for this version, though in the last stage I wrote a simple program for generating coding sequences to take advantage of graph-building functions of earlier versions of Graffiti.

Let d₁, d₂, ... d_n be the degree sequence of a n-vertex graph G sorted in a non-decreasing order. The annihilation number of G is the largest integer k such that the partial sum d₁ + d₂ + ... d_k is not more than the number of edges of G. This concept, in a quite different ( in a sense dual to the residue) form was proposed by Ryan Pepper as an upper bound for the independence number, [P].

Upper Bounds for Annihilation Number

IP1. size + the number of isolated vertices.

This conjecture is included here along with IP2 and IP3 as an easy exercise for the case of equality, but also because it is an occasion to define and to show examples of Invariant Interpolation Problems of the Second Kind. Interpolation Problems of the first kind call for invention new invariants to "handle" objects which prevent Graffiti from hitting bingo for NP-hard invariants, [AF]. The purpose of Interpolation problems of the second kind is to prevent Graffiti from making trivial conjectures at all by inventing invariants leading to stronger conjectures. With early versions of Graffiti the proportion of trivial conjectures was the major problem. Even though, for all practical purposes, the Dalmatian version solved this problem (as for example this run shows), still one would like to have a program which makes no obvious conjectures at all. Basically, it is the same problem as the problem of strenghtening of a result if is too weak. The only difference is that in the realm of Graffiti, the solution must be given in the form of a new bound.

An alternative solution to this problem is to run conjectures about graphs excluding those that satisfy the equality in IP1 This is a solution and it is one of the Red Burton styles, which may be well worth to try with this version.

1007. 2(residue) + size - n.

1008. 2( the covering number) + residue.

1009. n/2 + the independence number - 1/2.

k20 + 19k3 is also a counterexample to 1012,1015,1016, 1018,1019. Ryan Pepper. 8. 22. '04.

IP2. n - 1 + the number of isolated vertices

IP3. n - 1 + the number of interior vertices

1010. 2 + the independence number + the number of edge connectors.

A counterexample can be obtained by taking a star on 8 vertices and adding one pendant to each of 6 of its 7 arms. This graph has degree sequnce {7,2,2,2,2,2,2,1,1,1,1,1,1,1}. Thus, A=10, alpha=7 (since it is a tree with a perfect matching), and there are no edge-connectors. Ryan Pepper. 8. 30. '04.

1011. 2 + the residue + the covering number

1012. n/2 + residue + 1/2 .

see 1009.

see 1009.

see 1009.

see 1009.

see 1009.

A counter-example to #1020 is a path on on 17 vertices with a pendant vertex attached to one of the degree two vertices. The maximum degree is three with frequency one, the number of connectors is three, hence the right hand side is nine -- but the annihilation number is 10. Ryan Pepper 5. 26. '05 1021. number of vertices of maximum degree + 2(1 + the number of exterior edges).

1022. residue + 4(the number of connectors)

A counter-example to #1022 is a path on 53 vertices. It has Residue of 18 and 2 connectors so the right hand side is 26. But the annihilation number is 27. Ryan Pepper 5. 26. '05

1023. n - half of the average degree

This conjecture was proved by Ryan Pepper using results from [P]. 8. 22. '04

1024. n - log of the number of interior edges - 0.208

1025. n - log of the coverning number - 0.901

1026. residue (1 + half of the average degree)

1027. 2(the independence number)(1 + number of vertices of the minimum degree) -1

1028. residue (1/2 + half of the number of connectors)

8. 22. '04.

Let m be the number of edges of a minimum maximal matching

1029. m is at least the annihilation number - the independence number.

8. 31. '04.

1030. the annihilation number is not more than the independence number + 2r, where r is the number of repetitions of positive terms of the coding sequence.

2. 16. '05.

Diamondoid graphs are usually defined informally as finite fragments of the diamond lattice, but the fate of conjectures below may very much depend on the precise mathematical definition of these objects. Similarly as it is the case with the benzenoid graphs it seems of interest to consider several classes of these objects depending for example on the nontriviality conditions and "topological" properties of diamondoids. An often implicitely assumed nontriviality condition, seem to be that every edge is contained in an adamantane and that the common part of two adamantane cells caontains a 6-cycle. A coding sequence of adamantane is 1 2 3 4 5 9 1 10 7 6 5 0 7 8 3. Pictures of this and other simplest diamondoids can be found for example on the ChevronTexaco websites and on a website of G. Ali Monsoori. . An introduction to diamondoids can be found in [B].

1031. the independence number of every diamondoid is equal to the the number of its non-negative eigenvalues, comp [S].

Graffiti made also a similar conjecture for non-positive eigenvalues suggesting that diamondoids are both helio- and geo-tropic plants:

1032. the independence number of every diamondoid is equal to the the number of its non-positive eigenvalues, comp [S].

1033. the independence number of every diamondoid is equal to the number of vertices minus their matching number.

2. 18. '05. These three conjectures suggested to me that diamondoids should be bipartite and Sandy Balaban, Doug Klein and Tom Schmalz told me today (i.e., two days after Graffiti made this conjecture) that this indeed is the case (which of course proves 1033

Doug's argument is crystal clear: the vertices of the diamondoid lattice D can be represented as triples with integer coefficients generated from D(0) consisting of the sigleton (0,0,0) by adding or subtracting a vector from the set S = {(1,1,1), (1,-1,-1), (-1,1,-1), (-1,-1,1)}. If p is a vector which (already) is in D(n) and all components of p are even then q = p + d also belongs to D for arbitrary d from S and q's determine all the (new) neighbors of p. Similarly, if all components of p from D are odd then q = p - d also belongs to D for arbitrary element d from set S and as before all the new adjacencies are again defined by vectors q.

Since diamondoids are bipartite, the above representation suggests that the arguments from [S] can be extended to prove 1031 for large class of diamondoids analoguous to hexagonal systems. The relation in conjecture 1031 was conjectured for benzenoids in 1001 of Pony Express. and it stated before for hexagonal systems by Gutman, [G], see however [S]. 2. 18. '05.

4. 18. '05. Peter John and Horst Sachs point out however that the arguments from [S] use also the planarity of benzenoids. 4. 18. '05.

The first Graffiti's conjecture of this run (listed as 1034 was obvious, but according to the program there are (at least) four (out of 10 diamondoid sequences constructed by Tim Bell) for which we have equality in the conjecture:

1034. the independence number of every diamondoid is at most the annihilation number.

However the very first diamondoid conjecture of Graffiti was listed appropriately in the Ashes and Diamonds:

1035 . the independence number of every diamondoid is equal to the chromatic number of its complement.

This conjecture was tested just against one example - the adamantane. Still it has crossed my mind at the time, that being diamondoids, these graphs should be perfect, and now indeed we know they are :-).

4. 29, '05 Following our discussions with Sandy Balaban, Doug wrote extensive and very informative notes on representation of diamondoids, [D]. 4. 29. '05. 5. 30 '05.

***

A conjecture of Graffiti not included previously in "Written on the Wall" , [W] was

1036 If R is the number of repetitions of a coding sequence of an Eulerian graph with V vertices and E edges then

R = E - V + 1

Later the program made also the conjecture that for every planar graph

PR = E - V +1

where PR is the number of repetitions of positive terms of the coding sequence, <> These two were some of the first conjectures of the educational (Red Burton) version of Graffiti and 1036 is discussed in [AF] and below

***

The next conjecture on this list originally had number 895, which is now the number of the first conjecture of the Minuteman version of Graffiti,[MM]. The file in which I found it was last time modified in July of '98, but I remember discussing this conjecture with Professor Cvetkovic in April '98 at a DIMACS meeting. I do not remember why I did not include this conjecture at once into WoW, but very likely I wanted to test it for larger graphs, as we did it later with my colleagues Ed Dean . My experience with Graffiti is that equalities conjectured by this program are as a rule true, though 446 discussed below was a marked exception. Large "touch" number also seems to be an indicator of correctness of conjectures, but this pattern is not nearly as clear as with the equalities. Most of the equalities conjectured by Graffiti in the past were trivially true as for example 1036 above, but (as I wrote in "Conjectures of Graffiti, II") in the future, it might happen, that the program will make an obvious, but nevertheless unanticipated conjecture. To me, the most startling feature of 1036, is not that it suggests the Euler characteristic formula, but that it contains a hint of a completely new proof of this formula.

I also seem to remember that I decided to run conjectures about separators of fullerenes, [MM], because of separator conjectures about masking graphs which are defined below. Ever since 1001 was proved by Horst Sachs, I often thought of rerunning the "masking" version, but eventually (particularly that I can not find it) I decided to use conjectures from notes about the original run. Horst's solution and now the diamondoid conjecture 1032 make plants even more interesting. In addition to this we have now a sensible question, namely what posets have the property that the size of their largest antichain is the same as the number of non-negative or non-positive eigenvalues of their comparability graphs.

1037 . If p and q are two natural numbers written in base 2 then p ≤ q means that every binary digit of p is less than or equal to the corresponding digit of q. To be more precise, let S(n) be the set of natural numbers k such that the coefficient of 2**k in the binary expansion of n is equal to 1. Then p ≤ q iff S(p) is a subset of S(q) The relation ≤ is called by Jones and Matiyasevich, the masking relation or masking poset , [JM]. The comparability graph of this relation on the set 0..n-1, will be called masking graph M(n) i.e., r is adjacent to s in M(n) if and only if r ≤ s or s ≤ r.

Conjecture. The size of he largest antichain of the masking poset equals to the number of non-negative eigenvalues of the masking graph.

In terminology of conjecture 345 (see also [CDS95] p. 146-147) this conjecture asserts that masking graphs are heliotropic plants. Similarly as in 446, Cvetkovic's spectral independence bound implies that the inequality holds true in one direction.

Conjecture 446 was asserting that the number of primes between 2 and n is exactly the number of non-negative eigenvalues of the graph with vertices 2..n, two of these numbers being adjacent iff they are not relatively prime. This conjecture turned out to be false, but if one could show that the difference between the corresponding invariants is not too large then this would imply the correctness of the Riemann Hypothesis. Conjecture 1037 seems also false for larger n. According to our correspondence with Ed Dean from July of '98, the conjecture seemed to be false for n around 2000. It would be nice to have an argument though, independent from possibility of numerical errors.

There is a considerable interplay between the Hilbert's 10th problem and the Riemann Hypothesis, see for example [CHW] or [DMR]. The latter discusses relationships between the Tenth problem and many other famous problems including for example Goldbach's and a strong version of the twin prime conjecture.

1038 The number of elements of the largest level of the masking poset is at least the number of different non-negative eigenvalues of its adjacency graph.

Level is the set of elements of the same height. The height of an element is the lenght of the longest strictly descending chain starting with this element; the smallest element has hight 0.

Interestingly there are quite a few graphs with equality.

1039 The number of elements of the largest level of the masking poset is at least as large as the difference between the first and the second eigenvalues (its separator).

1040 The number of distinct eigenvalues of the adjacency matrix of the complement of the masking graph is not more than the number of distinct eigenvalues of the Laplacian of the masking graph.

1041 The number of positive eigenvalues of the complement of the masking graph is not more than its separator.

1042 The separator of the complement of the masking graph is at least -1 + its Randic index.

1043 The multiplicity of the largest eigenvalue of Laplacian of the masking graph is at most the mean temperature.

1044 Residue of the masking graph is at most the number of levels.

The data seems to indicate that for about half of graph we have the equality and for the remaining the difference between the two invariants is 1. (As I said above, I can not find anymore the relevant part of the program, but retesting of this conjeture would be easy.)

1045 Residue of the masking graph is at most the number of distinct non-positive eigenvalues of the masking graph.

1046 Residue of the masking graph is at least the corank (i.e., n - rank) of the masking graph.

1047 Residue of the complement of the masking graph is at most 2 + frequency of the minimum eigenvalue of this graph.

The database seem to indicate that for many graphs we have equality.

1048 Let p(n) be the number of primes smaller or equal to n and let L be the largest eigenvalue of the masking graph M(n). Then p(n) ≤ 1 + L.

6. 5. '05. I tested this conjecture up to n = 165 and so far it seem correct. I would expect nevertheless a counterexample around n = 200. By comparison, the current data seem to suggest that the next conjecture i.e., 1049 is correct. Still the first two eigenvalues of the masking graph seem to me now much less predictable than I first thought, so it is hardly obvious to me how indicative is the current data. 6. 05. '05.

6. 8. '05. The smallest counterexample seems to be n = 313. I am grateful to Inga Matthews who isolated spectral procedures of Graffiti to make possible testing larger graphs. It certainly would be a good idea to confirm these computations with a well tested numerical software. 6. 8. '05.

1049 Separator of the eigenvalues of the masking graph is at most 1 + the number of primes (strictly) less than the number of its vertices.

1050 Separator of the eigenvalues of the masking graph is at most 1 + the number of elements of the largest level.

1051 Let MXI(G) be the worst performance of Maxine for a graph G.

Conjecture: Mean dual degree of the masking graph is not more than 1 + MXI.

Note that this conjecture would be much weaker if the right hand side were replaced by the indpendence number.

1052 Separator of the masking graph is not more than 1 + MXI

See the previous conjecture for the comment definition and a definition of MXI.

References

[B] Alexandru T. Balaban and Paul Von Rague Schleyer, Systematic Classification and Nomenclature of Diamondoid Hydrocarbons, I, Tetrahedron Vol. 34 pp. 3599-3609.

[CHW] S. Chowla, The Riemann Hypothesis and Hilbert's Tenth Problem, Gordon and Breach, 1965.

[CDS95], D.Cvetkovic, M.Doob, H.Sachs, Spectra of Graphs - Theory and Applications, 3rd revised and enlarged edition, Johann Ambrosius Barth Verlag, Heidelberg - Leipzig, 1995.

[DMR] Martin Davis, Yurij Matiyasevich and Julia Robinson, Hilberts's Tenth Problem Diophantine Equations: Positive Aspects of a Negative Solution, Mathematical Developments from Hilbert Problems, AMS 1976.

[D] DJK, ATB and SF, Diamondoids.

[AF] S. Fajtlowicz, Toward Fully Automated Fragments of Graph Theory, Graph Theory Notes of NY Academy of Sciences, XLII, 2002.

[S] S. Fajtlowicz, Peter John and Horst Sachs, On Maximum Matchings and Eigenvalues of Benzenoid Graphs, to appear in Croatica Chemica Acta.

[W] Written on the Wall, a list of conjectures of Graffiti available on the website of Craig Larson.

[W] Minuteman Conjectures, a list of conjectures of Graffiti available on the website of Craig Larson.

[G] I.Gutman, Characteristic and matching polynomials of benzenoid hydrocarbons J.Chem.Soc.Faraday Trans. 2 79 (1983) 337-345.

[JM] J. P. Jones and Y. V. Matiyasevich, Proof of Recursive Unsolvability of Hilbert's Tenth Problem. American Mathematical Monthly, 98 (1991) 689-709.

[M] Y. V. Matiyasevich, Hilbert's Tenth Problem, MIT Press, Cambridge, 1993.

[P] R. Pepper, Binding Independence, PhD dissertation, August 2004.