Conjecture of Graffiti.pc

Written on the Wall II

Ermelinda DeLaVina (delavinae@uhd.edu)

Lower bounds for maximum number of leaves over all spanning trees, L_s(G)

T 1. If G is a simple connected graph, then L_s(G) ≥ n + 1 - 2m(G) definitions reference
1996. In 1984, Hedetniemi and Laskar [HL] proved that for simple connected graphs L_s(G) ≥ n - 2m(G). In 1996, Fajtlowicz proved that for connected graphs on at least two vertices L_s(G) ≥ n + 1 - 2m(G) and later send the following.
Dec 12, 2004 Fajtlowicz. Let T be a spanning tree containing a maximum matching. Then Graffiti's conjecture follows (for graphs with at least one edge) from the

Lemma. Let T be a n-vertex tree with L endpoints and n > 1. If T has a matching with m edges then L > n - 2m.

Proof: We can assume that n > 3. *Suppose T has two leaves adjacent to a vertex u of degree > 2. Let T' be the tree obtained from T by deletion of one of these leaves,* and let n', L' and m' be the corresponding invariants of T'. Since n' > 1, by induction on n we have that L' > n' - 2m'. Because deg(u) > 2, it follows that L' = L-1, and m' = m. Thus

L - 1 > n - 1 - 2m' , i.e., L > n - 2m.

Suppose now that T has a leaf adjacent to a vertex of degree 2 and let T' be the tree obtained from T by deleting this leaf and its unique neighbor *u*. Clearly m'= m-1 in this case and L' = L if the degree of the other neighbor of u is 2 and L-1 otherwise. In either of these two cases we have

L >= L' > n' - 2m' >= n - 2 - 2 (m-1) = n - 2m

and the theorem again follows by induction on n, because n' > 1.

T 3. If G is a simple connected graph, then L_s(G)≥ g_i(G) * maximum temp(v) definitions

1996. Mar. 17, 2004: Ryan Pepper " Here, MID is the number of vertices in a minimum independent dominating set. Take any vertex v of max degree D from graph G with n vertices and remove all vertices adjacent to v leaving G'. Now, any independent dominating set of G' must include v and so is also an independent dominating set of G. But there are at most n-D vertices in any independent dominating set of G'. Therefore, MID <= n-D, since MID is cardinality of a minimum independent dominating set. The rest of proof is as even more of an exercise than this and goes as follows. For any graph, max(temp) <= D/(n-D), D is max degree. So,
MID(max(temperature)) <= (n-D)D/(n-D) = D <= Max number of leaves of spanning tree.

The last inequality because, starting from a vertex x of maximum degree, we can build a spanning tree by including first all vertices of distance one from x, then all vertices of distance two from x, etc .... This will give spanning tree with a vertex of maximum degree D, and every tree has at least as many leaves as its maximum degree."

T 4. If G is a simple connected graph, then L_s(G) ≥ minimum of |N_G(e)| - 1 definitions reference
1996. DeLaVina 1996

T 5. If G is a simple connected graph, then L_s(G) ≥ maximum{| S(v, rad(G)) |: v is a center of G} definitions reference
1996. DeLaVina and Fajtlowicz 1996

T 6. If G is a simple connected graph, then L_s(G) ≥ 1 + n -m(G)- a(G) definitions reference
1996. DeLaVina 1996

T 7. If G is a simple connected graph, then L_s(G) ≥ maximum of l(v) -1 + n - 2a(G) definitions reference
1996. DeLaVina, Fajtlowicz, Waller (2002)

T 8. If G is a simple connected graph, then L_s(G) ≥ maximum of dist_even(v) - a(G) definitions reference
1996. DeLaVina 1996

Lower bounds for the path covering number of trees, p(T).

E 9. If T is a tree, then p(T) ≥ D(T) -1 definitions reference
2001

E 10. If T is a tree, then p(T) ≥ CEIL(L(T)/2) definitions reference
2001

E 11. If T is a tree, then p(T) ≥ 2a(T) - n definitions reference
2001

E 12. If T is a tree, then 2a(T) - n ≥ maximum of dist_even(v) - minimum of dist_even(v) definitions reference
2001

Lower bounds on the bipartite number of simple connected graphs, b(G).

T 13. If G is a simple connected graph, then b(G) ≥ diam(G) + maximum of l(v) -1 definitions reference
July 3, 2003. DeLaVina and Waller 2004.

T 14. If G is a simple connected graph, then b(G) ≥ diam(G) + f_G(1) -1 definitions reference
July 3, 2003. DeLaVina and Waller 2003

R 15. If G is a simple connected graph, then b(G) ≥ 2rad(G) definitions reference
July 3, 2003. This was proven by Fajtlowicz, 1988. Waller sent an alternate proof 2003.

T 16. If G is a simple connected graph, then b(G) ≥ 2(rad(G)-1) + maximum of l(v) definitions reference

July 3, 2003.
July 26, 2003 Bill Waller shows, by proof similar to Favaron's for a(G) ≥ rad(G), that b(G) ≥ 2rad(G) + maximum of l(v) - 5.

Mar. 17, 2004: Ryan Pepper communicated that he could prove f(G) ≥ diam(G) + maximum of l(v) - 3.

Note: A second run of the program was conducted for forest number (see conjectures 57-67.) Mar. 25, 2004: In a second run for forest the program conjectured f(G) ≥ diam(G) + maximum of l(v) - 2. It is conjecture 67.
Nov. 25, 2006 The conjectured relation follows for a tree T since diam(T) ≥ 2rad(T) -1 and by wowII #13 it follows that b(T) ≥ diam(T) + maximum of l(v) -1.
Jan. 2008: DRW

T 17. If G is a simple connected graph, then b(G) ≥ a(G) + CEIL(diam(G)/3) definitions

July 3, 2003. Independently proven by Benny John, UHD (Dec. 2005) and David Schindl,Gerard Univ (Jan. 2006).

T 18. If G is a simple connected graph, then b(G) ≥ a(G) + CEIL(sqrt(dist_max(M))) definitions

July 3, 2003. July 2005, for large enough diameter this follows from conjecture #17. Feb. 21, 2006 Benny John generalized Schindl's proof of 17 to prove #18..

T* 20. If G is a simple connected graph, then b(G) ≥ n/FLOOR[deg_avg(G)] definitions reference

