Written on the Wall II

Ermelinda DeLaVina (delavinae@uhd.edu)

		Lower bounds for maximum number of leaves over all spanning trees, Ls(G)
		Note: there is now a second list for Ls(G).
T	1.	If G is a simple connected graph, then Ls(G) ≥ n + 1 - 2m(G)	definitions  reference
		1996. In 1984, Hedetniemi and Laskar [HL] proved that for simple connected graphs Ls(G) ≥ n - 2m(G). In 1996, Fajtlowicz proved that for connected graphs on at least two vertices Ls(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 Ls(G)≥ gi(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 Ls(G) ≥ minimum of |NG(e)| - 1	definitions  reference
		1996. DeLaVina 1996

T	5.	If G is a simple connected graph, then Ls(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 Ls(G) ≥ 1 + n -m(G)- a(G)	definitions  reference
		1996. DeLaVina 1996

T	7.	If G is a simple connected graph, then Ls(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 Ls(G) ≥ maximum of disteven(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 disteven(v) - minimum of  disteven(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) + fG(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(distmax(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[degavg(G)]	definitions reference
		July 3, 2003. Mar 06, 2004, Bill Waller observes that for graphs that are p-regular and Kp-free, f(G) ≥ n/FLOOR[degavg(G)] (see conjecture #50 below)  follows from Fajtlowicz's result on the independence ratio that for graphs with max. degree at most p and Kq-free,  a(G)/n ≥ 2/(p+q). Mar. 07, 2004, Fajtlowicz sent a proof of f(G) ≥ n/degavg(G), see conjecture #50.
F	21.	If G is a simple connected graph, then b(G) ≥ CEIL(2distavg(B,V))	definitions
		July 3, 2003.  This is similar to Graffiti's #747 that  b(G) ≥ CEIL(2distavg(V)). Note: March 2004 now that the program has the forest number this bound was made for it also. See wowII conjecture #42 below. Sept. 2008: this counterexample was among the 11,716,571 connected 10-vertex graphs that my student H. Hemmati and I added to the database of G.pc,  The counterexample has  b(G) = 6 and distavg(B,V)=3.52. Increasing the order of either of the cliques in the counterexample did not increasee the difference between the left and right sides of the inequality, so it is still of interest if the difference can be arbitrarily large..
F	22.	If G is a simple connected graph, then CEIL(2dist(B,V)))≥ CEIL(2distavg(V))	definitions reference
		July 3, 2003. DeLaVina and Waller July 4, 2003; see the counterexample (drawn with Waller's GraphDraw program) Also note this conjecture was a by-product of dalmatian implemented in Graffiti.pc. See On Some History of the Development of Graffiti (ps 32MB)  (zipped ps 1MB)

F	23.	If G is a simple connected graph, then b(G) ≥ FLOOR[a(G) + distavg(M)/2]	definitions reference
		July 3, 2003. July 2005. See counterexample; b = 19, a(G)= 15, distavg(M) = 10. Note: This counterexample also serves as a counterexample to  b(G) ≥ a(G) + rad(G) -1, which in our paper we listed as an open but unnumbered conjecture of G.pc.
F	24.	If G is a simple connected graph, then b(G) ≥ l(G) + CEIL[minimum of disteven(v)/3]	definitions
		July 3, 2003. May 27, 2004 DeLaVina. Take two copies of complete(9) and enumerate the vertices of each 0, 1, 2, ... , 8. Join vertices 3, 4, and 5 of one copy to vertices 3, 4, and 5 of the other copy; and  join vertices 6, 7, and 8 of one copy to vertices 6, 7, and 8 of the other copy. Bipartite number is 4, every vertex has 7 of vertices at even distance, and maximum of local independence is 2.
F	25.	If G is a simple connected graph, then b(G) ≥ 2CEIL[(1 + minimum of disteven(v))/3]	definitions
		July 3, 2003.  May 27, 2004 DeLaVina. Same counterexample as in #24. Bipartite number is 4, and every vertex has 7 of vertices at even distance.
F	26.	If G is a simple connected graph, then b(G) ≥ CEIL[1 + dd(G)0.25]	definitions
		July 3, 2003. Mar. 6, 2004. (DeLaVina) The only counterexample that I know of at the moment has over 4000 vertices. It would be helpful to know if there is a smaller one.
F	28.	If G is a simple connected graph, then b(G) ≥ distmin(A)+ (distmin(M))0.25	definitions
		July 3, 2003. May 2004 see the counterexample. Bipartite number is 4, minimum distance between minimum degree vertices is 3, and minimum distance between maximum degree vertices is 2.
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) ≥ distmax(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.
F	30.	If G is a simple connected graph, then b(G) ≥ distmin(A)+ |EG(M(G))|0.25	definitions
		July 3, 2003. June 2005, Barbell(18,2) is a counterexample. Take two copies of K(18) and bridge them by an edge.

		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).
F	32.	If G is a simple connected graph, then path(G) ≥ distavg(A) + 0.5 eccavg(M)	definitions
		July 15, 2003. Aug 2005, the path on 5 vertices is a counterexample, path = 5, distavg(A) = 4 and the average of eccentricity of maximum degree vertices is 8/3; this may have resulted from an initially unnoticed computational error(s) for average of distances or eccentricities in earlier code.
F	33.	If G is a simple connected graph, then path(G) ≥ CEIL[2distavg(M,V)]	definitions
		July 15, 2003. Oct 2005 see the counterexample. Path number is 7,distavg(M,V = avg dist = 3.56.
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.
F	36.	If G is a simple connected graph, then path(G) ≥ 2rad(G)/dp(G)	definitions
		July 15, 2003. DeLaVina, June 2005 see the counterexample. Path number is 5, radius is 3, and dp is 1.

		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.
F	38.	If G is a simple connected graph, then f(G) ≥ CEIL[0.5(res(G)+b(G))]	definitions
		Mar 05, 2004. May 2004 see the counterexample. Forest number is 6, bipartite is 10, and residue is 3.
F	39.	If G is a simple connected graph, then f(G) ≥ a(G) +CEIL[(1/3) distavg(B,V))]	definitions
		Mar 05, 2004. Nov. 2005 As stated this conjecture is false see the counterexample, but I still think there may be a constant less than 1/3 for which the relation may be true. For the counterexample forest is 21, independence number is 20 and average distance from the boundary is slightly more than three.
F	41.	If G is a simple connected graph, then f(G) ≥ CEIL[distavg(V)*(1 + sqrt(p(G)) ]	definitions
		Mar 05, 2004. June 2005, binary stars with 5 leaves on each end and interior path of length at least 8 are counterexamples. Path covering number is 9, and increasing the length of the interior path increases the average distance, which shows that the difference between the left and right of the inequality can be arbitrarily large.
F	42.	If G is a simple connected graph, then f(G) ≥ CEIL(2distavg(B,V))	definitions reference
		Mar 05, 2004. Note #21 of wowII is b(G) ≥ CEIL(2distavg(B,V)). Sept. 2008: this counterexample was among the 11,716,571 connected 10-vertex graphs that my student H. Hemmati and I added to the database of G.pc,  The counterexample has  f(G) = 6 and distavg(B,V)=3.52. Increasing the order of either of the cliques in the counterexample did not increasee the difference between the left and right sides of the inequality, so it is still of interest if the difference can be arbitrarily large..
F	43.	If G is a simple connected graph, then f(G) ≥ FLOOR[sqrt[path(G)*(b(G)-1)]]	definitions
		Mar 05, 2004. Mar 06, 2004, DeLaVina: It is easy shown that for graphs on more than one vertex,  f(G) ≥ sqrt[path(G)*(b(G)+2)/2], since f(G)  ≥ path(G) and f(G)  ≥ b(G)/2  + 1, the +1 we get for connected graphs on more than one vertex. Mar. 6, 2004, Ryan Pepper's counterexample follows: "Take a path on 7 vertices and alternately label its vertices red and blue (pendants are red). Join both vertices of an empty graph on two vertices to every vertex that is red and take another empty graph on two vertices and join both of them to every vertex that is blue. This gives you a bipartite graph on 11 vertices. So, b(G)=11, and f(G) >= p(G) >= 7.". Further he showed that f(G) = 7.
F	44.	If G is a simple connected graph, then f(G) ≥ a(G) + FLOOR[(1/2) average of ecc(v)]	definitions
		Mar 05, 2004. July 2005, DeLaVina see the counterexample. Forest number is 17, independence number is 13, and average eccentricity is 12.1905.
F	45.	If G is a simple connected graph, then f(G) ≥ FLOOR[path(G) - 1 + (1/3)(n mod D(G)) ]	definitions
		Mar 05, 2004. Mar 06, 2004, DeLaVina: K3 with K12 attached to each vertex is a counterexample. f = 5, path = 4, n = 36, D(G) = 24.
F	46.	If G is a simple connected graph, then f(G) ≥ FLOOR[path(G) - 1 + (1/3)(n mod D(G)) ]	definitions
		Mar 05, 2004. Mar 06, 2004, DeLaVina: K3 with K12 attached to each vertex is a counterexample. f = 5, path = 4, n = 36, D = 13.
R	47.	If G is a simple connected graph, then f(G) ≥ diam(G) + fG(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) + fG(1) -1	definitions reference
		Mar 05, 2004. The proof is similar to that of #47. DeLaVina and Waller 2004. *must check algorithm for circumference.
F	49.	If G is a simple connected graph, then f(G) ≥ CEIL[ 2 + (1/6)*length(G) ]	definitions
		Mar 05, 2004. Mar. 08, 2004, Ryan Pepper: a path on 38 vertices is a counterexample.
T*	50.	If G is a simple connected graph, then f(G) ≥ n/FLOOR[degavg(G)]	definitions reference
		Mar 05, 2004. Note conj. #20 of wowII is b(G) ≥ n/FLOOR[degavg(G)]. Mar 06, 2004, Bill Waller observes that for graphs that are p-regular and Kp-free, f(G) ≥ n/FLOOR[degavg(G)]  follows from Fajtlowicz's result on the independence ratio that for graphs with max. degree at most p and Kq-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/degavg(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"
F	51.	If G is a simple connected graph, then f(G) ≥ diam(G) + FLOOR[(1/3)*dd(G) ]	definitions
		Mar 05, 2004. Mar 06, 2004, DeLaVina: progressive-join(complete(9), complete(9)) is a counterexample. f = 4, diam = 2, dd = 9.
F	52.	If G is a simple connected graph, then f(G) ≥ CEIL[(1/2)*[dd(G) + 1 + (n mod D(G))] ]	definitions
		Mar 05, 2004. Mar 06, 2004, DeLaVina: progressive-join(complete(9), complete(9)) is a counterexample. f = 4, n = 18, D = 17, dd = 9.
F	53.	If G is a simple connected graph, then f(G) ≥ 2*CEIL[modemin(G) /degavg(G)]	definitions
		Mar 05, 2004. DeLaVina, Mar. 23, 2004; see the counterexample (drawn with Waller's GraphDraw program)
F	54.	If G is a simple connected graph, then f(G) ≥ CEIL[distavg(V) +(1/2)*minimum of  disteven(v)]	definitions
		Mar 05, 2004. DeLaVina, Mar. 23, 2004; Take two copies of complete(9) and enumerate the vertices of each 0, 1, 2, ... , 8. Join vertices 3, 4, and 5 of one copy to vertices 3, 4, and 5 of the other copy; and  join vertices 6, 7, and 8 of one copy to vertices 6, 7, and 8 of the other copy. Forest number is 4, average distance is slightly less than 1.5, but every vertex has 7 of vertices at even distance.
F	55.	If G is a simple connected graph, then f(G) ≥ CEIL[minimum of  disteven(v) -1 + |N(A)|/3], where A is the set of vertices of minimum degree.	definitions
		Mar 05, 2004.  Mar 06, 2004, DeLaVina: progressive-join(complete(9), complete(9)) is a counterexample. f = 4 and minimum of  disteven(v)  = 1. There are two vertices of min. degree, 10, and |N(A)| = 16.
F	56.	If G is a simple connected graph, then f(G) ≥ CEIL[sqrt[distmax(A)*(1+degavg(G))]], where A is the set of vertices of minimum degree.	definitions
		Mar 05, 2004. DeLaVina, Mar. 23, 2004; the counterexample to #54 is also a counterexample to #56
		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.
F	60.	If G is a simple connected graph, then f(G) ≥ domination(G) + FLOOR[tree(G)/2]	definitions
		Mar 25, 2004. April 22, 2006. See the counterexample. Forest number is 6, domination number is 4, and tree number is 6..
F	62.	If G is a simple connected graph, then f(G) ≥ domination(G) + maximum of l(v) -1	definitions
		Mar 25, 2004. Oct 2005 see the counterexample. Forest number is 5, domination number =3, and max local indep is 4.
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.
F	69.	If G is a simple connected graph, then tree(G) ≥ maximum of l(v) + FLOOR[sqrt(domination(G))]	definitions
		Apr 04, 2004. May 2004 see the counterexample. Tree number is 4, maximum of local independence is 3, and domination is 4.
F	70.	If G is a simple connected graph, then tree(G) ≥ FLOOR[distavg(C,V)] + maximum of l(v)	definitions
		Apr 04, 2004. June 2005 see the counterexample. Tree number is 12, maximum of local independence is 11, and floor of average distance from the center is 2.
F	71.	If G is a simple connected graph, then tree(G) ≥ FLOOR[distavg(B,V)/3] + maximum of l(v)	definitions
		Apr 04, 2004. Oct 2005, see the counterexample. Tree number is 16, max of local independence is 15, and average distance from the boundary is slightly more than 6. .
F	73.	If G is a simple connected graph, then tree(G) ≥ FLOOR[average of ecc(v)/2] + maximum of l(v)	definitions
		Apr 04, 2004. June 2005 see the counterexample. Tree number is 13, maximum of local independence is 12, and  average of eccentricities is 4.25.
F	74.	If G is a simple connected graph, then tree(G) ≥ CEIL(2distavg(B,V))	definitions reference
		Apr 04, 2004. May 2004 DeLaVina see counterexample.
F	75.	If G is a simple connected graph, then tree(G) ≥ b(G)/FLOOR[degavg(G)]	definitions
		Apr 04, 2004. July 2005, DeLaVina. Take a clique on p vertices and to each vertex attach a path on p vertices by the endpoint of the path for a total of p(p+1) vertices. The tree number is 2(p+1), the bipartite number is  p^2 + 2 , and the average degree is less than 3. For p at least 5, the graph serves as a counterexample.
F	77.	If G is a simple connected graph, then tree(G) ≥ distavg(C,V) + ecc(B) + 1, where B is the set of vertices of boundary vertices.	definitions
		Apr 04, 2004. April 22, 2006 see the counterexample. Tree number is 6, distavg(C,V) is 7/6, and ecc(B) is 4..
F	79.	If G is a simple connected graph, then tree(G) ≥ (n mod 2)* CEIL(2distavg(V))	definitions
		Apr 04, 2004. Oct 2005 see the counterexample. Path number is 7, n = 25,  avg dist = 3.56.
F	78.	If G is a simple connected graph, then tree(G) ≥ CEIL[path(G)/3 + maximum of l(v) -1]	definitions
		Apr 04, 2004. June 2005 see the counterexample. Tree number is 7, maximum of local independence is 6, and  path number is 7.
F	80.	If G is a simple connected graph, then tree(G) ≥ CEIL[sqrt[2*sqrt[|N(M)| + 1]]], where M is the set of vertices of maximum degree of the complement of G.	definitions
		Apr 04, 2004. Oct. 28, 2005. Large barbells, beginning with Barbell(32,2), are counterexamples; the tree number is 4 and the is |N(M)| equal to the number of the vertices.
F	81.	If G is a simple connected graph, then tree(G) ≥ CEIL[sqrt[2*(1+sqrt[|N(A)|)]]], where A is the set of vertices of minimum degree.	definitions
		Apr 04, 2004. This statement must have a typo, since even fairly small cliques are counterexamples.
F	82.	If G is a simple connected graph, then tree(G) ≥ 2*CEIL[(2*ecc(B) + 1)/3], where B is the set of vertices of boundary vertices.	definitions
		Apr 04, 2004. April 22, 2006 see the counterexample. Tree number is 8 and ecc(B) is 6.
F	83.	If G is a simple connected graph, then tree(G) ≥ 1 + distavg(C,V) * minimum of l(v)	definitions
		Apr 04, 2004. August 16, 2005, see the counterexample. Tree number is 6, minimum of local independence is 3, and  average distance from centers is 2.
		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.
F	87.	If G is a simple connected graph, then b(G) ≤ 1 + minimum of l(v)  + D(G)	definitions
		April 10, 2004. Oct 2005, see the counterexample. Bipartite number is 8, min of local independence is 2, and D(G) = 4.
F	88.	If G is a simple connected graph, then b(G) ≤ 1 + average of l(v)  + average degree of G.	definitions
		April 10, 2004. Dec. 2005, the join of discrete 2 and K(m,m) is a counterexample to this conjecture but it is still open as to whether or not the relation holds without the 1, that is b(G) ≤ average of l(v)  + average degree of G is still open.
E	89.	If G is a simple connected graph, then b(G) ≤ 2a(G)	definitions
		April 10, 2004.
F	90.	If G is a simple connected graph, then b(G) ≤ f(G) * (FLOOR[2average of l(v)])/2	definitions
		April 10, 2004. Oct 2005, see the counterexample. Bipartite number is 6, forest number is 5, and average of local independence is 14/9.
		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.
F	95.	If G is a simple connected graph, then a(G) ≤ CEIL[f(G) -LN(path(G))]	definitions
		April 21, 2004. April  2006, see the counterexample. a(G) is 7, forest number is 8, and path number  is 8.
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
F	98.	If G is a simple connected graph, then a(G) ≤ maximum of disteven(v)  + FLOOR[p(G)/2]	definitions
		April 21, 2004. DeLaVina May 2004; see counterexample.
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) 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.
F	104.	If G is a simple connected graph, then a(G) ≤ rad(G) + maximum of l(v) + |N(S) - S| -1, where S is the set of minimum degree vertices of the complement of the graph G and the neighborhood is taken in the complement.	definitions reference
		April 21, 2004. Fajtlowicz April 2004. This relation was interesting in light of his theorem  rad(G) + maximum of l(v) -2  ≤ a(G)  in our Griggs and Graffiti paper (see reference link). #104 is false as Fajtlowicz noted "You can construct d-regular graph of small radius, say 3 or 4 with close to d^3 vertices. Then a will much more than d, but loc ind is at most d and the term |N(S) - S| is 0", see an example. He then asks for the smallest S such that a counterexample is possible.
F	105.	If G is a simple connected graph, then a(G) ≤ tree(G)*SQRT[domination(G)] - 1	definitions
		April 21, 2004. April 2004. Bill Waller proved that a(G) ≤ tree(G)*domination(G) - 1. Nov. 2005, see the counterexample. Independence number is 16, tree number is 12, and domination is 2. Note that this counterexample belongs to a family of graphs with independence number 3k+1, tree number 2k + 2, and domination 2 for k a positive integer. For large k, members of the family will make the difference a(G) - tree(G)*SQRT[domination(G)] large.
E	106.	If G is a simple connected graph, then a(G) ≤ n - domination(G)]	definitions
		April 21, 2004.
F	107.	If G is a simple connected graph, then a(G) ≤ maximum disteven(v)* CEIL[distavg(B,V)/2]	definitions
		April 21, 2004.  Oct 2005, see the counterexample. independence number is 6, maximum disteven(v) is 5, and  distavg(B,V) is about 1.99.
F	110.	If G is a simple connected graph, then a(G) ≤ FLOOR[(residue(G)+1)* average of l(v) - 1]	definitions
		April 21, 2004.  Oct 2005, see the counterexample. independence number is 7, average of local independence is 11/7, and  residue is 4.
		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 { modemax(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.
F	123	If G is a connected X,Y bigraph such that |X| £ |Y|, then m(G) ≥ minimum{FLOOR[1 + degavg(G)}, |X|}	definitions
		June, 2004.  Jan 2005,  Iride Gramajo; see counterexample.
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.
F	126	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) ≥ minimum{|N(A)-A|, |X|}	definitions
		December 2004. I. Gramajo, Feb 2005; see counterexample.
T	127	If G is a simple connected graph, then m(G) ≥ minimum{1 + ecc(centers), minimum of disteven(G)}	definitions
		December 2004.  I. Gramajo, Mar 2005.
F	128	Let G be a connected X,Y bigraph such that |X| £ |Y|,. Then m(G) ≥ minimum of { freq(d(G)), freq(s(G)), D(Y)}	definitions
		December 2004. I. Gramajo, Feb 2005; see counterexample.
T	129	Let G be a connected X,Y bigraph such that |X| £ |Y|,. Then m(G) ≥ |X|/(D(Y)-1)	definitions  reference
		December 2004.  D. R. Woodall of the University of Nottingham, Sept. 2008.
T	130	Let G be a connected X,Y bigraph such that |X| £ |Y|,. Then m(G) ≥ |X|/(S(G)-1)	definitions  reference
		December 2004.  D. R. Woodall of the University of Nottingham, Sept. 2008
		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.
F	132.	If G is a simple connected graph, then path(G) ≥ 2*rad(G)/|N(A)|, where A is the set of vertices of minimum degree.	definitions
		July 12, 2005. April 22, 2006 see counterexample. path number is 5, radius is 3 and |N(A)| is 1.
F	134.	If G is a simple connected graph, then path(G) ≥ girth - 1+ ecc(centers(G2))	definitions
		July 12, 2005. Jan 2006, see counterexample.
T	135.	If G is a simple connected graph, then path(G) ≥ girth/d(G)	definitions
		July 12, 2005. B. Waller
F	139.	If G is a simple connected graph, then path(G) ≥ u(G)*(1+2*distavg(C))	definitions
		July 12, 2005. The counterexample to 105 was also a counterexample the this conjecture. path number is 4, u(G) = 1 and, distavg(C) = 43/28.
		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.
F	148.	If G is a simple connected graph, then tree(G) ≥ diameter(G) -1 + CEIL(distavg(Centers(G2,V))	definitions
		July 19, 2005. Oct. 2005. See counterexamples. In these graphs, tree number and diameter differ by one, but average distance from the centers of the 2nd power graph can be arbitrarily large.
F	149.	If G is a simple connected graph, then tree(G) ≥ 1+ m(G) *cK3(G)	definitions
		July 19, 2005. Nov. 2005. For k ≥ 5, take G as the (k-1)-regular bipartite graph with bipartitions of order k. Then G is a counterexample, since tree number will be k, and matching will be k.
F	150.	If G is a simple connected graph, then tree(G) ≥ Tdistmin(v)/m(G)	definitions
		July 19, 2005.Nov. 2005. See counterexample. In this graph, tree number is 15, min total distance is 31 (realized by a max degree vertex), and matching is 2.
F	151.	Let er = maximum of {|E(R(v))|: v is a center of G}. If G is a simple connected graph, then tree(G) ≥ 1 + er ^cc4(G)	definitions
		July 19, 2005. Nov. 2005. See counterexample. In this graph, tree number is 9, er is at least 9 and the graph is C4-free.
			Next List
		2nd Run for Lower bounds for maximum number of leaves over all spanning trees, Ls(G) note: conjecture 5 was repeated from the first run for L.
E	152.	If G is a simple connected graph, then Ls(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 Ls(G) ≥ D(G).	definitions
		Aug 8, 2005.
F	156.	If G is a simple connected graph, then Ls(G) ≥ order of the intersection of radial circles + CEIL[0.5*distavg(Centers)].	definitions
		Aug 8, 2005. April 22, 2006, Cycle 19 is a counterexample. L is 2, order of the intersection of radial circles is 0, and average distance from centers which  is  also average distance of the graph for cycle 19 is 5.
E	158.	If G is a simple connected graph, then Ls(G) ≥ maximum of l(v) + 1 - cK3(G).	definitions
		Aug 8, 2005. It is easily proven that Ls(G) ≥ maximum of l(v) and if the graph has a triangle it is also easily proven that Ls(G) ≥ maximum of l(v) can be improved by one.
T	159.	If G is a simple connected graph, then Ls(G) ≥ maximum of l(v) + 0.5*w(G) - 1.	definitions
		Aug 8, 2005.  Oct. 2005, if G is not K1, the the stronger bound of Ls(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 Ls(G) ≥ CEIL[0.5*D(G2)].	definitions
		Aug 8, 2005.  Oct 10, 2005.
E	164.	If G is a simple connected graph, then Ls(G) ≥ D(G2) - D(G).	definitions
		Aug 8, 2005.  Oct 10, 2005.
F	167.	If G is a simple connected graph, then Ls(G) ≥ d(G) + FLOOR[(1/3)*|N(M2)-M2|], where M2 is the set of vertices of maximum degree of G2and the neighborhood is taken in G2.	definitions
		Aug 8, 2005.  Jan. 2006. See counterexample.
F	168.	If G is a simple connected graph, then Ls(G) ≥ 2*CEIL[|N(A)-A|/3], where A is the set of vertices of minimum degree of G.	definitions
		Aug 8, 2005. April 22, 2006, the Harris and Mossinghoff graph is  a counterexample. L is 6 and |N(A) - A| is 12.
F	170.	If G is a simple connected graph, then Ls(G) ≥ [maximum  of  disteven(v)  in G] -  [minimum of  disteven(v) in G2.]	definitions
		Aug 8, 2005. Oct. 2005. See counterexample. In this graph, Ls(G) is 5, the top white vertices realizes  maximum  of  disteven(v)  in G which is 7, and the bottom white vertex realizes minimum of  disteven(v) in G2 which is one.
			Next List
		Lower bounds for Ls(G) + b(G)
T	173.	If G is a simple connected graph on at least 2 vertices, then Ls(G) + b(G)  ≥ n + 1 + cbipartite(G).	definitions  reference
		Aug 8, 2005.  Note that since 2a(G) ≥ b(G) , G.pc's 173 is an improvement over Grigg's Conjecture Ls(G)  ≥ n - 2a(G)  + 1, which inspired the first run of lower bounds (listed on wowII) on Ls(G). DeLaVina and Waller proved that if G is a simple connected graph on at least 2 vertices, then Ls(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 Ls(G) ≥ 2. Note: Since n - Ls(G) is the connected domination number, gc of a graph, this relation provides an upper bound on the connected domination number b(G)  ≥  gc+ 1 + cbipartite(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) ≥  g2 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 Ls(G) + b(G)  ≥ n + D(G)*cbipartite(G).	definitions
		Aug 8, 2005. In the case that G is a bipartite graph, the relation follows since b(G) = n and Ls(G) ≥ D(G); otherwise, the relation follows from Ls(G) + b(G)  ≥ n + 1, see wowII 173.
F	187.	If G is a simple connected graph on at least 2 vertices, then Ls(G) + b(G)  ≥  |N(M2)-M2|+ minimum of l(v) + 2, where M2 is the set of vertices of maximum degree of G2.	definitions
		Aug 8, 2005.   This counterexample was among the 11,716,571 10-vertex graphs that my student H. Hemmati and I added to the database of G.pc, Sept. 2008. The counterexample has Ls(G) = 5, b(G) = 6,  |N(M2)-M2| = 8 and minimum of l(v) = 2.
		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	190a.	If G is a simple connected graph with n > 1 such that LS(G)-1 ≤ σ(G), then G has a Hamiltonian path.	definitions
		Jan 12, 2006.  At some point in the program's execution, this conjecture (appeared together with #190) was eventually superseded by some combination of other conjectures, however, since we thought about this conjecture, it is included on this list. Note, the program may have made this conjecture because if L = 2 then must be a path or cycle, which has a Hamiltonian path, but the hypothesis of #190 is not satisfied for paths. June 2013, in [M1], using theorems of Griggs and Wu, and of Dirac, Mukwembi proved that if \( \delta \ge 5 \) and \( \delta \ge L -1 \), then G is Hamiltonian and in [M2] he extended this to if \( \delta \ge 3 \) and \( \delta \ge L -1 \), then G is Hamiltonian. [M1] Simon Mukwembi, Minimum degree, leaf number and Hamiltonicity, American Mathematical Monthly, 115-, (2013). [M2] Simon Mukwembi, On spanning cycles, paths and trees, Discrete Applied Mathematics, 2217-2222, (2013).
T	191.	If G is a simple connected graph with n > 1 such that 2 * lower median of degree sequence of G - 1 ≤ min { deg(v) + deg(u) : v and u are not adjacent }, then G has a Hamiltonian path.	definitions
		Jan 12, 2006. June 2010, Richard Stong (CCR, La Jolla).
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  d1≤ d2≤ ...≤ dn with n at least 3. If for i < (n+1)/2 we have that di ≥  i or dn+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) ≤ di. Now, if di < 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,  dn+1-i ≥ d(n+3)/2 ≥ d(n+2)/2 ≥ n - σ(G) - 1 ≥ n - i.                   QED
F	193.	If G is a simple connected graph with n > 1 such that 1+  Σ(G) ≤ frequency of λmax(G)  then G has a Hamiltonian path.	definitions
		Jan 12, 2006. The Harris and Mossinghoff graph which is a smallest 2-connected and claw-free that has no hamiltonian path also served as a counterexample to Sophie's number 6; frequency of λmax(G)  = 18 and 1+  Σ(G)  = 16.
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) ≥ 2a(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	198.	If G is a simple connected graph with n > 1 such that b(G) ≤ 2 + eccavg(M), then G has a Hamiltonian path, where M is the set of vertices of maximum degree of G.	definitions
		Jan 12, 2006. June 2010, Richard Stong (CCR, La Jolla).
T	201.	If G is a simple connected graph with n > 1 such that path(G) = 2 + Σ(G), then G has a Hamiltonian path.	definitions
		Jan 12, 2006. May 2010, Richard Stong (CCR, La Jolla).
T	205.	If G is a simple connected graph with n > 1 such that induced circumference(G) ≥ 2(annihilation number -1), then G has a Hamiltonian path.	definitions
		Jan 12, 2006. May 2010, Richard Stong (CCR, La Jolla).
F	202.	If G is a simple connected graph with n > 1 such that λmax(G) ≤  κ(G), then G has a Hamiltonian path.	definitions
		Jan 12, 2006.  Mar.13, 2006 I came across the paper  Traceability in small claw-free graphs, in which J.M. Harris and M. J. Mossinghoff found that a claw-free, 2-connected graph with fewer than 18 vertices is traceable, and determined all non-traceable, claw-free, 2-connected graphs with exactly 18 vertices and a minimal number of edges. See an example of such a graph. [HM]   J.M. Harris and M. J. Mossinghoff , Traceability in small claw-free graphs, The Ninth Quadrennial International Conference on Graph Theory, Combinatorics, Algorithms and Applications, Electron. Notes Discrete Math, 11, Elsevier, Amsterdam, 2002.
T	203.	If G is a simple connected graph with n > 1 such that  Σ(G) ≤ λmax(G), then G has a Hamiltonian path.	definitions
		Jan 12, 2006. Note that in G, the value of λmax(G) corresponds to the maximum of all co-clique numbers of vertices. For a vertex, v, compute the clique number of the subgraph induced by V(G) - N[v], this will be the co-clique number of a vertex. Note, N[v] is the vertex v together with its neighborhood.  Let us denote this value at wc(G). Then the conjecture can be rewritten as n - (σ(G) + 1) ≤  wc(G), which for σ(G) ≤ 3 is easily argued since the graph must have a large clique....
		Jan 12, 2006. June 2010, Richard Stong (CCR, La Jolla).
F	204.	If G is a simple connected graph with n > 1 such that induced circumference(G) ≥ 2+ median of degree sequence of G, then G has a Hamiltonian path.	definitions
		Jan 12, 2006. Feb. 16th R. Pepper, see counterexample. Induced circumference is 12 and the median of the degree sequence of the complement is 10.
T	206.	If G is a simple connected graph with n > 1 such that Σ(G)  ≤  1 + 0.5*modemax(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	207.	If G is a simple connected graph with n > 1 such that (1/4)* [1 + 2*|E(G)| ]   ≤   modemax(G), then G has a Hamiltonian path.	definitions
		Jan 12, 2006. April 5, 2008, I coded in Chvatal's sufficient condition and for the graphs in the program's database the conjectured sufficient condition implies Chvatal's . June 2010, Richard Stong (CCR, La Jolla); he proved |E(G)|  ≤   2*modemax(G)-1 implies Chvatal's sufficient condition for a Hamiltonian path.
T	208.	If G is a simple connected graph with n > 1 such that (1/2)* [1 + (2/3)*|E(G)| ]   ≤   matching(G), then G has a Hamiltonian path.	definitions
		Jan 12, 2006. April 5, 2008, I coded in Chvatal's sufficient condition and for the graphs in the program's database the conjectured sufficient condition implies Chvatal's. June 2010, Richard Stong (CCR, La Jolla); he also communicated that this does not imply Chvatal's sufficient condition. This is likely due to my error in coding the expression.
F	210.	If G is a simple connected graph with n > 1 such that (2/3)*lower median of degree sequence of G ≤ λmin(G), then G has a Hamiltonian path.	definitions
		Jan 12, 2006. Oct. 2008: this counterexample was among the 11,716,571 connected 10-vertex graphs that my student H. Hemmati and I added to the database of G.pc.  The lower median of the complement of the graph is three, and λmin(G) = 2.
F	211.	If G is a simple connected graph with n > 1 such that 2*( the lower median of degree sequence of G ) ≤ |N(A)|, then G has a Hamiltonian path, where A is the set of vertices of minimum degree.	definitions
		Jan 12, 2006. June 2010, Richard Stong (CCR, La Jolla) has a counterexample to both 211 & 212.
F	212.	If G is a simple connected graph with n > 1 such that 2*(the median of degree sequence of G  - 1) ≤ |N(A) - A|, then G has a Hamiltonian path, where A is the set of vertices of minimum degree.	definitions
		Jan 12, 2006. June 2010, Richard Stong (CCR, La Jolla) has a counterexample to both 211 & 212.
F	214.	Let M = {v:  λ(v) = λmax(G)}. Then if G is a simple connected graph with n > 1 such that  3*g2 (G)  ≤  |M|  ,  then G has a Hamiltonian path.	definitions
		Jan 12, 2006. Mar. 10, 2006: my counterexample to Sophie's 29 is also a counterexample to this conjecture. This graph has 2-domination of the complement equal to three and has 18 vertices that realize the maximum of local independence.
T	215.	If G is a simple connected graph with n > 1 such that  (1/2)*domination(G)  ≤  cclaw(G),  then G has a Hamiltonian path.	definitions
		Jan 12, 2006. Mar. 9, 2006. DeLaVina, John & Pepper Note that this statement is equivalent to the statement that if the graph G is claw-free and the domination number is at most 2, then G has a Hamiltonian path.. May 11, 2006: I came across a 1994 result of A. A. Ageev Dominating Sets and Hamiltonicity in K1,3-free Graphs, in which there is the similar result for Hamiltonian graphs, namely, if the graph G is claw-free, 2-connected and the domination number is 2, then G is Hamiltonian. [AA] A. A. Agreev, Dominating Sets and Hamiltonicity in K1,3-free Graphs, Siberian Mathematical Journal,  Vol. 35, No. 3, 1994.
F	216.	If G is a simple connected graph with n > 1 such that  1/(2-B(G))  ≤  cclaw(G),  then G has a Hamiltonian path.	definitions
		Jan 12, 2006. Mar. 9, 2006. This counterexample is claw-free and has 3 pairs of distance two vertices in the boundary.
F	218.	If G is a simple connected graph with n > 1 such that  maximum {disteven(v) - even horizontal(v): v in V(G)}  ≤  4*cresidue=2(G) + 1,  then G has a Hamiltonian path.	definitions
		Jan 12, 2006. Feb 28th, Greg Henry. His counterexample has residue = 5 ,  cresidue=2(G) =0, maximum {disteven(v) - even horizontal(v): v in V(G)} = 1, and has no Hamiltonian path.
		Dalmatian Heuristic
		A conjecture for the independence number of degree-regular connected graphs.
F	219.	If G is a simple connected graph with maximum degree equal to minimum degree, then a(G) = maximum{ceiling[b(G)/2], maximum {disteven(v) - even horizontal(v): v in V(G)}}	definitions
		March  2006.  For simple graphs it easily seen that a(G) ≥  ceiling[b(G)/2] and for simple connected graphs it is known that that a(G) ≥ maximum {disteven(v) - even horizontal(v): v in V(G)}; Graffiti's 750 inspired Fajtlowicz to note the latter lower bound on the independence number. May 3, 2006. R. Pepper. Dodecahedron is a counterexample. Note: A smallest order counterexample I am fairly certain must have at least 10 vertices.
		Dalmatian Heuristic
		Lower bounds for Total Domination gt
R	226.	If G is a simple connected graph, then gt(G) ≥ g(G))	definitions
		Feb. 23, 2007.
F	227.	If G is a simple connected graph such that D(G) ≤ n(G)/2 , then gt(G) ≥ g(G))	definitions
		Feb. 23, 2007.  April 18, 2007: Hehui Wu, "The idea is to generate a random graph H with edge probability exceeding 1/2 by a nonzero constant.  For fixed k, it holds almost always that g(H) > k and D(H) > n/2.  To form G, add to H three vertices forming a 3-clique T. Partition V(H) into four sets, one a bit smaller than the others.  Make each vertex of T adjacent to the small set and one of the other three.  Now T is a total dominating set, D(G) < n/2, g(G) > 3."
T	228.	If G is a simple connected triangle-free graph, then gt(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 gt(G) ≥ n(G)/D(G)	definitions
		Feb. 23, 2007.
T	230.	If G is a simple connected graph, then gt(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 gt(G) ≥ 1 + ecc(Centers)	definitions  reference
		Feb. 23, 2007.
F	234.	If G is a simple connected graph, then gt(G) ≥ ecc(B)/modemin(G).	definitions
		Feb. 23, 2007.  April 21 R. Pepper forwarded a counterexample;  gt(G) = 6, ecc(B) = 7, and modemin(G)=1.
F	236.	If G is a simple connected graph such that girth(G) ≥ 5, then gt(G) ≥  ecc(B).	definitions
		Feb. 23, 2007. April 21, 2007 R. Pepper sent a counterexample; girth = 5, gt(G) = 10 and ecc(B) = 11. April 24, 2007, B. John forwarded a counterexample and here is a simplified version of his counterexample; girth = 6, gt(G) = 8 and ecc(B) = 9.
F	237.	If G is a simple connected graph such that δ(G) ≥ 2, then gt(G) ≥  ecc(B).	definitions
		Feb. 23, 2007.  April 20, 2007: B. John, see counterexample; gt(G) = 6 and ecc(B) = 7.
F	238.	If G is a simple connected graph, then gt(G) ≥  (3/2)*number of components(<N[S]>), where <N[S]> is the subgraph induced by the closed neighborhood of the set of vertices of degree two.	definitions
		Feb. 23, 2007.  March 11, 2007. DeLaVina. Let G be the union of K2 and k*K3. Then each vertex of the K2 is joined to two vertices of each K3. Then total domination is k + 2 and components(<N[S]>) is k. For k = 6 see graph.
F	239.	If G is a simple connected C4-free graph, then gt(G) ≥  number of components(<N(S)>), where <N(S)> is the subgraph induced by the neighborhood of the set of vertices of degree two.	definitions
		Feb. 23, 2007.  August 18, 2009. This counterexample was among the graphs in the newly augmented database of G.pc.  The graph is connected, C4-free gt(G) = 4 and  number of components(<N(S)>) = 6.
F	240.	If G is a tree, then gt(G) ≥  number of components(<N(S)-S>), where S is the set of vertices of degree two.	definitions
		Feb. 23,  2007.  May 2009, P. Feit discovered a 34-counterexample that clearly belongs to a family that demonstrates that the right can be arbitrarily larger than the right. May 2009, inspired by this conjecture [DLPW] proved that  if G is a tree, then gt(G) ≥  number of components(< V(T) - S>) + p2/2 - 1, where S is the set of vertices of degree two and p2 is the order of a largest component induced by S. [DLPW] DeLaVina, Larson, Pepper, and Waller, Graffiti.pc on the total domination number of a tree, preprint 2009.
F	244.	If G is a simple connected graph, then gt(G) ≥ [1 + components(<M>)]/median(G), where <M> is the subgraph induced by the set of vertices of maximum degree.	definitions
		Feb. 23, 2007.  June 2018, E. DeLaVina & A. Melgar.
F	245.	If G is a simple connected graph such that δ(G) ≥ 3, then gt(G) ≥ FLOOR[eccavg(M)], where M is the set of vertices of maximum degree.	definitions
		Feb. 23,  2007.  May 4, 2007: DeLaVina. See counterexample. gt(G) = 4 and eccavg(M)=5.
F	246.	If G is a tree, then gt(G) ≥  m(G) - 1	definitions  reference
		Feb. 23,  2007.  DeLaVina March 2007: counterexample Let H be P5 with a spike at the center vertex. Let G(k) be the union of  K1, P2 and k copies of H. Now take a K1 and join it to one vertex of degree one in each of the k+2 components of G(k). Let the resulting graph be denoted by G(k). Then the matching number is 3k+2, and the total domination number is 2k+2 . See G(2). March 2007: R. Pepper proved that the size of a minimum maximal matching bounds the total domination number below for trees, see reference.
F	248.	If G is a  simple connected graph such that girth(G) ≥  6, then gt(G) ≥  SQRT[2* p(G)]	definitions
		Feb. 23,  2007.  Sept. 2008: Cycle 6 with one endpoint of each of k P2s identified with one vertex of the 6-cycle is a counterexample when k is at least 9. For k = 9 this among graphs that my student H. Hemmati and I added to the database of G.pc,  The counterexample has gt(G) = 4 and path covering number is k.
T	249.	If G is a  simple connected graph, then gt(G) ≥  CEIL[girth(G)/2]	definitions  reference
		Feb. 23,  2007.  April 19, 2007 B. Waller & R. Pepper.
F	250.	If G is a  simple connected C4-free graph, then gt(G) ≥  circumference(G)/2.	definitions
		Feb. 23,  2007.  April 20, 2007: Independently R. Pepper and E. DeLaVina found counterexamples belonging to the same family of counterexamples. For k ≥ 2, take the union of star(k+1) and cycle(4k). Label the vertices of the star s0, s1, s2, ..., sk with s0 the center of the star. Label the vertices of the cycle c1, c2, ..., c4k. For 1 ≤ i ≤ k, join si to c(2i-1), c(2i), c(2k+2i-1), c(2k+2i), gt(G) = k+1 and induced circumference is 4k. See counterexample when k = 3.
T	251.	If G is a  simple connected graph such that girth(G) ≥ 5, then gt(G) ≥ 1 + upper_median(G).	definitions   reference
		Feb. 23,2007.  In 2016 Desormeaux and Henning proved this conjecture, see reference.
F	254.	If G is a  simple connected graph, then gt(G) ≥  2*|N(C)|/[maximum of {N(e): e an edge of G}], where C is the set of vertices that are centers of G.	definitions
		Feb. 23,  2007.  August 18, 2009. This counterexample was among the graphs in the newly augmented database of G.pc.  The graph is connected, gt(G) = 3,  |N(C)| = 14, and maximum of {N(e): e an edge of G} = 8.
F	257.	If G is a  simple connected graph, then gt(G) ≥  2*|S|/[maximum of {N(e): e an edge of G}], where S = {v: even(v) = maximum {even(w) :  even(w) = |{u : dist(w,u} is even}|}.	definitions
		Feb. 23,  2007.   Feb. 2009. For m ≥ 8, this counterexample has 2m+3 vertices, gt(G) = 3, |S| = 2m+1 and maximum of {N(e): e an edge of G} = m+3.
F	262.	If G is a tree, then gt(G) ≥  (1/2)*|N(S)|, where S is the set of vertices of degree two.	definitions
		Feb. 23,  2007.  April 23, 2007 B. John found a counterexample; gt(G) = 16 and |N(S)| = 33.
E	263.	If G is a  simple connected graph on an odd number of vertices such that D(G) ≤ n(G)/2, then gt(G) ≥  3.	definitions
		Feb. 23,  2007.
F	264.	If G is a  simple connected graph, then gt(G) ≥  FLOOR[average of {dist(C,v): v in V-C} + average of {dist(B,v): v in V-B}], where B is the set of vertices of maximum eccentricity , C the set of vertices of minimum eccentricity and dist(S,v) = minimum {dist(s,v): s in S}.	definitions
		Feb. 23,  2007.  Feb. 2009. This counterexample has gt(G) = 2, average of {dist(C,v): v in V-C} = 1.5, and average of {dist(B,v): v in V-B} = 2.5.
F	265.	If G is a  simple connected graph such that D(G) ≤  3, then gt(G) ≥  FLOOR[2distavg(B,V)].	definitions
		Feb. 23,  2007.  Sept. 2008: this counterexample was among the 11,716,571 connected 10-vertex graphs that my student H. Hemmati and I added to the database of G.pc,  The counterexample has gt(G) = 5 and distavg(B,V)=3.07. Stringing two of these graphs together increased the difference between te left and right sides of the conjectured inequality to more than one.
F	266.	If G is a  simple connected graph, then gt(G) ≥  FLOOR[distavg(A,V)], where A is the set of minimum degree vertices.	definitions
		Feb. 23,  2007.  Sept. 2008: this counterexample was among the 11,716,571 connected 10-vertex graphs that my student H. Hemmati and I added to the database of G.pc,  The counterexample has gt(G) = 4 and distavg(A,V)=56/11.
F	270.	If G is a  simple connected graph such that D(G) ≤ 3, then gt(G) ≥  (1/2)*|S|, where S = {v: even(v) = maximum {even(w) :  even(w) = |{u : dist(w,u} is even}|}. Sept. 2008: this counterexample was among the 11,716,571 connected 10-vertex graphs that my student H. Hemmati and I added to the database of G.pc,  The counterexample has gt(G) = 4 and every vertex has five vertices at even distance from it.	definitions
		Feb. 23,  2007.
F	272.	If G is a  simple connected graph such that D(G) ≤ n(G)/2, then gt(G) ≥  2*SQRT[distmax(M,V)], where M is the set of vertices of maximum degree.	definitions
		Feb. 23,  2007.  This counterexample was among the 11,716,571 10-vertex graphs that my student H. Hemmati and I added to the database of G.pc, Sept. 2008. The counterexample has gt(G) = 2 and each of three maximum degree vertices is at distance two from some vertex of the graph.
F	273.	If G is a  simple connected C4-free graph, then gt(G) ≥  2^(q-1), where q is the 1st quartile of the degree sequence.	definitions
		Feb. 23,  2007.  July 2009, it occurred to me that there should be a C4-free k-regular graph whose total domination number is less than 2^(k-1), and so I queried McKay's nauty program for 16 vertex C4-free 4-regular graph. It returned one graph. So after computing that the total domination number of this one graph is 6 with Graffiti.pc, indeed there is such a counterexample.
F	274.	If G is a  simple connected graph, then gt(G) ≥  k/median(G), where k is the kth step for a zero in the Havil-Hakimi process.	definitions
		Feb. 23,  2007.  Oct. 2008: this counterexample, was among the 20 million simple connected 11-vertex graphs added to the database of G.pc. This graph has gt(G)=2, k=5 and median(G) = 2.
F	275.	If G is a  simple connected graph such that girth(G) ≥ 6, then gt(G) ≥  δ(G2) -1.	definitions
		Feb. 23,  2007.  DeLaVina, March 15, 2007:see counterexample, for which gt(G)=4 and δ(G2) = 8.
F	276.	If G is a  simple connected graph such that girth(G) ≥ 6, then gt(G) ≥  maximum{horizontal(v) : v a vertex} + 1.	definitions
		Feb. 23,  2007.  DeLaVina, March 1, 2007:see counterexample, for which gt(G)=4 and maximum{horizontal(v) : v a vertex} = 5.
		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 {|EG(D)|: D is a minimum total dominating set} =0.5*radius(G) if and only if gt(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 {|EG(D)|: D is a minimum total dominating set} =0.5*radius(G), then gt(G)=radius(G). May 4, 2007: B. Waller proved the converse.
		Sophie Heuristic
		Sufficient conditions on a simple connected graph G for Total Domination equal to Radius (excluding the invariant from above minimum {|EG(D)|: D is a minimum total dominating set}.
		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	278.	Let G is a simple connected graph with n > 1. maximum {|EG(D)|: D is a minimum total dominating set} =0.5*radius(G) if and only if gt(G)=radius(G).	definitions  reference
		Feb 25, 2007. It is easily proven that if maximum {|EG(D)|: D is a minimum total dominating set} =0.5*radius(G), then gt(G)=radius(G).
		Dalmatian Heuristic
		Upper bounds for Total Domination gt
R	279.	If G is a simple connected graph, then gt(G) ≤ 2*g(G))	definitions
		Mar. 1,  2007.
R	280.	If G is a simple connected graph, then gt(G) ≤ FLOOR[(2/3)*n(G)]	definitions
		Mar. 1,  2007.
F	282.	If G is a simple connected graph such that n(G)> 2, then gt(G) ≤  k+ m(G), where k = nonzero minimum{maximum{k,|Dk|: Dk is the set of vertices of degree k }: k a positive integer}.	definitions
		Mar. 1,  2007. April 19, 2007:R. Pepper noted that the counterexample for 284 is also a counterexample for 282.
F	283.	If G is a simple connected graph such that n(G)> 2, then gt(G) ≤ |N(A)|+ m(G), where A is the set of vertices of minimum degree.	definitions
		Mar. 1,  2007. April 19, 2007:R. Pepper noted that the counterexample for 284 is also a counterexample for 283.
T	285.	If G is a simple connected graph such that n(G)> 2, then gt(G) ≤  m(G)* frequency of  minimum{T(v): v a vertex}, where T(v) is the number of triangles incident to vertex v.	definitions
		Mar. 1,  2007.Oct 2012, Henning and Yeo settled this conjecture in [HY] where they show that f G is a simple connected graph such that n(G)> 2, then gt(G) ≤  m(G) +  frequency of  minimum{T(v): v a vertex} -1, where T(v) is the number of triangles incident to vertex v. [HY] Michael A. Henning, Anders Yeo, Total domination and matching numbers in graphs with all vertices in triangles, Discrete Mathematics, 313 (2013) 174-181.
F	284.	If G is a simple connected graph such that n(G)> 2, then gt(G) ≤  |A|+ m(G), where A is the set of vertices of minimum degree.	definitions
		Mar. 1,  2007. April 16, 2007: with B. Waller and independently R. Pepper: very similar counterexamples were discovered, which belong to a family that demonstrates that the difference between the left and right can be arbitrarily large. See counterexample gt(G) is 14, matching is 12, and there is only one vertex of minimum degree.
F	286.	If G is a simple connected graph such that n(G)> 2, then gt(G) ≤  m(G) + |{T(w) : T(w) = maximum{T(v): v a vertex}}|, where T(v) is the number of triangles incident to vertex v.	definitions
		Mar. 1,  2007. April 16, 2007:  See counterexample gt(G) is 34, matching is 30, and |{T(w) : T(w) = maximum{T(v): v a vertex}}| = 3.
T	288.	If G is a simple connected graph, then gt(G) ≤ p(G) + m(G)	definitions
		Mar. 1,  2007.  B. Waller. To see that this relation is sharp for every value of p(G), let Cm be a cycle on m vertices with the convention that C1 = K1 and C2 = P2. Next, identify each vertex of Cm with the center of a P7. The resulting graph has 7m vertices, gt(G) = 4m,  p(G) = m, and  m(G) = 3m. See the graphs for m = 2 and m = 4. Feb. 2019, in [HW17] this bound is improved to gt(G) ≤ [p(G)-1]/2 + m(G) when the graph has minimum degree is at least 3. [HW17] Michael A. Henning and Kirsti Wash, Matchings, path covers and domination, Discrete Mathematics 340 (2017), no. 1, 3207-3216.
F	289.	If G is a simple connected graph such that n(G)> 2, then gt(G) ≤ p(G) + CEIL[(1/2)*b(G)]	definitions
		Mar. 1,  2007.  April 19, 2007: R. Pepper, see counterexample.
F	292.	If G is a simple connected graph such that n(G)> 2, then gt(G) ≤ k + residue(G), where k is the first step in which a zero appears in the Havil-Hakimi process.	definitions
		Mar. 1,  2007. Feb 2009 see counterexample gt(G) = 12, k = 3,  residue(G) = 8.
F	293.	If G is a simple connected graph, then gt(G) ≤ 2*residue(G)	definitions
		Mar. 1,  2007. April 1, 2007 DeLaVina: Let k = 6m for m >1. Let H be a Kk with the edges of a perfect matching removed (i..e let H be the complement of 3m copies of P2). Now let Gk be the graph derived by amalgamating to each vertex of H a P3 by an endpoint of P3. It is known that gt(Gk) = (2/3)n = 2k = 12m. Since the graph has 3k vertices, k of degree k-1, k of degree 2 and k of degree 1,  residue of Gk is 1 + k/3 + k/2 = 1 + (5/6)k=1 + 5m. Now gt(Gk) - 2*residue(Gk) =  (1/3)k - 2 = 2m -2 > 0 when m >1. See G12. April 13, 2007 with R. Pepper: The following family of graphs demonstrate that for any positive integer k, there exists a graph such that g(G) > k*residue(G). Let m = k(k+1)2. Let H be a Km with the edges of a perfect matching removed. Partition the vertices of H into (k+1)2 blocks of k vertices each. Now let Gk be the graph derived by taking the union of H and the empty graph on (k+1)2 vertices, and joining each isolated vertex to the k vertices of a distinct block. Gk has k(k+1)2 vertices of degree k(k+1)2 -1 and (k+1)2 of degree k. The residue of Gk is  k+2 and g(Gk) = (k+1)2. Now g(Gk) - k*residue(Gk) =  (k+1)2 -k(k+2) > 0.
R	294.	If G is a simple connected graph such that n(G)> 2, then gt(G) ≤ n(G) - D(G) +1	definitions reference
		Mar. 1,  2007. In 1980, Cocknaye, Dawnes, and Hedetniemi proved the following: [CDH] If a graph G has no isolated vertices,  then gt(G) ≤ n(G) - D(G) +1; and if a connected graph G has D(G) < n-1,  then gt(G) ≤ n(G) - D(G).
T	295.	If G is a simple connected graph such that n(G)> 2 and its complement G is traceable, then gt(G) ≤ n(G) - D(G)	definitions reference
		Mar. 1,  2007. April 4, 2007: It is easily seen that if G is traceable, then D(G) ≤  n(G) - 2. So #295 follows from [CDH] If a connected graph G has D(G) < n-1,  then gt(G) ≤ n(G) - D(G)..
R	296.	If G is a simple connected graph such that n(G)> 2, then gt(G) ≤ n(G) - gi(G).	definitions reference
		Mar. 1,  2007. Allan, Laskar, and Hedetniemi proved this in 1984.
T	297.	If G is a simple connected graph such that n(G)> 2, then gt(G) ≤ n(G) - (1/2)*gc(G).	definitions reference
		Mar. 1,  2007. April 6, 2007 Note: A corollary to a result of Kleitman and West in [KW]  is that if  δ(G) ≥  4, then gc(G) ≤ (3/5)n(G) - 2. From the latter and from gt(G) ≤ (2/3)n(G), if δ(G) ≥  4, then gt(G) + (1/2)gc(G) ≤ (2/3)n(G) + (3/10)n(G) - 1 ≤  n(G). Mar. 30, 2007. Stephen Hartke, Qi Liu, Doug West and Hehui Wu.
T	301.	If G is a simple connected graph, then gt(G) ≤  w(G) + frequency of λmax(G))	definitions
		Mar. 1,  2007.
F	303.	If G is a simple connected graph such that n(G)> 2, then gt(G) ≤  degavg(C) + frequency of λmax(G), where C is the set of center vertices.	definitions
		Mar. 1,  2007. Oct. 2008: this counterexample, was among the 20 million simple connected 11-vertex graphs added to the database of G.pc. This graph has gt(G)=6, degavg(C)=3.5 and frequency of λmax(G) = 2.
T	306.	If G is a simple connected graph, then gt(G) ≤ 2*FLOOR[(1/2)*minimum of |NG(e)|]	definitions
		Mar. 1,  2007. April 4, 2007:
F	307.	If G is a simple connected graph such that n(G)> 2 with at least one vertex of even degree, then gt(G) ≤ maxine(G) + maximum of even degrees	definitions
		Mar. 1,  2007. April 20, 2007: Let k be an odd positive integer. Take Kk and to each vertex of Kk amalgamate a P3 be be an endpoint;. maxine is k, maximum even degree is 2 and gt(G) is 2k. See counterexample for k=5.
F	311.	If G is a simple connected graph, then gt(G) ≤ radius(G) + frequency of minimum{K(v): K(v) is the number of K4 incident to a vertex v}	definitions
		Mar. 1,  2007. March 23, 2007. Counterexample.
F	312.	If G is a simple connected graph such that n(G)> 2 with at least one vertex of even degree, then gt(G) ≤ maximum of even degrees + independence number	definitions
		Mar. 1,  2007. April 19, 2007: R. Pepper, see counterexample. April 20, 2007: the counterexample for 307 is also a counterexample.
F	313.	If G is a simple connected graph such that n(G)> 2, then gt(G) ≤ diameter(G) + frequency Tmin(v)	definitions
		Mar. 1,  2007. April 19, 2007: see counterexample. gt(G) is at least 16, diameter is 13, and frequency Tmin(v) is 2.
		Sophie Heuristic
		For totally independence reducible graphs.
		Note: the following conjectures were generated by G.pc's Sophie heuristic.
T	329.	Let G is a simple connected graph with n > 1. The matching number = vertex cover number if and only if  the independence number equals the critical independence number.	definitions
		Dec. 19,  2007. Feb 2008 Craig Larson. He notes that this is equivalent to the independence number equals the critical independence number of graph if and only if the graph is a Konig-Egervary graph. See [CEL2011]. June 2011: in [LM2011] Vadim E. Levit · Eugen Mandrescu proved that G is a Konig-Egervary graph if and only if every maximum independent set is critical. [CEL2011] C.E. Larson, The critical independence number and an independence decomposition, European Journal of Combinatorics, Vol. 32, Issue 2, February 2011, pp. 294-300. [LM2011] V. Levit and E. Mandrescu, Critical Independent Sets and König–Egerváry Graphs, Graphs and Combinatorics, 2011 pp. 1-8.
		Dalmatian Heuristic
		Upper bounds on Total Domination number gt of a Tree
R	330.	If T is a tree on n > 2 vertices, then      γt ≤ κv(T) + number of isolated vertices of T      γt ≤ n(T) - Δ(T) - 1 + 3/rad(T)      γt ≤ ⌈ ((2/3)(n(T)-1))⌉      γt≤ 2γ(T)      γt ≤ n(T) - γ(T)      γt ≤ γ2(T)	definitions
		Feb. 18, 2009. 6 of the 20 upper bounds were obvious rediscoveries, but for completion I list them here. Note, that they appeared on the list implies that the others on the list did not follow from the rediscoveries.
T	331.	If T is a tree on n > 2 vertices, then γt ≤ 2α(T) - number of isolates of <N(S(T))>, where S(T) is the set of support vertices of T	definitions
		Feb. 18, 2009.  Mar 3, 2009 B. Waller. Note: γt ≤ 2α(G) is an exercise for all simple graphs.
T	332.	If T is a tree on n > 2 vertices, then γt ≤ ½[n(T) + number of isolates of <S(T)>], where S(T) is the set of support vertices of T.	definitions reference
		Feb. 18, 2009. April 2009, this conjecture proposes a strengthening of a result of Chellali & Haynes that for a tree γt ≤ ½[n(T) + |S(T)|]. In [DLPW2], we prove the stronger bound that for a non-star tree γt ≤ (n + |S*(T)|)/2 - (L - |S(T)| )/2. [DLPW2] E. DeLaVina, C. E. Larson, R. Pepper, & B. Waller, On total domination and support vertices of a tree, preprint 2009.
T	333.	If T is a tree on n > 2 vertices, then γt ≤ |S(T)| + ⌈ κv(T)/2 ⌉, where S(T) is the set of support vertices of T.	definitions
		Feb. 18, 2009. April 2009, since κv(T) = n(T)-L, this conjecture proposes a strengthening of a result of Chellali & Haynes that for a tree γt ≤ ½[n(T) + |S(T)|]. Note for a non-star tree  |S(T)| +  κv(T)/2  =  |S(T)| +  (n(T)-L)/2   = (n + |S(T)|)/2 - (L - |S(T)|)/2. So this too proposes and improvement  over Chellali & Haynes that for a tree γt ≤ ½[n(T) + |S(T)|]. In [DLPW2], we prove the stronger bound that for a non-star tree γt ≤ (n + |S*(T)|)/2 - (L - |S(T)| )/2. [DLPW2] E. DeLaVina, C. E. Larson, R. Pepper, & B. Waller, On total domination and support vertices of a tree, preprint 2009.
T	334.	If T is a tree on n > 2 vertices, then γt ≤ number of isolates of <S(T)> + vc(T), where S(T) is the set of support vertices of T.	definitions
		Feb. 18, 2009. July 2009. [DLPW2] E. DeLaVina, C. E. Larson, R. Pepper, & B. Waller, On total domination and support vertices of a tree, preprint 2009.
F	335.	If T is a tree on n > 2 vertices with degree 2 vertices,  then γt ≤ number of isolates of <S(T)> + γ(T) * order of a largest component of <D2>, where S(T) is the set of support vertices of T and D2={v| deg(v) = 2}	definitions
		Feb. 18, 2009. May 2009, P. Feit's 34-vertex counterexample to conjecture 240 is also a counterexample to 335. Note γt(T)= 14, γ(T)=13 and all degree 2 vertices are isolates.
F	336.	If T is a tree on n > 2 vertices,  then γt ≤  number of isolates of <S(T)> + γ(T) + |EB(T)| , where EB(T) = {(uv}=e ∈E(T): deg(u)=deg(v)} called here the balanced edges of the graph.	definitions
		Feb. 18, 2009. May 2009, a larger version of P. Feit's 34-vertex counterexample to conjecture 240 is also a counterexample to 336. Note γt(T)= 18, γ(T)=17 and no edges are balanced.
F	337.	If T is a tree on n > 2 vertices,  then γt ≤  |S(T)|  + ⌈ half of nonzero minimum of maximum{k, |Dk(T)|}⌉, where S(T) is the set of support vertices of T and Dk(T) = {v: deg(v) =k}	definitions
		Feb. 18, 2009. May 2009, there must have been an issue in my interpretation of the conjecture or a computational error, since there is a 9 vertex counterexample.
F	338.	If T is a tree on n > 2 vertices,  then γt ≤ diam(T)* ⌈|S(T)|/3⌉	definitions
		Feb. 18, 2009. May 2009, there must have been an issue in my interpretation of the conjecture or a computational error, since there is an 11 vertex counterexample.
F	339.	If T is a tree on n > 2 vertices,  then γt ≤ ecc(B) + modemax(T)* γ(T)	definitions
		Feb. 18, 2009. May 2009, this counterexample has γt(T)= 10, ecc(B)=3, γ(T) = 6 and modemax(T) = 1.
		Dalmatian Heuristic
		Lower bounds on Total Domination number gt of a Tree
R	345.	If T is a tree on n > 2 vertices, then        γT(T) ≥ γ(T)               γT(T) ≥ rad(T)       γT(T) ≥ 1+ 2⁄3*ecc(B)   (conj 233)       γT(T) ≥  ⌈ 1 + ½κv⌉   (Chellali & Haynes [CH2])	definitions
		Feb. 18, 2009. Conj 240 from a previous run was repeated. [CH2] M. Chellali and T. W. Haynes, A note on the total domination of a tree, J. Combin. Math. Combin. Comput., 58(2006), 189-193.
F	346.	If T is a tree on n > 2 vertices,  then  γT(T) ≥  half of order of a largest component of <D2(T)> + -1 + number of components of <N(D2(T)) - D2(T)>, where D2={v| deg(v) = 2}.	definitions
		Feb. 18, 2009. This is sometimes an improvement over conjecture 240. Note: Although not for trees, there is the following result on involving γT(G) and D2(G). Lam & Wei proved that for G an n vertex graph with minimum degree at least two, γT(G) ≤ n/2 if the length of the longest paths in the <D2(T)> is at most one. [LW] Lam, P and Wei, B, On the total domination number of graphs,  UTILITAS MATHEMATICA, 72: 223-240 MAR 2007. May 2009, P. Feit discovered a 34-vertex counterexample belonging to a family of graphs that demonstrates that the left and right can be arbitrarily far apart. May 2009, inspired by this conjecture [DLPW] proved that  if G is a tree, then gt(G) ≥  number of components(< V(T) - S>) + p2/2 - 1, where S is the set of vertices of degree two and p2 is the order of a largest component induced by S. [DLPW] DeLaVina, Larson, Pepper, and Waller, Graffiti.pc on the total domination number of a tree, preprint 2009.
T	347.	If T is a tree on n > 2 vertices,  then  γT(T) ≥  half of order of a largest component of <D2(T)> + -1 +|S(T)|, where D2={v| deg(v) = 2} and S(T) is the set of support vertices of T.	definitions
		Feb. 18, 2009. 2012 Hongxing Jiang.
T	349.	If T is a tree on n>2 vertices, then γT(T) ≥  rad(T) -1 + number of components of <N(D2(T)) ∪ D2(T) >, where D2={v| deg(v) = 2}.	definitions
		Feb. 18, 2009. 2012 Hongxing Jiang.
T	350.	If T is a tree on n>2 vertices, then γT(T) ≥   ½[diam(T) + number of components of <N(D2(T)) ∪ D2(T) >], where D2={v| deg(v) = 2}.	definitions
		Feb. 18, 2009. 2012 Hongxing Jiang.
T	355.	If T is a tree on n>2 vertices, then γT(T) ≥  κv/(ecc(C) - 1), where C is the center of T.	definitions
		Feb. 18, 2009. Feb. 2009: R. Pepper. Note: if ecc(C) > 2, then this follows from γT(T) ≥  ⌈ 1 + ½*κv⌉   (Chellali & Haynes [CH2]). So it was enough to prove this for ecc(C) = 2.
T	357.	If T is a tree on n>2 vertices, then γT(T) ≥  ecc(C) + |N(B)| -1 , where C is the center of T and B is the boundary of T.	definitions
		Feb. 18, 2009. Feb. 2009: DPW.
T	366.	If T is a tree on n>2 vertices, then γT(T) ≥  2⁄3 *dd(T).	definitions
		Feb. 18, 2009. Feb. 2009. DPW
F	368.	If T is a tree on n>2 vertices, then γT(T) ≥  1 + k, where k corresponds to the kth step for a zero in the Havil-Hakimi process of a degree sequence.	definitions
		Feb. 18, 2009. April 27, 2009: Pepper & Waller see counterexample for which γT(T) = 8 and k = 8.
T	370.	If T is a tree on n>2 vertices, then γT(T) ≥  2μ'(T)/Δ(T), where μ(G) denotes the matching number of G, and we define μ'(T) = maximumv∈V{ deg(v) + μ(<V(T) - N(v)>).	definitions
		Feb. 18, 2009. 2012 Hongxing Jiang.
T	371.	If T is a tree on n>2 vertices, then γT(T) ≥  2vc(T)/Σ(T)	definitions
		Feb. 18, 2009. August 2009, if  Σ(T)=2 or Σ(T)=1, then T is a path or star, and the relation clearly holds. So assume Σ(T) ≥ 3. In [DLPW2], we prove that γT(T) ≥  vc(T) - (k-1) where k is the number of components of the subgraph induced by a minimum total dominating set. Since k £ γT(T) /2, -k ≥ -γT(T)/2. Now by the above  γT(T) ≥  vc(T) - (k-1) ≥  vc(T) -γT(T)/2 +1, which yields γT(T) ≥  (2/3)(vc(T) +1). Since we can assume that Σ(T)≥ 3, the conjecture follows.   [DLPW2] DeLaVina, Larson, Pepper, and Waller, On total domination and support vertices of a tree, preprint 2009.
		Dalmatian Heuristic
		Upper bounds on 2-domination number g2 of a connected graph
T	382a.	If G is a connected graph n > 2 vertices, then        γ2 ≤ 2a-ac.	definitions
		Jan. 2010. DeLaVina & Hemmati. It is easy to see that γ2 ≤ 2a, and the independence number is not an upper bound for the 2-domination number; so we note the corollary, if G has a unique maximum independent set, then  γ2 ≤ a.
F	382f.	Let G be a connected graph n > 2 vertices.        γ2 ≤ a + |A|*ck4., where A is the set of vertices that achieve the minimum of local independence and ck4 is the number of vertices incident to the most K4 subgraphs.	definitions
		Jan. 2010. DeLaVina March 2010: the counterexample has γ2 = 17, a = 13, l=1 and ck4 =1
T	383a.	If G is a connected graph n > 2 vertices, then        γ2 ≤ n - a (G[A]), where A is the set of non-minimum degree vertices.	definitions
		Jan. 2010. DPW. This together with conjecture 384 led us to the stronger statement. If G is a connected graph n > 2 vertices, then  γ2 ≤ n - a (G[A]), where A is the set of non-pendant vertices.
T	383b.	If G is a connected graph n > 2 vertices, then           γ2 ≤ n - a + |P|, where P is the set of pendants (i.e. vertices of degree 1).	definitions
		Jan. 2010. DPW. This together with conjecture 384 led us to the stronger statement. If G is a connected graph n > 2 vertices, then  γ2 ≤ n - a (G[A]), where A is the set of pendant  vertices.
T	384.	If G is a connected graph on n > 2 vertices with kv cut vertices, then           γ2 ≤ FLOOR(n - kv/2).	definitions
		Jan. 2010. DPW.
T	385a.	If G is a connected graph n > 2, then           γ2 ≤ n - D(G[N(M)-M]).    where M is the set of maximum degree vertices.	definitions
		Jan. 2010. DeLaVina, Feb 2010. A more general  statement follows, namely, If G is a connected graph n > 2, then γ2 ≤ n - D(G[N(S)-S]). where S is any subset of vertices .
T	385b.	If G is a connected graph n > 2, then           γ2 ≤ n - D(G[N(A)-A]).    where A is the set of minimum degree vertices.	definitions
		Jan. 2010. DeLaVina, Feb 2010. A more general  statement follows, namely, If G is a connected graph n > 2, then γ2 ≤ n - D(G[N(S)-S]). where S is any subset of vertices .
T	385c.	If G is a connected graph n > 2, then           γ2 ≤ n - D(G[N(B)-B]).    where B is the set of periphery vertices.	definitions
		Jan. 2010. DeLaVina, Feb 2010. A more general  statement follows, namely, If G is a connected graph n > 2, then γ2 ≤ n - D(G[N(S)-S]). where S is any subset of vertices .
T	386.	If G is a connected graph on n > 2, then           γ2 ≤ n - maximum{|N(u) Ç N(u)| : u and v distinct vertices of G }.	definitions
		Jan. 2010. DeLaVina Feb. 2010
T	388.	If G is a connected graph on n > 2 vertices, then           γ2 ≤ (n + a (G[A]))/2, where A is the set vertices of degree at most two.	definitions
		Jan. 2010. March 11, 2010 DeLaVina, Pepper & Vaughan.
F	389.	If G is a connected graph on n > 2 vertices, then           γ2 ≤ q*|M| + a (G[A]), where A is the set vertices of degree at most two, M is the set of vertices of modemin degree and q is the 1st quartile degree .	definitions
		Jan. 2010. DeLaVina March 2010: the counterexample has γ2 = 9, q = 1, |M|= 4 and a (G[A]) = 4
T	390.	If G is a connected graph on n > 2 vertices, then           γ2 ≤ ≤ p(G) + m(G), where A is the set vertices of degree at most two.	definitions
		Jan. 2010. Feb. 2010 DeLaVina, Pepper & Waller.
		Dalmatian Heuristic
		Upper bounds on 2-domination number g2 of a connected graph
T	382a.	If G is a connected graph n > 2 vertices, then        γ2 ≤ 2a-ac.	definitions
		Jan. 2010. DeLaVina & Hemmati. It is easy to see that γ2 ≤ 2a, and the independence number is not an upper bound for the 2-domination number; so we note the corollary, if G has a unique maximum independent set, then  γ2 ≤ a. In [DLPW3] we simplified the proof. [DLPW3] DeLaVina, Larson, Pepper, and Waller, Graffiti.pc on the 2-domination number of a tree, preprint 2009.
F	382f.	Let G be a connected graph n > 2 vertices.        γ2 ≤ a + |A|*ck4., where A is the set of vertices that achieve the minimum of local independence and ck4 is the number of vertices incident to the most K4 subgraphs.	definitions
		Jan. 2010. DeLaVina March 2010: the counterexample has γ2 = 17, a = 13, l=1 and ck4 =1
T	383a.	If G is a connected graph n > 2 vertices, then        γ2 ≤ n - a (G[A]), where A is the set of non-minimum degree vertices.	definitions
		Jan. 2010. Feb. 2010 DPW. This together with conjecture 384 led us to the stronger statement. If G is a connected graph n > 2 vertices, then  γ2 ≤ n - a (G[A]), where A is the set of non-pendant vertices. Pepper later generalized this & 383b to If G is a connected graph n > 2 vertices, then  γk ≤ n - a (G[Ak]), where Ak is the set of vertices of degree at least k. (see [DLPW3])
T	383b.	If G is a connected graph n > 2 vertices, then           γ2 ≤ n - a + |P|, where P is the set of pendants (i.e. vertices of degree 1).	definitions
		Jan. 2010. DPW. This together with conjecture 384 led us to the stronger statement. If G is a connected graph n > 2 vertices, then  γ2 ≤ n - a (G[A]), where A is the set of non-pendant vertices. Pepper later generalized this and 383a to If G is a connected graph n > 2 vertices, then  γk ≤ n - a (G[Ak]), where Ak is the set of vertices of degree at least k. (see [DLPW3])
T	384a.	If G is a connected graph on n > 2 vertices and kv cut vertices, then           γ2 ≤ FLOOR(n - kv/2).	definitions
		Jan. 2010. March 2010 (see [DLPW3])..
E	385a.	If G is a connected graph n > 2, then           γ2 ≤ n - D(G[N(M)-M]).    where M is the set of maximum degree vertices.	definitions
		Jan. 2010. DeLaVina, Feb 2010. Inspired by 385a,b&c, a more general  statement follows, namely, If G is a connected graph n > 2, then γ2 ≤ n - D(G[N(S)-S]). where S is any subset of vertices .
E	385b.	If G is a connected graph n > 2, then           γ2 ≤ n - D(G[N(Ad )-Ad ]).    where Ad  is the set of minimum degree vertices.	definitions
		Jan. 2010. DeLaVina, Feb 2010. Inspired by 385a,b&c, a more general  statement follows, namely, If G is a connected graph n > 2, then γ2 ≤ n - D(G[N(S)-S]). where S is any subset of vertices .
E	385c.	If G is a connected graph n > 2, then           γ2 ≤ n - D(G[N(B)-B]).    where B is the set of periphery vertices.	definitions
		Jan. 2010. DeLaVina, Feb 2010. Inspired by 385a,b&c, a more general  statement follows, namely, If G is a connected graph n > 2, then γ2 ≤ n - D(G[N(S)-S]). where S is any subset of vertices .
E	386a.	If G is a connected graph on n > 2, then           γ2 ≤ n - maximum{|N(u) Ç N(u)| : u and v distinct vertices of G }.	definitions
		Jan. 2010. DeLaVina Feb. 2010
E	386b.	If G is a connected graph on n > 2, then           γ2 ≤ 2(n - S(G)).    where S(G) is the 2nd largest entry of the ordered (non-decreasing) degree sequence.	definitions
		Jan. 2010. March 2010 DLPW.
T	388.	If G is a connected graph on n > 2 vertices, then           γ2 ≤ (n + a (G[A2 ]))/2, where A2  is the set vertices of degree at most two.	definitions
		Jan. 2010. March 11, 2010 DeLaVina, Pepper & Vaughan.  May 18, 2010. M. Henning & W. Goddard communicated an independent proof of this conjecture.
F	389b.	If G is a connected graph on n > 2 vertices, then           γ2 ≤ q*|M| + a (G[A2]), where A2 is the set vertices of degree at most two, M is the set of vertices of modemin degree and q is the 1st quartile degree .	definitions
		Jan. 2010. DeLaVina March 2010: the counterexample has γ2 = 9, q = 1, |M|= 4 and a (G[A]) = 4.
T	390.	If G is a connected graph on n > 2 vertices, then           γ2 ≤ p(G) + m(G).	definitions
		Jan. 2010. Feb. 2010 DeLaVina, Pepper & Waller see [DLPW3].
T	392a.	If G is a connected graph on n > 2 vertices, then           γ2 ≤  m(G[A3]) + |V-A3|, where A3 is the set vertices of degree at least three.	definitions
		Jan. 2010.  March 11, 2010. DeLaVina, Pepper & Vaughan. Our argument generalized to γk ≤  m(G[A2k-1]) + |V-A2k-1|, where A2k-1 is the set vertices of degree at least 2k-1. May 18, 2010. M. Henning & W. Goddard communicated another independent proof of this conjecture and its generalization. Note: In an effort to organize conjectures, I've grouped all involving matching and small degrees under 392.
T	397a.	If G is a connected graph on n > 2 vertices, then          γ2 ≤  |V - N(P)| + |{v : |N(v) Ç [V - N(P)] | = 1}| , where P is the set of pendants.	definitions
		Jan. 2010. March 20101. DeLaVina Proof: If minimum degree is greater than one, then this follows trivially. So assume P is not empty. Let D' = {v : | N(v) Ç [V - N(P)]| =1}. Then V-N(P) is a 2-dominating set unless some vertex v in N(P) is adjacent to only one vertex in V-N(P), but then v is in D'. Thus, [V-N(P)] È  D'  is a 2-dominating set. qed. [DLPW3]
T	397b	If G is a connected graph on n > 2 vertices, then          γ2 ≤  |V - N(P)| + m(G[N(P)]) , where P is the set of pendants.	definitions
		Jan. 2010. April 2010 [DLPW3].
		Dalmatian Heuristic
		Bounds on sets related to H (the union of all maximum critical independent sets) for trees.
T	403.	Let G be a tree on n > 2 vertices and H the union of all maximum critical independent sets of G. Then number of isolates(G[H])  = ac(G)	definitions
		Jan. 2010. Larson proved that this identity holds for Konig-Egarvy graphs.
		Dalmatian Heuristic
		Upper Bounds on the order of H (the union of all maximum critical independent sets) for connected graphs.
T	408.	Let G be a connected graph on n > 2 vertices and H the union of all maximum critical independent sets of G. Then |H| ≤ 2a(G[V-N(P)]) - ac(G).	definitions
		June 2010. June 2010, DeLaVina&Larson, note that a(G[V-N(P)]) = a(G) unless G has a component of P2, thus the conjecture is equivalent to |H| ≤ 2a(G) - ac(G), which we prove and also characterize that the graphs for which equality holds are Konig-Egervary graphs.
T	409a.	Let G be a connected graph on n > 2 vertices; let M be the set of maximum degree vertices and H the union of all maximum critical independent sets of G. If D(G) > n/2,  |H| ≤ n-|M|.	definitions
		June 2010. June 2010, DeLaVina&Larson, proved the stronger statement that for M be the set of whose degree is greater than n/2, we have  |H| ≤ n-|M|. which settles 409b & 409c also.
T	409b.	Let G be a connected graph on n > 2 vertices and H the union of all maximum critical independent sets of G. If d(G) > n/2,  |H| =0.	definitions
		June 2010. June 2010, DeLaVina&Larson, proved the stronger statement that for M be the set of whose degree is greater than n/2, we have  |H| ≤ n-|M|. which settles 409a & 409c  also.
T	409c.	Let G be a connected graph on 6 > n > 2; let A2 be  vertices of degree less than or equal to 2, and H the union of all maximum critical independent sets of G. Then |H| ≤ |A2|.	definitions
		June 2010. June 2010, DeLaVina&Larson, proved the stronger statement that for M be the set of whose degree is greater than n/2, we have  |H| ≤ n-|M|. which settles 409a & 409b also.
		Dalmatian Heuristic
		Lower Bounds on the order of H (the union of all maximum critical independent sets) for connected graphs.
T	411.	Let G be a connected graph on n > 2 vertices, P the set of pendant vertices and H the union of all maximum critical independent sets of G. Then |H| ≥ isolates(G[V-N(P)]) + peN(V-N(P)) .	definitions
		June 2010. June 2010, with Larson.
T	412c.	Let G be a connected bipartite graph on n > 2 vertices and H the union of all maximum critical independent sets of G. Then |H| ≥ a(G).	definitions
		June 2010. This follows for the larger class of Konig-Egervary graphs because maximum critical independent sets are maximum independent sets.
F	414.	Let G be a connected graph on n > 2 vertices and H the union of all maximum critical independent sets of G. Then |H| ≥ ac(G)*FLOOR[1/lower median].	definitions
		June 2010. August 2010 C. Larson. See counterexample.
		Dalmatian Heuristic
		Lower Bounds on the independent domination for connected graphs.
R	417.	Let G be a connected graph on n > 3 vertices. Then i(G) £ n(G) - maximum{deg(v) + m(G[V-N(v)])  : v in V(G) }	definitions
		Dec. 8 2010.  M. Blidia, M. Chellali, F. Maffray, Extremal graphs for a new upper bound on domination parameters in graphs, Discrete Mathematics, 306 (2006), 2314-2326.
T	418a.	Let G be a connected graph on n > 3 vertices, A the set of minimum degree vertices of G. Then i(G) £ a(G[V-A]) + |A| -1.	definitions
		Dec. 8 2010. W. Goddard. May 2012, just noticed that this is similar to G.pc's #451.
F	418d.	Let G be a connected graph on n > 3 vertices, A the set of minimum degree vertices, M the maximum degree vertices of G, and K_4(G) the vertices incident to the most K4. Then i(G) £ |A| *|K4|G)| + g(G[V-M])	definitions
		Dec. 8 2010.  Jan 2011 DeLaVina see counterexample
F	418e.	Let G be a connected graph on n > 3 vertices, A the set of minimum degree vertices, and D the set of neighbor dominators. Then i(G) £  |A|  +  diameter(G) + |E(D, V-D)|.	definitions
		Dec. 8 2010.  Jan 2011 counterexample for 424 also refuted 418e.
T	419a.	Let G be a connected graph on n > 3 vertices, A the set of minimum degree vertices of G. Then i(G) £  a(G) - 1/(w(G[N[Ac]]) -1 ).	definitions
		Dec. 8 2010. For this and 419b if the core of G is empty then the right hand side is a(G) +1 and so the inequality follows trivially. If the core of G is not empty, then  both w(G[N[Ac]]) and r(G[N[Ac]]) are both at least two, and the smallest that the right hand side can be is a(G) - 1. Dec, 2010 Bill Waller proved that For a connected graph G, if the core of G is non-empty, then i(G) £ a(G) - 1.
T	419b.	Let G be a connected graph on n > 3 vertices, A the set of minimum degree vertices of G. Then i(G) £  a(G) - 1/(r(G[N[Ac]]) -1 ).	definitions
		Dec. 8 2010. Dec 2010 Bill Waller (see above).
T	420a.	Let G be a connected graph on n > 3 vertices, S the set of support vertices of G. Then i(G) £  a(G[V(G)-N(S)]) + 2*Floor[0.5|E(G[N(S)])|] ).	definitions
		Dec. 8 2010. Dec 2010Wayne Goddard proved that i(G) £  a(G[V(G)-N(S)]) + |E(G[N(S)])| (so there is still the question of a slight improvement when |E(G[N(S)])| is odd.)
R	421a.	Let G be a connected graph on n > 3 vertices. Then i(G) £  lmax(G) (gt(G)-1).	definitions
		Dec. 8 2010. DeLaVina If G is a graph on  n > 1 vertices i(G) £  1 + (lmax(G)-1) (g(G)-1).
F	421d.	Let G be a connected graph on n > 3 vertices and M the vertices of maximum degree. Then i(G) £  FLOOR[0.5g2(G)]a(G[N(M)]).	definitions
		Dec. 8 2010. Pepper Jan. 26, 2011 see counterexample
F	424.	Let G be a connected graph on n > 3 vertices, M its set of maximum degree vertices and D the set of vertices each of whose closed neighborhood contains the closed neighborhood of some other vertex. Then i(G) £  |E(D,V-D)|+ a(G[M]) + g(G[V-M]).	definitions
		Dec. 8 2010. Jan 2011 DeLaVina see counterexample
F	425a.	Let G be a connected graph on n > 3 vertices, M its set of maximum degree vertices and D the set of vertices each of whose closed neighborhood contains the closed neighborhood of some other vertex. Then i(G) £  |Tmin(G)|+ isol(G[B]) + g(G[V-N(P)]).	definitions
		Dec. 8 2010. Jan 2011 counterexample for 424 also refuted 425a.
F	425b.	Let G be a connected graph on n > 3 vertices and A the core of G. Then i(G) £  2|Tmin(G)|(2+c(G[N[A]])), where c(G[N[A]]) is the order of a largest component of the subgraph induced by N[A].	definitions
		Dec. 8 2010. Jan 2011 counterexample for 424 also refuted 425b.
F	425c.	Let G be a connected graph on n > 3 vertices and M the vertices of maximum local independence of G. Then i(G) £  2|Tmin(G)|FLOOR[0.5|N[M]|].	definitions
		Dec. 8 2010. Jan 2011 DeLaVina see counterexample
F	428.	Let G be a connected graph on n > 3 vertices and M the vertices of maximum degree. Then i(G) £  g(G[V-N(P)]) + (n mod D(G)) + x, where x = the number of vertices with  minimum{deg(v) + m(G[V-N(v)])  : v in V(G) }.	definitions
		Dec. 8 2010. Jan 2011 the counterexample for 418d also refuted this conjecture.
F	429.	Let G be a connected graph on n > 3 vertices and M the vertices of maximum degree and Davg(P) average of distance from each periphery vertex of graph. Then i(G) £  Davg(P)*(a(G[N(M)]) + 1)	definitions
		Dec. 8 2010. Jan 2011 the counterexample for 421d also refuted this conjecture.
		Dalmatian Heuristic
		Upper Bounds on the 2-independence number for connected graphs.
T	436a.	Let G be a connected graph on n > 3 vertices. Then a2(G)£ WP(G) + c(D), where WP(G) is the Welsh-Powell invariant of the complement graph and c(D) is the number of components of the subgraph induced by the set of neighbor dominators of G.	definitions
		Jan. 2012. May 2012, in [DP12] we proved that ak ≤ WP(G) + k - 1 and that a2 ≤ WP(G) whenever the graph G has no neighbor dominators. [DP12] E. DeLaVina, R. Pepper, Graffiti.pc on the 2-independence number of a graph, preprint 2012.
T	436b.	Let G be a connected graph on n > 3 vertices. Then a2(G)£ WP(G) + FLOOR[3/radius], where WP(G) is the Welsh-Powell invariant of the complement graph.	definitions
		Jan. 2012. *May 2012, in [DP12] we proved that ak ≤ WP(G) + k-1, so here it simply remains to settle a2 ≤ WP(G) whenever the graph G has has radius at least 4. May 2013, DeLaVina. [DP12] E. DeLaVina, R. Pepper, Graffiti.pc on the 2-independence number of a graph, preprint 2012.
T	437.	Let G be a connected graph on n > 3 vertices. Then a2(G)£ CEILING[(2/3)n]*p(G).	definitions
		Jan. 2012. May 2012, Pepper: if the path covering number of G is greater than 1 then the conjecture is trivially true. Now if p(G) =1, that is the graph has a Hamiltonian path, then since  the a2(Pn) = CEILING[(2/3)n] the conjecture follows.
T	440.	Let G be a connected graph on n > 3 vertices. Then a2(G)£  n - g(G[V-A]), where A is the set of minimum degree vertices of G.	definitions
		Jan. 2012.  May 2012, Pepper and Waller.
T	441a.	Let G be a connected graph on n > 3 vertices. Then a2(G)£  n - m(G[N(Ac)]) -1, where Ac is the intersection of all maximum independent sets  of G.	definitions
		Jan. 2012.   April 2013, DeLaVina & Lazo.
T	441b.	Let G be a connected graph on n > 3 vertices. Then a2(G)£  n - d(G[N(Ac)]) -1, where Ac is the intersection of all maximum independent sets  of G.	definitions
		Jan. 2012.   April 2013, DeLaVina & Lazo.
T	445a.	Let G be a connected graph on n > 3 vertices. Then a2(G)£ a3(G) - D(G[H2]) + 1, where H2 is the set of vertices of degree at most 2 in G.	definitions
		Jan. 2012.   April 2012,DeLaVina & Pepper. [DP12] E. DeLaVina, R. Pepper, Graffiti.pc on the k-independence number of a graph, preprint 2012.
F	445b.	Let G be a connected graph on n > 3 vertices. Then a2(G)£ a3(G) - FLOOR[c(G[H3]/3], where H3 is the set of vertices of degree at least 3 in G.	definitions
		Jan. 2012.   April 2012, DeLaVina & Pepper. Take three copies of K(4,4) linked together by one edge between the first and second copy and one edge between the second and third, and then subdivide the linked edges a2(G)= a3(G) = 14, but c(G[H3] = 3.
F	447a.	Let G be a connected graph on n > 3 vertices. Then a2(G)£ A + FLOOR[g3 /3], where A is the annihilation number and g3 is the3-domination number of G.	definitions
		Jan. 2012.    Feb. 2013, DPW see a counterexample.
F	447b.	Let G be a connected graph on n > 3 vertices. Then a2(G)£ A + FLOOR[R/2], where A is the annihilation number and R is the residue.	definitions
		Jan. 2012.   Feb. 2013, DPW see a counterexample.
T	451.	Let G be a connected graph on n > 3 vertices. Then a2(G)£ 2a(V-A) + |A|, where AÍV.	definitions
		Jan. 2012.  Note that the program made several conjectures of this exact form with a variety of different sets, so I chose to report the stronger conjecture and indeed it is true. Jan 2012, the more general statement  ak(G)£ ka(V-A) + |A|, where AÍV is proven in [DP12]. Note that this is similar to G.pc's #418a. [DP12] E. DeLaVina, R. Pepper, Graffiti.pc on the k-independence number of a graph, preprint 2012.
		Dalmatian Heuristic
		Lower Bounds on the 2-independence number for connected graphs.
T	451.	Let G be a connected graph on n > 3 vertices. Then a2(G)£ 2a(V-A) + |A|, where AÍV.	definitions
		Jan. 2012.  Note that the program made several conjectures of this exact form with a variety of different sets, so I chose to report the stronger conjecture and indeed it is true. Jan 2012, the more general statement  ak(G)£ ka(V-A) + |A|, where AÍV is proven in [DP12]. Note that this is similar to G.pc's #418a. [DP12] E. DeLaVina, R. Pepper, Graffiti.pc on the k-independence number of a graph, preprint 2012.
T	452.	Let G be a connected graph on n > 3 vertices. Then a2(G)£ 2a(G) - m(G[S]), where S is the set of support vertices of G.	definitions
		Jan. 2012.   June 2013, Bill Kinnersly settled this during my talk at CanaDAM 2013 in St John's.
		Dalmatian Heuristic
		Lower Bounds on the 2-independence number for connected graphs.
T	453.	Let G be a connected graph on \( n \ge 3 \) vertices, and \( H_{n/2} \) the vertices of degree at most \( \frac{n}{2} \). Then \( \alpha_2(G) \ge 2c(G[H_{n/2}]) - isol(G[H_{n/2}]) \), where \( c(G[H_{n/2}]) \) is the number of components of the subgraph induced by  \( H_{n/2} \). In this run, the program made the similar conjecture for many different sets.	definitions
		Jan. 2012. April 2012, DeLaVina & Pepper. It isn't difficult to see that this relation holds for any subset of the vertices not only \( H_{n/2} \). [DP12] E. DeLaVina, R. Pepper, Graffiti.pc on the k-independence number of a graph, preprint 2012.
T	454.	Let G be a connected graph on \( n \ge 3 \) vertices, and \( D \) the set of neighbor-dominators. Then \( \alpha_2(G) \ge 2c(G[D])  \)	definitions
		Jan. 2012. April 2012, DeLaVina & Pepper. [DP12] E. DeLaVina, R. Pepper, Graffiti.pc on the k-independence number of a graph, preprint 2012.
E	455.	Let G be a connected graph on \( n \ge 3 \) vertices, and \( H_2 \) the set of degree two vertices. Then \( \alpha_2(G) \ge \rho(G[V \setminus H_2]) - \lfloor \frac{1}{3} \rho(G[V \setminus H_2]) \rfloor \), where \( \rho(G[V \setminus H_2]) \) is the path covering number of the subgraph induced by the vertices that are not of degree two. In this run, the program made the similar conjecture for many different sets.	definitions
		Jan. 2012. April 2012, DeLaVina & Pepper. For any induced path the 2-independence number is about \( 2/3 \) the order of the path.
R	456.	Let G be a connected graph on \( n \ge 3 \) vertices. Then \( \alpha_2(G) \ge \alpha(G) \).	definitions
		Jan. 2012.
T	457.	Let G be a connected graph on \( n \ge 3 \) vertices. Then \( \alpha_2(G) \ge \alpha_c(G) + 2c(G[N[V-A_c]]) \), where \( A_c \) is the core of G.	definitions
		Jan. 2012. June 2013, DeLaVina
T	458.	Let G be a connected graph on \( n \ge 3 \) vertices. Then \( \alpha_2(G) \ge 2\alpha(G) - |V-D| \), where D is the set of neighbor-dominators.	definitions
		Jan. 2012. April 2012, DeLaVina & Pepper. [DP12] E. DeLaVina, R. Pepper, Graffiti.pc on the \( k \)-independence number of a graph, preprint 2012
T	459.	Let G be a connected graph on \( n \ge 3 \) vertices. Then \( \alpha_2(G) \ge |A| - |E(G[A])/2| \), where A is any subset of the vertices.	definitions
		Jan. 2012. The program conjecture this for a variety of sets so I propose the stronger conjecture. June 2013, Pepper wrote the following: "Let R_k, CT_k, a_k be the k-Residue, k-Caro-Tuza, and k-independence respectively. Also, let n be order and m be size.  Theorem(s): (Jelen 1999)  a_k >= R_k >= CT_k Observation: (Jelen 1999) For k < D, where D means max degree, CT_k = n – m/k  Theorem: (Pepper 2004) For k >= D, where D means max degree, R_k = n – m/k  Corollaries:  a_k >= R_k >= n – m/k  Randy and G.pc Conjecture: a_k >= |A| - |E(G[A])|/k  Proof: Let A be a set of vertices in graph G.  Then a_k(G) >= a_k([A]) >= R_k([A]) >= n([A]) – m([A])/k = |A| - |E(G[A])|/k."