July 3, 2003.
Mar 06, 2004, Bill Waller observes that for graphs that are p-regular and K_p-free, f(G) ≥ n/FLOOR[deg_avg(G)] (see conjecture #50 below) follows from Fajtlowicz's result on the independence ratio that for graphs with max. degree at most p and K_q-free, a(G)/n ≥ 2/(p+q).

Mar. 07, 2004, Fajtlowicz sent a proof of f(G) ≥ n/deg_avg(G), see conjecture #50.

T 27. If G is a simple connected graph, then b(G) ≥ (minimum of |N(e)|)^1-t(G) definitions

July 3, 2003. ** Mar. 17 2004: thanks to Ryan Pepper for alerting me to a typo in this statement.
Mar. 19, 2004: Pepper sent a proof of a bound on b in terms of the degree of an edge which is stronger for triangle-free graphs, and notes that for t(G) ≥ 1, 1 ≥ (minimum of |N(e)|)^1-t(G).

T 29. If G is a simple connected graph, then b(G) ≥ dist_max(A)+ 1/(n mod D(G)) definitions

July 3, 2003. The expression on the right is undefined for some graphs. The conjecture is made for those graphs for which is is defined. June 2005, this follows from b(G) ≥ diam(G)+ 1.

Lower bounds on the path number of simple connected graphs, path(G).

R 31. If G is a simple connected graph, then path(G) ≥ 2rad(G) - 1 definitions reference
July 15, 2003. This is Chung's Lemma, see reference.

R 31a. If G is a simple connected graph, then path(G) ≥ 2ecc(Centers) + 1 definitions reference

Summer 2003. This is offers an improvement over Chung's Theorem see wowII #31, when rad(G) = ecc(centers). June 2005, Waller noticed that conjecture follows from a Theorem of Basco and Tuza (see reference).

R 35. If G is a simple connected graph, then path(G) ≥ 1 + diam(G) definitions reference
July 15, 2003. This could also have been labeled an exercise, but since it was noted in the cited reference we include it here as a rediscovery.

Lower bounds on the forest number of simple connected graphs, f(G).

Note: Clearly b(G) ≥ f(G) ≥ path(G), and note that f(G) and path(G) were not available to the program when lower bounds for b(G) were generated.

E 37. If G is a simple connected graph, then f(G) ≥ path(G) definitions

Mar 05, 2004.

R 47. If G is a simple connected graph, then f(G) ≥ diam(G) + f_G(1) -1 definitions reference

Mar 05, 2004. This is a rediscovery since Waller and I knew it to be true from our work on b(G). DeLaVina and Waller 2003, see #14 above.

T 48. If G is a simple connected graph, then f(G) ≥ girth(G) + f_G(1) -1 definitions reference

Mar 05, 2004. The proof is similar to that of #47. DeLaVina and Waller 2004. *must check algorithm for circumference.

T* 50. If G is a simple connected graph, then f(G) ≥ n/FLOOR[deg_avg(G)] definitions reference

Mar 05, 2004. Note conj. #20 of wowII is b(G) ≥ n/FLOOR[deg_avg(G)].
Mar 06, 2004, Bill Waller observes that for graphs that are p-regular and K_p-free, f(G) ≥ n/FLOOR[deg_avg(G)] follows from Fajtlowicz's result on the independence ratio that for graphs with max. degree at most p and K_q-free, a(G)/n ≥ 2/(p+q).[F]

Mar 07, 2004, DeLaVina: I came across a paper [BB] (see reference link) by Bau and Beineke on n(G) - f(G), which they called the decycling number of a graph. In their paper they cite a result of Zheng and Lu in [ZL] that for cubic graphs without triangles and n not 8, f => n - ceil[n/3] (settling a conjecture by Bondy, Hopkins and Staton [BHS].) Zheng and Lu's bound for cubic triangle-free graphs is an improvement over the above. Bau and Beineke also cite other results on the decycling number, they write "A sharp upper bound for the decycling number of cubic graphs has been obtained in [LZ] by Liu and Zhao and that for connected graphs with maximum degree 3 has been obtained in [AMT]."
Mar. 07, 2004, Fajtlowicz sent a proof of f(G) ≥ n/deg_avg(G)
"The algorithm is as the proof which essentially shows how to find a forest of size n/A, where A is the average degree.

Proof: We can assume that G has no isolated points. Let's order vertices at random and starting with empty set F, let us keep adding to F a vertex v, if F + {v} is an induced forest. We add suitable vertices to F in order they are listed. Let d be the degree of v. The probability that v will eventually land in F is at least 2/(d+1), because that's the probability that v is the first or the second on the list of v +{neighbors of v}. Adding such vertices keeps F acyclic.

Let f(v) = 1 if v is in F and zero otherwise. By linearity, The expected value of f is at least R = sum 1/d, where the summation is over the degree sequence D, because for d >= 1, 2/(d+1) >= 1/d. Since that is the expected value then there is at least one ordering for which |F| is at least R.

This is a version of Caro-Wei bound for forests rather than the independence number and the idea of the proof is the same as Shearer's proof of their result.

Let H be the harmonic mean of D, i.e., H = n/R and A the average of D. Then f >= n/A follows from the inequality of arithmetic-harmonic means which says that A >= H.

f >= R

f/n >= R/n = 1/H >= 1/A i.e, f >= n/A

Siemion"

2nd run on Lower bounds on the forest number of simple connected graphs, f(G).

Note: Clearly b(G) ≥ f(G) ≥ tree(G) ≥ path(G), and note that this (for the second run) time b(G), tree(G) and path(G) were available to the program when lower bounds for f(G) were generated; Also for the second run for forest should reflect the counterexamples listed above and now also includes the local independence invariants and the domination number.
conjectures 39, 42, 47

E 57. If G is a simple connected graph, then f(G) ≥ tree(G) definitions

Mar 25, 2004.

T 67. If G is a simple connected graph, then f(G) ≥ diam(G) + maximum of l(v) -2 definitions reference

Mar 25, 2004. This is related to the discussion of conjecture 16.
Mar 27, 2004. DeLaVina and Waller.

Lower bounds on the tree number of simple connected graphs, tree(G).

Note: Clearly b(G) ≥ f(G) ≥ tree(G) ≥ path(G).

E 68. If G is a simple connected graph, then tree(G) ≥ path(G) definitions

Apr 04, 2004.

Upper bounds on the bipartite number of simple connected graphs, b(G).

E 86. If G is a simple connected graph, then b(G) ≤ 2 + n - w(G) definitions

April 10, 2004.

E 89. If G is a simple connected graph, then b(G) ≤ 2a(G) definitions

April 10, 2004.

Upper bounds on the independence number of simple connected graphs, a(G).

R 92. If G is a simple connected graph, then a(G) ≤ FLOOR[( n + p)/2] definitions reference

April 21, 2004. This is equivalent to conjecture #11 which as described in the reference I knew was correct for all simple graphs.

E 93. If G is a simple connected graph, then a(G) ≤ f(G) -1 definitions

April 21, 2004.

T 94. If G is a simple connected graph, then a(G) ≤ CEIL[b(G) - SQRT[circumference(G)]] definitions

April 21, 2004. July 2005, for large enough circumference(G), the conjecture follows from the proposition below.
Proposition. If G is a simple connected graph, then b(G) ≥ a(G) + FLOOR(circumference(G)/4).

Proof. Note circumference(G) => 3. Let C be the set of vertices of a largest induced cycle. Let I be the set of vertices of a maximum independent set. Color the vertices of I with color green. Since the intersection of C and I is at most FLOOR(circumference(G)/2), there are at least FLOOR(circumference(G)/4) vertices of C that can be colored red. Hence, G has an induced bipartite subgraph on at least a(G) + FLOOR(circumference(G)/4) vertices.
October 12, 2006. Benny John.

T 97. If G is a simple connected graph, then a(G) ≤ maximum of l(v) - d(G) definitions

April 21, 2004. Fajtlowicz April 2004

E 99. If G is a simple connected graph, then a(G) ≤ b(G) -minimum of l(v) definitions

April 21, 2004. DeLaVina April 2004

T 101. If G is a simple connected graph, then a(G) ≤ FLOOR[(n + alphacore(G))/2] definitions

April 21, 2004. March 14, 2008. This follows from a(G) ≤ [matching(G) + alphacore(G)]/2 a result with R. Pepper.

T 102. If G is a simple connected graph, then a(G) ≤ CEIL[b(G) - SQRT[diam(G)]] definitions

April 21, 2004. July 2005, for large enough diameter this follows from the proposition listed below conjecture 17.
October 12, 2006. Benny John.

E 106. If G is a simple connected graph, then a(G) ≤ n - domination(G)] definitions

April 21, 2004.

Lower bounds on the matching number of connected bipartite graphs, m(G).

note: Graffiti.pc was asked to focus on lower bounds for the matching number, which are sharp for some connected bipartite graphs and thus some conjectures were made for all graphs (see 113 & 127)

E 112. If G is a connect bipartite graph, then m(G) ≥ CEILING[freq(D(G))/2] definitions reference

June, 2004. DeLaVina and Gramajo June 2004.

T 113. If G is a simple connected graph, then m(G) ≥ CEILING[dd(G)/2] definitions reference

June, 2004. DeLaVina and Gramajo (June 2004) proved this for connected bipartite graphs.
Jan 2005. Craig Larson proved this for all simple graphs with no isolated vertices.

E 114. If G is a connect bipartite graph, then m(G) ≥ minimum { mode_max(G), frequency of mode} definitions reference

June, 2004. DeLaVina and Gramajo July 2004. In light of this and conjectures #115 and #116, we proved the more general statement m(G) ≥ minimum {d(S), |S|}

E 115. If G is a connect bipartite graph, then m(G) ≥ minimum {D(G), freq(D(G))} definitions reference

June, 2004. DeLaVina and Gramajo July 2004. See #114.

E 116. If G is a connect bipartite graph, then m(G) ≥ minimum { min degree of center vertices, number of center vertices} definitions reference

June, 2004. DeLaVina and Gramajo July 2004. See #114.

E 118 If G is a connect bipartite graph, then m(G) ≥ s(G) definitions reference

June, 2004. DeLaVina and Gramajo June 2004. Follows from the general statement given in #114.

T 119 If G is a connect X,Y bigraph such that |X| £ |Y|, then m(G) ≥ minimum{2s(G), |X|} definitions reference

June, 2004. DeLaVina and Gramajo June 2004.

R 120 If G is a bipartite graph, then m(G) ≥ |E(G)|/D(G). definitions reference

June, 2004.

T 121 Let G be a connected X,Y bigraph such that |X| £ |Y|, and let A be the set of vertices of minimum degree. Then m(G) ≥ |N(A)-A|/d(G). definitions reference

June 2004. DeLaVina and Gramajo September 2004.

T 122 If G is a connected bipartite graph, then m(G) ≥ rad(G). definitions reference

June 2004. Gramajo June 2004.

T 122a If G is a connected bipartite graph, then m(G) ≥ 0.5diam(G) + d(G) - 1 . definitions reference

June, 2004. DeLaVina and Gramajo June 2004. The numbering of conjectures was in err at this point.

T 124 If G is a connected X,Y bigraph such that |X| £ |Y|, then m(G) ≥ minimum{CEILING[1 + median of degrees], |X|} definitions

December 2004. I. Gramajo, Feb 2005.

T 125 If G is a connected X,Y bigraph such that |X| £ |Y|, then m(G) ≥ minimum{1 + k, |X|}, where k is the (n-|X|-1)th degree of the ordered degree sequence. definitions

December 2004. I. Gramajo, Feb 2005.

T 127 If G is a simple connected graph, then m(G) ≥ minimum{1 + ecc(centers), minimum of dist_even(G)} definitions

December 2004. I. Gramajo, Mar 2005.

Lower bounds on the path number of simple connected graphs, path(G). #'s 31, 31a, and 35 were repeated from 1st run for path.

E 131. If G is a simple connected graph, then path(G) ≥ circumference - 1 definitions

July 12, 2005.

T 135. If G is a simple connected graph, then path(G) ≥ girth/d(G) definitions

July 12, 2005. B. Waller

2nd run for Lower bounds on the tree number of simple connected graphs, tree(G). See 68-85 for 1st run. Note: the program repeated some conjectures, but I do not repeat them here.

Note: Clearly b(G) ≥ f(G) ≥ tree(G) ≥ path(G).

E 140. If G is a simple connected graph, then tree(G) ≥ 1 + maximum of l(v) definitions

July 19, 2005.

E 147. If G is a simple connected graph, then tree(G) ≥ n(G)*t(G) definitions

July 19, 2005.

Next List

2nd Run for Lower bounds for maximum number of leaves over all spanning trees, L_s(G)
note: conjecture 5 was repeated from the first run for L.

E 152. If G is a simple connected graph, then L_s(G) ≥ maximum of {N(e): e an edge of G} - 2. definitions

Aug 8, 2005.

E 153. If G is a simple connected graph, then L_s(G) ≥ D(G). definitions

Aug 8, 2005.

E 158. If G is a simple connected graph, then L_s(G) ≥ maximum of l(v) + 1 - c_K3(G). definitions

Aug 8, 2005. It is easily proven that L_s(G) ≥ maximum of l(v) and if the graph has a triangle it is also easily proven that L_s(G) ≥ maximum of l(v) can be improved by one.

E 159. If G is a simple connected graph, then L_s(G) ≥ maximum of l(v) + 0.5*w(G) - 1. definitions

Aug 8, 2005. Oct. 2005, if G is not K₁, the the stronger bound of L_s(G) ≥ maximum of l(v) + w(G) - 2 is easily argued. If there is a vertex of a maximum clique that realizes the maximum of local independence, then one can begin to build a spanning tree from that vertex with maximum of l(v) + w(G) - 2 leaves and then extend the spanning tree. If no vertex of a maximum clique is a vertex that realizes the maximum of local independence, then one can begin to build a spanning tree rooted at a vertex of maximum local independence with at least maximum of l(v) leaves. At most one of its independent neighbors will be in any one maximum clique; in any case, add the edges and vertices of a shortest path from the root to a maximum clique, and extend the tree to include w(G) - 1 vertices of the clique as leaves of the extended spanning tree. Since at most one independent neighbor is on the maximum clique, this initial spanning tree will contain at least maximum of l(v) + w(G) - 2 leaves.

E
163. If G is a simple connected graph, then L_s(G) ≥ CEIL[0.5*D(G²)]. definitions

Aug 8, 2005. Oct 10, 2005.

E 164. If G is a simple connected graph, then L_s(G) ≥ D(G²) - D(G). definitions

Aug 8, 2005. Oct 10, 2005.

Next List

Lower bounds for L_s(G) + b(G)

T 173. If G is a simple connected graph on at least 2 vertices, then L_s(G) + b(G) ≥ n + 1 + c_bipartite(G). definitions reference

Aug 8, 2005. Note that since 2a(G) ≥ b(G) , G.pc's 173 is an improvement over Grigg's Conjecture L_s(G) ≥ n - 2a(G) + 1, which inspired the first run of lower bounds (listed on wowII) on L_s(G). DeLaVina and Waller proved that if G is a simple connected graph on at least 2 vertices, then L_s(G) + b(G) ≥ n + 1. see reference. Note that in the case that the graph is bipartite, the relation is obvious since b(G) = n and L_s(G) ≥ 2.
Note: Since n - L_s(G) is the connected domination number, g_c of a graph, this relation provides an upper bound on the connected domination number b(G) ≥ g_c+ 1 + c_bipartite(G). Since a largest induced bipartite subgraph B has the property that every vertex not among the vertices of B is adjacent to 2 vertices of B of different colors, the vertices of B determine a special variety of 2-dominating set, and so b(G) ≥ g₂ but I know of no relation between connected domination and 2-domination.

T 175. If G is a simple connected graph on at least 2 vertices, then L_s(G) + b(G) ≥ n + D(G)*c_bipartite(G). definitions

Aug 8, 2005. In the case that G is a bipartite graph, the relation follows since b(G) = n and L_s(G) ≥ D(G); otherwise, the relation follows from L_s(G) + b(G) ≥ n + 1, see wowII 173.

Sophie Heuristic

Sufficient conditions on a simple graph G for the existence of a Hamiltonian path (also known as Traceable graph)

Note: the following conjectures were generated by a new heuristic for G.pc named Sophie. The program was queried for sufficient conditions for simple connected graphs on at least two vertices.

T 188. If G is a simple connected graph with n > 1 such that annihilation number ≤ 1 + σ(G), then G has a Hamiltonian path. definitions

Jan 12, 2006. April 2008, Landon Jennings

T 192. If G is a simple connected graph with n > 1 such that
Σ(G) ≤ upper median of degree sequence of G,

then G has a Hamiltonian path.
definitions

Jan 12, 2006. Note one can rewrite the hypothesis of this conjecture as n - σ(G) - 1 ≤ upper median of degree sequence of G], where σ(G) is the 2nd smallest of the degree sequence of G. The following theorem is an analogue to Chvatal's condition for hamiltonian cycle (see D. West's Intro. to Graph Theory.) from which below it is proven that the conjecture follows.
Theorem (Chvatal's). Let G be a simple graph with degree sequence d₁≤ d₂≤ ...≤ d_n with n at least 3. If for i < (n+1)/2 we have that d_i ≥ i or d_n+1-i ≥ n-i. , then G has a Hamiltonian path.

Lemma. If n is at least 2, then [n - σ(G) - 1 ≤ upper median of degree sequence of G] implies Chvatal's condition.

Proof. Assume that n is at least 2 and n - σ(G) - 1 ≤ upper median of degree sequence of G . Observe that our assumption implies

d_(n+2)/2 ≥ upper median of degree sequence of G ≥ n - σ(G) - 1.

If i = 1, then since the graph is connected the Chvatal's condition clearly holds. So suppose 2 ≤ i < (n+1)/2. Then clearly σ(G) ≤ d_i. Now, if d_i < i, then i ≥ σ(G) + 1, which is equivalent to

n -1- σ(G) ≥ n - i.

Since i < (n+1)/2, it follows that n +1 - i ≥ (n+3)/2. Thus, d_n+1-i ≥ d_(n+3)/2 ≥ d_(n+2)/2≥ n - σ(G) - 1 ≥ n - i.                   QED

R 195. If G is a simple connected graph with n > 1 such that a(G) - 1 ≤   κ(G) , then G has a Hamiltonian path.    definitions

Jan 12, 2006. This is a Theorem of Chvatal & Erdos.

T 196. If G is a simple connected graph with n > 1 such that b(G)/2 = radius(G), then G has a Hamiltonian path.    definitions

Jan 12, 2006. Jan. 2008 DPW.

T 196a. If G is a simple connected graph with n > 1 such that a(G) = radius(G), then G has a Hamiltonian path.    definitions reference

Jan 12, 2006. Note that this conjecture was superseded by Sophie's #196, but since Pepper and Waller were aware of it and began working on it, I've included it on the list.

T 197. If G is a simple connected graph with n > 1 such that girth(G) ≥ 2^a^{(G)
- 1}, then G has a Hamiltonian path.    definitions

Jan 12, 2006. Note that this conjecture was superseded by later conjectures, but since Pepper and Waller proved it, it is included on the list.

T 206. If G is a simple connected graph with n > 1 such that Σ(G) ≤ 1 + 0.5*mode_max(G), then G has a Hamiltonian path. definitions

Jan 12, 2006. April 2008, Landon Jennings proved that this condition follows from Chvatal's sufficient condition for Hamiltonian paths.

T 215. If G is a simple connected graph with n > 1 such that (1/2)*domination(G) ≤ c_claw(G), then G has a Hamiltonian path.    definitions

Jan 12, 2006. Mar. 9, 2006. DeLaVina, John & Pepper.

Dalmatian Heuristic

Lower bounds for Total Domination g_t

R 226. If G is a simple connected graph, then g_t(G) ≥ g(G))
definitions

Feb. 23, 2007.

T 228. If G is a simple connected triangle-free graph, then g_t(G) ≥ c(G)
definitions reference

Feb. 23, 2007. Mar. 30, 2007. Stephen Hartke, Qi Liu, Doug West and Hehui Wu.

R 229. If G is a simple connected graph, then g_t(G) ≥ n(G)/D(G)
definitions

Feb. 23, 2007.

T 230. If G is a simple connected graph, then g_t(G) ≥ 2 * (CEIL[0.5*radius(G)])
definitions reference

Feb. 23, 2007. B. Waller & R. Pepper.

T 231. If G is a simple connected graph, then g_t(G) ≥ 1 + ecc(Centers)
definitions reference

Feb. 23, 2007.

T 249. If G is a simple connected graph, then g_t(G) ≥ CEIL[girth(G)/2]
definitions reference

Feb. 23, 2007. April 19, 2007: B. Waller & R. Pepper.

E 263. If G is a simple connected graph on an odd number of vertices such that D(G) ≤ n(G)/2, then g_t(G) ≥ 3.
definitions

Feb. 23, 2007.

Sophie Heuristic

Sufficient conditions on a simple connected graph G for Total Domination equal to Radius

Note: the following conjectures were generated by a new heuristic for G.pc named Sophie. The program was queried for sufficient conditions for simple connected graphs on at least two vertices.

T 277. Let G is a simple connected graph with n > 1. minimum {|E_G(D)|: D is a minimum total dominating set} =0.5*radius(G) if and only if g_t(G)=radius(G). definitions reference

Feb 25, 2007. Since radius was proven to be a lower bound for total domination (see 230), Sophie was queried for sufficient condition for the case of equality and subsequently reported the above equivalence. It is easily proven that if minimum {|E_G(D)|: D is a minimum total dominating set} =0.5*radius(G), then g_t(G)=radius(G).
May 4, 2007: B. Waller proved the converse.


		Lower bounds for maximum number of leaves over all spanning trees, L_s(G)

T	1.	If G is a simple connected graph, then L_s(G) ≥ n + 1 - 2m(G)	definitions reference
		1996. In 1984, Hedetniemi and Laskar [HL] proved that for simple connected graphs L_s(G) ≥ n - 2m(G). In 1996, Fajtlowicz proved that for connected graphs on at least two vertices L_s(G) ≥ n + 1 - 2m(G) and later send the following. Dec 12, 2004 Fajtlowicz. Let T be a spanning tree containing a maximum matching. Then Graffiti's conjecture follows (for graphs with at least one edge) from the Lemma. Let T be a n-vertex tree with L endpoints and n > 1. If T has a matching with m edges then L > n - 2m. Proof: We can assume that n > 3. Suppose T has two leaves adjacent to a vertex u of degree > 2. Let T' be the tree obtained from T by deletion of one of these leaves, and let n', L' and m' be the corresponding invariants of T'. Since n' > 1, by induction on n we have that L' > n' - 2m'. Because deg(u) > 2, it follows that L' = L-1, and m' = m. Thus L - 1 > n - 1 - 2m' , i.e., L > n - 2m. Suppose now that T has a leaf adjacent to a vertex of degree 2 and let T' be the tree obtained from T by deleting this leaf and its unique neighbor u. Clearly m'= m-1 in this case and L' = L if the degree of the other neighbor of u is 2 and L-1 otherwise. In either of these two cases we have L >= L' > n' - 2m' >= n - 2 - 2 (m-1) = n - 2m and the theorem again follows by induction on n, because n' > 1.

T	3.	If G is a simple connected graph, then L_s(G)≥ g_i(G) maximum temp(v)*	definitions
		1996. Mar. 17, 2004: Ryan Pepper " Here, MID is the number of vertices in a minimum independent dominating set. Take any vertex v of max degree D from graph G with n vertices and remove all vertices adjacent to v leaving G'. Now, any independent dominating set of G' must include v and so is also an independent dominating set of G. But there are at most n-D vertices in any independent dominating set of G'. Therefore, MID <= n-D, since MID is cardinality of a minimum independent dominating set. The rest of proof is as even more of an exercise than this and goes as follows. For any graph, max(temp) <= D/(n-D), D is max degree. So, MID(max(temperature)) <= (n-D)D/(n-D) = D <= Max number of leaves of spanning tree. The last inequality because, starting from a vertex x of maximum degree, we can build a spanning tree by including first all vertices of distance one from x, then all vertices of distance two from x, etc .... This will give spanning tree with a vertex of maximum degree D, and every tree has at least as many leaves as its maximum degree."

T	4.	If G is a simple connected graph, then L_s(G) ≥ minimum of \|N_G(e)\| - 1	definitions reference
		1996. DeLaVina 1996

T	5.	If G is a simple connected graph, then L_s(G) ≥ maximum{\| S(v, rad(G)) \|: v is a center of G}	definitions reference
		1996. DeLaVina and Fajtlowicz 1996

T	7.	If G is a simple connected graph, then L_s(G) ≥ maximum of l(v) -1 + n - 2a(G)	definitions reference
		1996. DeLaVina, Fajtlowicz, Waller (2002)


		*Lower bounds for the path covering number of trees, p(T).*

E	9.	If T is a tree, then p(T) ≥ D(T) -1	definitions reference
		2001

E	10.	If T is a tree, then p(T) ≥ CEIL(L(T)/2)	definitions reference
		2001

E	11.	If T is a tree, then p(T) ≥ 2a(T) - n	definitions reference
		2001

E	12.	If T is a tree, then 2a(T) - n ≥ maximum of dist_even(v) - minimum of dist_even(v)	definitions reference
		2001


		*Lower bounds on the bipartite number of simple connected graphs, b(G).*

T	13.	If G is a simple connected graph, then b(G) ≥ diam(G) + maximum of l(v) -1	definitions reference
		July 3, 2003. DeLaVina and Waller 2004.

T	14.	If G is a simple connected graph, then b(G) ≥ diam(G) + f_G(1) -1	definitions reference
		July 3, 2003. DeLaVina and Waller 2003

R	15.	If G is a simple connected graph, then b(G) ≥ 2rad(G)	definitions reference
		July 3, 2003. This was proven by Fajtlowicz, 1988. Waller sent an alternate proof 2003.

T	16.	If G is a simple connected graph, then b(G) ≥ 2(rad(G)-1) + maximum of l(v)	definitions reference
		July 3, 2003. July 26, 2003 Bill Waller shows, by proof similar to Favaron's for a(G) ≥ rad(G), that b(G) ≥ 2rad(G) + maximum of l(v) - 5. Mar. 17, 2004: Ryan Pepper communicated that he could prove f(G) ≥ diam(G) + maximum of l(v) - 3. Note: A second run of the program was conducted for forest number (see conjectures 57-67.) Mar. 25, 2004: In a second run for forest the program conjectured f(G) ≥ diam(G) + maximum of l(v) - 2. It is conjecture 67. Nov. 25, 2006 The conjectured relation follows for a tree T since diam(T) ≥ 2rad(T) -1 and by wowII #13 it follows that b(T) ≥ diam(T) + maximum of l(v) -1. Jan. 2008: DRW

T	17.	If G is a simple connected graph, then b(G) ≥ a(G) + CEIL(diam(G)/3)	definitions
		July 3, 2003. Independently proven by Benny John, UHD (Dec. 2005) and David Schindl,Gerard Univ (Jan. 2006).

T	18.	If G is a simple connected graph, then b(G) ≥ a(G) + CEIL(sqrt(dist_max(M)))	definitions
		July 3, 2003. July 2005, for large enough diameter this follows from conjecture #17. Feb. 21, 2006 Benny John generalized Schindl's proof of 17 to prove #18..

T*	20.	If G is a simple connected graph, then b(G) ≥ n/FLOOR[deg_avg(G)]	definitions reference
		July 3, 2003. Mar 06, 2004, Bill Waller observes that for graphs that are p-regular and K_p-free, f(G) ≥ n/FLOOR[deg_avg(G)] (see conjecture #50 below) follows from Fajtlowicz's result on the independence ratio that for graphs with max. degree at most p and K_q-free, a(G)/n ≥ 2/(p+q). Mar. 07, 2004, Fajtlowicz sent a proof of f(G) ≥ n/deg_avg(G), see conjecture #50.

T	27.	If G is a simple connected graph, then b(G) ≥ (minimum of \|N(e)\|)^1-t(G)	definitions
		July 3, 2003. ** Mar. 17 2004: thanks to Ryan Pepper for alerting me to a typo in this statement. Mar. 19, 2004: Pepper sent a proof of a bound on b in terms of the degree of an edge which is stronger for triangle-free graphs, and notes that for t(G) ≥ 1, 1 ≥ (minimum of \|N(e)\|)^1-t(G).

T	29.	If G is a simple connected graph, then b(G) ≥ dist_max(A)+ 1/(n mod D(G))	definitions
		July 3, 2003. The expression on the right is undefined for some graphs. The conjecture is made for those graphs for which is is defined. June 2005, this follows from b(G) ≥ diam(G)+ 1.

		*Lower bounds on the path number of simple connected graphs, path(G).*

R	31.	If G is a simple connected graph, then path(G) ≥ 2rad(G) - 1	definitions reference
		July 15, 2003. This is Chung's Lemma, see reference.

R	31a.	If G is a simple connected graph, then path(G) ≥ 2ecc(Centers) + 1	definitions reference
		Summer 2003. This is offers an improvement over Chung's Theorem see wowII #31, when rad(G) = ecc(centers). June 2005, Waller noticed that conjecture follows from a Theorem of Basco and Tuza (see reference).

R	35.	If G is a simple connected graph, then path(G) ≥ 1 + diam(G)	definitions reference
		July 15, 2003. This could also have been labeled an exercise, but since it was noted in the cited reference we include it here as a rediscovery.


		*Lower bounds on the forest number of simple connected graphs, f(G).*
	Note:	Clearly b(G) ≥ f(G) ≥ path(G), and note that f(G) and path(G) were not available to the program when lower bounds for b(G) were generated.
E	37.	If G is a simple connected graph, then f(G) ≥ path(G)	definitions
		Mar 05, 2004.

R	47.	If G is a simple connected graph, then f(G) ≥ diam(G) + f_G(1) -1	definitions reference
		Mar 05, 2004. This is a rediscovery since Waller and I knew it to be true from our work on b(G). DeLaVina and Waller 2003, see #14 above.

T	48.	If G is a simple connected graph, then f(G) ≥ girth(G) + f_G(1) -1	definitions reference
		Mar 05, 2004. The proof is similar to that of #47. DeLaVina and Waller 2004. *must check algorithm for circumference.

T*	50.	If G is a simple connected graph, then f(G) ≥ n/FLOOR[deg_avg(G)]	definitions reference
		Mar 05, 2004. Note conj. #20 of wowII is b(G) ≥ n/FLOOR[deg_avg(G)]. Mar 06, 2004, Bill Waller observes that for graphs that are p-regular and K_p-free, f(G) ≥ n/FLOOR[deg_avg(G)] follows from Fajtlowicz's result on the independence ratio that for graphs with max. degree at most p and K_q-free, a(G)/n ≥ 2/(p+q).[F] Mar 07, 2004, DeLaVina: I came across a paper [BB] (see reference link) by Bau and Beineke on n(G) - f(G), which they called the decycling number of a graph. In their paper they cite a result of Zheng and Lu in [ZL] that for cubic graphs without triangles and n not 8, f => n - ceil[n/3] (settling a conjecture by Bondy, Hopkins and Staton [BHS].) Zheng and Lu's bound for cubic triangle-free graphs is an improvement over the above. Bau and Beineke also cite other results on the decycling number, they write "A sharp upper bound for the decycling number of cubic graphs has been obtained in [LZ] by Liu and Zhao and that for connected graphs with maximum degree 3 has been obtained in [AMT]." Mar. 07, 2004, Fajtlowicz sent a proof of f(G) ≥ n/deg_avg(G) "The algorithm is as the proof which essentially shows how to find a forest of size n/A, where A is the average degree. Proof: We can assume that G has no isolated points. Let's order vertices at random and starting with empty set F, let us keep adding to F a vertex v, if F + {v} is an induced forest. We add suitable vertices to F in order they are listed. Let d be the degree of v. The probability that v will eventually land in F is at least 2/(d+1), because that's the probability that v is the first or the second on the list of v +{neighbors of v}. Adding such vertices keeps F acyclic. Let f(v) = 1 if v is in F and zero otherwise. By linearity, The expected value of f is at least R = sum 1/d, where the summation is over the degree sequence D, because for d >= 1, 2/(d+1) >= 1/d. Since that is the expected value then there is at least one ordering for which \|F\| is at least R. This is a version of Caro-Wei bound for forests rather than the independence number and the idea of the proof is the same as Shearer's proof of their result. Let H be the harmonic mean of D, i.e., H = n/R and A the average of D. Then f >= n/A follows from the inequality of arithmetic-harmonic means which says that A >= H. f >= R f/n >= R/n = 1/H >= 1/A i.e, f >= n/A Siemion"


		*2nd run on Lower bounds on the forest number of simple connected graphs, f(G).*
	Note:	Clearly b(G) ≥ f(G) ≥ tree(G) ≥ path(G), and note that this (for the second run) time b(G), tree(G) and path(G) were available to the program when lower bounds for f(G) were generated; Also for the second run for forest should reflect the counterexamples listed above and now also includes the local independence invariants and the domination number. conjectures 39, 42, 47
E	57.	If G is a simple connected graph, then f(G) ≥ tree(G)	definitions
		Mar 25, 2004.

T	67.	If G is a simple connected graph, then f(G) ≥ diam(G) + maximum of l(v) -2	definitions reference
		Mar 25, 2004. This is related to the discussion of conjecture 16. Mar 27, 2004. DeLaVina and Waller.


		*Lower bounds on the tree number of simple connected graphs, tree(G).*
	Note:	Clearly b(G) ≥ f(G) ≥ tree(G) ≥ path(G).

E	68.	If G is a simple connected graph, then tree(G) ≥ path(G)	definitions
		Apr 04, 2004.


		Upper *bounds on the bipartite number of simple connected graphs, b(G).*

E	86.	If G is a simple connected graph, then b(G) ≤ 2 + n - w(G)	definitions
		April 10, 2004.

E	89.	If G is a simple connected graph, then b(G) ≤ 2a(G)	definitions
		April 10, 2004.


		Upper bounds on the independence number of simple connected graphs, a(G).

R	92.	If G is a simple connected graph, then a(G) ≤ FLOOR[( n + p)/2]	definitions reference
		April 21, 2004. This is equivalent to conjecture #11 which as described in the reference I knew was correct for all simple graphs.

E	93.	If G is a simple connected graph, then a(G) ≤ f(G) -1	definitions
		April 21, 2004.

T	94.	If G is a simple connected graph, then a(G) ≤ CEIL[b(G) - SQRT[circumference(G)]]	definitions
		April 21, 2004. July 2005, for large enough circumference(G), the conjecture follows from the proposition below. Proposition. If G is a simple connected graph, then b(G) ≥ a(G) + FLOOR(circumference(G)/4). Proof. Note circumference(G) => 3. Let C be the set of vertices of a largest induced cycle. Let I be the set of vertices of a maximum independent set. Color the vertices of I with color green. Since the intersection of C and I is at most FLOOR(circumference(G)/2), there are at least FLOOR(circumference(G)/4) vertices of C that can be colored red. Hence, G has an induced bipartite subgraph on at least a(G) + FLOOR(circumference(G)/4) vertices. October 12, 2006. Benny John.

T	97.	If G is a simple connected graph, then a(G) ≤ maximum of l(v) - d(G)	definitions
		April 21, 2004. Fajtlowicz April 2004

E	99.	If G is a simple connected graph, then a(G) ≤ b(G) -minimum of l(v)	definitions
		April 21, 2004. DeLaVina April 2004

T	101.	If G is a simple connected graph, then a(G) ≤ FLOOR[(n + alphacore(G))/2]	definitions
		April 21, 2004. March 14, 2008. This follows from a(G) ≤ [matching(G) + alphacore(G)]/2 a result with R. Pepper.

T	102.	If G is a simple connected graph, then a(G) ≤ CEIL[b(G) - SQRT[diam(G)]]	definitions
		April 21, 2004. July 2005, for large enough diameter this follows from the proposition listed below conjecture 17. October 12, 2006. Benny John.

E	106.	If G is a simple connected graph, then a(G) ≤ n - domination(G)]	definitions
		April 21, 2004.


		Lower bounds on the matching number of connected bipartite graphs, m(G).
		note: Graffiti.pc was asked to focus on lower bounds for the matching number, which are sharp for some connected bipartite graphs and thus some conjectures were made for all graphs (see 113 & 127)
E	112.	If G is a connect bipartite graph, then m(G) ≥ CEILING[freq(D(G))/2]	definitions reference
		June, 2004. DeLaVina and Gramajo June 2004.

T	113.	If G is a simple connected graph, then m(G) ≥ CEILING[dd(G)/2]	definitions reference
		June, 2004. DeLaVina and Gramajo (June 2004) proved this for connected bipartite graphs. Jan 2005. Craig Larson proved this for all simple graphs with no isolated vertices.

E	114.	If G is a connect bipartite graph, then m(G) ≥ minimum { mode_max(G), frequency of mode}	definitions reference
		June, 2004. DeLaVina and Gramajo July 2004. In light of this and conjectures #115 and #116, we proved the more general statement m(G) ≥ minimum {d(S), \|S\|}

E	115.	If G is a connect bipartite graph, then m(G) ≥ minimum {D(G), freq(D(G))}	definitions reference
		June, 2004. DeLaVina and Gramajo July 2004. See #114.

E	116.	If G is a connect bipartite graph, then m(G) ≥ minimum { min degree of center vertices, number of center vertices}	definitions reference
		June, 2004. DeLaVina and Gramajo July 2004. See #114.

E	118	If G is a connect bipartite graph, then m(G) ≥ s(G)	definitions reference
		June, 2004. DeLaVina and Gramajo June 2004. Follows from the general statement given in #114.

T	119	If G is a connect X,Y bigraph such that \|X\| £ \|Y\|, then m(G) ≥ minimum{2s(G), \|X\|}	definitions reference
		June, 2004. DeLaVina and Gramajo June 2004.

R	120	If G is a bipartite graph, then m(G) ≥ \|E(G)\|/D(G).	definitions reference
		June, 2004.

T	121	Let G be a connected X,Y bigraph such that \|X\| £ \|Y\|, and let A be the set of vertices of minimum degree. Then m(G) ≥ \|N(A)-A\|/d(G).	definitions reference
		June 2004. DeLaVina and Gramajo September 2004.

T	122	If G is a connected bipartite graph, then m(G) ≥ rad(G).	definitions reference
		June 2004. Gramajo June 2004.

T	122a	If G is a connected bipartite graph, then m(G) ≥ 0.5diam(G) + d(G) - 1 .	definitions reference
		June, 2004. DeLaVina and Gramajo June 2004. The numbering of conjectures was in err at this point.

T	124	If G is a connected X,Y bigraph such that \|X\| £ \|Y\|, then m(G) ≥ minimum{CEILING[1 + median of degrees], \|X\|}	definitions
		December 2004. I. Gramajo, Feb 2005.

T	125	If G is a connected X,Y bigraph such that \|X\| £ \|Y\|, then m(G) ≥ minimum{1 + k, \|X\|}, where k is the (n-\|X\|-1)th degree of the ordered degree sequence.	definitions
		December 2004. I. Gramajo, Feb 2005.

T	127	If G is a simple connected graph, then m(G) ≥ minimum{1 + ecc(centers), minimum of dist_even(G)}	definitions
		December 2004. I. Gramajo, Mar 2005.


		*Lower bounds on the path number of simple connected graphs, path(G).* #'s 31, 31a, and 35 were repeated from 1st run for path.
E	131.	If G is a simple connected graph, then path(G) ≥ circumference - 1	definitions
		July 12, 2005.

T	135.	If G is a simple connected graph, then path(G) ≥ girth/d(G)	definitions
		July 12, 2005. B. Waller


		*2nd run for Lower bounds on the tree number of simple connected graphs, tree(G). See 68-85 for 1st run.* Note: the program repeated some conjectures, but I do not repeat them here.
	Note:	Clearly b(G) ≥ f(G) ≥ tree(G) ≥ path(G).

E	140.	If G is a simple connected graph, then tree(G) ≥ 1 + maximum of l(v)	definitions
		July 19, 2005.

E	147.	If G is a simple connected graph, then tree(G) ≥ n(G)t(G)*	definitions
		July 19, 2005.

			Next List
		2nd Run for Lower bounds for maximum number of leaves over all spanning trees, L_s(G) note: conjecture 5 was repeated from the first run for L.

E	152.	If G is a simple connected graph, then L_s(G) ≥ maximum of {N(e): e an edge of G} - 2.	definitions
		Aug 8, 2005.

E	153.	If G is a simple connected graph, then L_s(G) ≥ D(G).	definitions
		Aug 8, 2005.

E	158.	If G is a simple connected graph, then L_s(G) ≥ maximum of l(v) + 1 - c_K3(G).	definitions
		Aug 8, 2005. It is easily proven that L_s(G) ≥ maximum of l(v) and if the graph has a triangle it is also easily proven that L_s(G) ≥ maximum of l(v) can be improved by one.

E	159.	If G is a simple connected graph, then L_s(G) ≥ maximum of l(v) + 0.5w(G) - 1.*	definitions
		Aug 8, 2005. Oct. 2005, if G is not K₁, the the stronger bound of L_s(G) ≥ maximum of l(v) + w(G) - 2 is easily argued. If there is a vertex of a maximum clique that realizes the maximum of local independence, then one can begin to build a spanning tree from that vertex with maximum of l(v) + w(G) - 2 leaves and then extend the spanning tree. If no vertex of a maximum clique is a vertex that realizes the maximum of local independence, then one can begin to build a spanning tree rooted at a vertex of maximum local independence with at least maximum of l(v) leaves. At most one of its independent neighbors will be in any one maximum clique; in any case, add the edges and vertices of a shortest path from the root to a maximum clique, and extend the tree to include w(G) - 1 vertices of the clique as leaves of the extended spanning tree. Since at most one independent neighbor is on the maximum clique, this initial spanning tree will contain at least maximum of l(v) + w(G) - 2 leaves.


E	163.	If G is a simple connected graph, then L_s(G) ≥ CEIL[0.5D(G²)].*	definitions
		Aug 8, 2005. Oct 10, 2005.

E	164.	If G is a simple connected graph, then L_s(G) ≥ D(G²) - D(G).	definitions
		Aug 8, 2005. Oct 10, 2005.
			Next List
		Lower bounds for L_s(G) + b(G)

T	173.	If G is a simple connected graph on at least 2 vertices, then L_s(G) + b(G) ≥ n + 1 + c_bipartite(G).	definitions reference
		Aug 8, 2005. Note that since 2a(G) ≥ b(G) , G.pc's 173 is an improvement over Grigg's Conjecture L_s(G) ≥ n - 2a(G) + 1, which inspired the first run of lower bounds (listed on wowII) on L_s(G). DeLaVina and Waller proved that if G is a simple connected graph on at least 2 vertices, then L_s(G) + b(G) ≥ n + 1. see reference. Note that in the case that the graph is bipartite, the relation is obvious since b(G) = n and L_s(G) ≥ 2. Note: Since n - L_s(G) is the connected domination number, g_c of a graph, this relation provides an upper bound on the connected domination number b(G) ≥ g_c+ 1 + c_bipartite(G). Since a largest induced bipartite subgraph B has the property that every vertex not among the vertices of B is adjacent to 2 vertices of B of different colors, the vertices of B determine a special variety of 2-dominating set, and so b(G) ≥ g₂ but I know of no relation between connected domination and 2-domination.

T	175.	If G is a simple connected graph on at least 2 vertices, then L_s(G) + b(G) ≥ n + D(G)c_bipartite(G).*	definitions
		Aug 8, 2005. In the case that G is a bipartite graph, the relation follows since b(G) = n and L_s(G) ≥ D(G); otherwise, the relation follows from L_s(G) + b(G) ≥ n + 1, see wowII 173.

		Sophie Heuristic
		Sufficient conditions on a simple graph G for the existence of a Hamiltonian path (also known as Traceable graph)
		Note: the following conjectures were generated by a new heuristic for G.pc named Sophie. The program was queried for sufficient conditions for simple connected graphs on at least two vertices.
T	188.	If G is a simple connected graph with n > 1 such that annihilation number ≤ 1 + σ(G), then G has a Hamiltonian path.	definitions
		Jan 12, 2006. April 2008, Landon Jennings

T	192.	If G is a simple connected graph with n > 1 such that Σ(G) ≤ upper median of degree sequence of G, then G has a Hamiltonian path.	definitions
		Jan 12, 2006. Note one can rewrite the hypothesis of this conjecture as n - σ(G) - 1 ≤ upper median of degree sequence of G], where σ(G) is the 2nd smallest of the degree sequence of G. The following theorem is an analogue to Chvatal's condition for hamiltonian cycle (see D. West's Intro. to Graph Theory.) from which below it is proven that the conjecture follows. Theorem (Chvatal's). Let G be a simple graph with degree sequence d₁≤ d₂≤ ...≤ d_n with n at least 3. If for i < (n+1)/2 we have that d_i ≥ i or d_n+1-i ≥ n-i. , then G has a Hamiltonian path. Lemma. If n is at least 2, then [n - σ(G) - 1 ≤ upper median of degree sequence of G] implies Chvatal's condition. Proof. Assume that n is at least 2 and n - σ(G) - 1 ≤ upper median of degree sequence of G . Observe that our assumption implies d_(n+2)/2 ≥ upper median of degree sequence of G ≥ n - σ(G) - 1. If i = 1, then since the graph is connected the Chvatal's condition clearly holds. So suppose 2 ≤ i < (n+1)/2. Then clearly σ(G) ≤ d_i. Now, if d_i < i, then i ≥ σ(G) + 1, which is equivalent to n -1- σ(G) ≥ n - i. Since i < (n+1)/2, it follows that n +1 - i ≥ (n+3)/2. Thus, d_n+1-i ≥ d_(n+3)/2 ≥ d_(n+2)/2≥ n - σ(G) - 1 ≥ n - i. QED

R	195.	If G is a simple connected graph with n > 1 such that a(G) - 1 ≤ κ(G) , then G has a Hamiltonian path.	definitions
		Jan 12, 2006. This is a Theorem of Chvatal & Erdos.

T	196.	If G is a simple connected graph with n > 1 such that b(G)/2 = radius(G), then G has a Hamiltonian path.	definitions
		Jan 12, 2006. Jan. 2008 DPW.

T	196a.	If G is a simple connected graph with n > 1 such that a(G) = radius(G), then G has a Hamiltonian path.	definitions reference
		Jan 12, 2006. Note that this conjecture was superseded by Sophie's #196, but since Pepper and Waller were aware of it and began working on it, I've included it on the list.

T	197.	If G is a simple connected graph with n > 1 such that girth(G) ≥ 2^a^{(G) - 1}, then G has a Hamiltonian path.	definitions
		Jan 12, 2006. Note that this conjecture was superseded by later conjectures, but since Pepper and Waller proved it, it is included on the list.

T	206.	If G is a simple connected graph with n > 1 such that Σ(G) ≤ 1 + 0.5mode_max(G), then G has a Hamiltonian path.*	definitions
		Jan 12, 2006. April 2008, Landon Jennings proved that this condition follows from Chvatal's sufficient condition for Hamiltonian paths.

T	215.	If G is a simple connected graph with n > 1 such that (1/2)domination(G) ≤ c_claw(G), then G has a Hamiltonian path.*	definitions
		Jan 12, 2006. Mar. 9, 2006. DeLaVina, John & Pepper.

		Dalmatian Heuristic
		Lower bounds for Total Domination g_t
R	226.	If G is a simple connected graph, then g_t(G) ≥ g(G))	definitions
		Feb. 23, 2007.

T	228.	If G is a simple connected triangle-free graph, then g_t(G) ≥ c(G)	definitions reference
		Feb. 23, 2007. Mar. 30, 2007. Stephen Hartke, Qi Liu, Doug West and Hehui Wu.

R	229.	If G is a simple connected graph, then g_t(G) ≥ n(G)/D(G)	definitions
		Feb. 23, 2007.

T	230.	If G is a simple connected graph, then g_t(G) ≥ 2 (CEIL[0.5radius(G)])	definitions reference
		Feb. 23, 2007. B. Waller & R. Pepper.

T	231.	If G is a simple connected graph, then g_t(G) ≥ 1 + ecc(Centers)	definitions reference
		Feb. 23, 2007.

T	249.	If G is a simple connected graph, then g_t(G) ≥ CEIL[girth(G)/2]	definitions reference
		Feb. 23, 2007. April 19, 2007: B. Waller & R. Pepper.

E	263.	If G is a simple connected graph on an odd number of vertices such that D(G) ≤ n(G)/2, then g_t(G) ≥ 3.	definitions
		Feb. 23, 2007.

		Sophie Heuristic
		Sufficient conditions on a simple connected graph G for Total Domination equal to Radius
		Note: the following conjectures were generated by a new heuristic for G.pc named Sophie. The program was queried for sufficient conditions for simple connected graphs on at least two vertices.
T	277.	Let G is a simple connected graph with n > 1. minimum {\|E_G(D)\|: D is a minimum total dominating set} =0.5radius(G) if and only if* g_t(G)=radius(G).	definitions reference
		Feb 25, 2007. Since radius was proven to be a lower bound for total domination (see 230), Sophie was queried for sufficient condition for the case of equality and subsequently reported the above equivalence. It is easily proven that if minimum {\|E_G(D)\|: D is a minimum total dominating set} =0.5radius(G), then* g_t(G)=radius(G). May 4, 2007: B. Waller proved the converse.