Written on the Wall II

Ermelinda DeLaVina (delavinae@uhd.edu)

		Lower bounds for maximum number of leaves over all spanning trees, 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.
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.

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

R	31a.	If G is a simple connected graph, then path(G) ≥ 2ecc(Centers) + 1	definitions  reference
		Summer 2003. This is offers an improvement over Chung's Theorem see wowII #31, when rad(G) =  ecc(centers). June 2005, Waller noticed that conjecture follows from a Theorem of Basco and Tuza (see reference).
R	35.	If G is a simple connected graph, then path(G) ≥ 1 + diam(G)	definitions  reference
		July 15, 2003. This could also have been labeled an exercise, but since it was noted in the cited reference we include it here as a rediscovery.

		Lower bounds on the forest number of simple connected graphs, f(G).
	Note:	Clearly b(G)  ≥  f(G)  ≥ path(G), and note that f(G) and path(G) were not available to the program when lower bounds for b(G) were generated.
E	37.	If G is a simple connected graph, then f(G) ≥ path(G)	definitions
		Mar 05, 2004.
R	47.	If G is a simple connected graph, then f(G) ≥ diam(G) + 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.
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"
		2nd run on Lower bounds on the forest number of simple connected graphs, f(G).
	Note:	Clearly b(G)  ≥  f(G)  ≥ tree(G) ≥ path(G), and note that this (for the second run) time b(G), tree(G) and path(G) were available to the program when lower bounds for f(G) were generated;  Also for the second run for forest should reflect the counterexamples listed above and now also includes the local independence invariants and the domination number.  conjectures 39, 42, 47
E	57.	If G is a simple connected graph, then f(G) ≥ tree(G)	definitions
		Mar 25, 2004.
T	67.	If G is a simple connected graph, then f(G) ≥ diam(G) + maximum of l(v) -2	definitions reference
		Mar 25, 2004. This is related to the discussion of conjecture 16. Mar 27, 2004. DeLaVina and Waller.
		Lower bounds on the tree number of simple connected graphs, tree(G).
	Note:	Clearly b(G)  ≥  f(G)  ≥ tree(G) ≥ path(G).
E	68.	If G is a simple connected graph, then tree(G) ≥ path(G)	definitions
		Apr 04, 2004.
		Upper bounds on the bipartite number of simple connected graphs, b(G).
E	86.	If G is a simple connected graph, then b(G) ≤ 2 + n - w(G)	definitions
		April 10, 2004.
E	89.	If G is a simple connected graph, then b(G) ≤ 2a(G)	definitions
		April 10, 2004.
		Upper bounds on the independence number of simple connected graphs, a(G).
R	92.	If G is a simple connected graph, then a(G) ≤ FLOOR[( n + p)/2]	definitions  reference
		April 21, 2004. This is equivalent to conjecture #11 which as described in the reference I knew was correct for all simple graphs.
E	93.	If G is a simple connected graph, then a(G) ≤ f(G) -1	definitions
		April 21, 2004.
T	94.	If G is a simple connected graph, then a(G) ≤ CEIL[b(G) - SQRT[circumference(G)]]	definitions
		April 21, 2004. July 2005, for large enough  circumference(G), the conjecture follows from the proposition below. Proposition. If G is a simple connected graph, then b(G) ≥ a(G) + FLOOR(circumference(G)/4). Proof. Note circumference(G) => 3.  Let C be the set of vertices of a largest induced cycle. Let I be the set of vertices of a maximum independent set. Color the vertices of I with color green. Since the intersection of C and I is at most FLOOR(circumference(G)/2), there are at least FLOOR(circumference(G)/4) vertices of C that can be colored red. Hence, G has an induced bipartite subgraph on at least a(G) + FLOOR(circumference(G)/4) vertices. October 12, 2006. Benny John.
T	97.	If G is a simple connected graph, then a(G) ≤ maximum of l(v) - d(G)	definitions
		April 21, 2004. Fajtlowicz April 2004
E	99.	If G is a simple connected graph, then a(G) ≤ b(G) -minimum of l(v)	definitions
		April 21, 2004. DeLaVina April 2004
T	101.	If G is a simple connected graph, then a(G) ≤ FLOOR[(n + alphacore(G))/2]	definitions
		April 21, 2004.  This follows from the inclusion-exclusion principle. March 14, 2008. Pepper and I noticed a similar bound a(G) ≤ matching(G) + alphacore(G).
T	102.	If G is a simple connected graph, then a(G) ≤ CEIL[b(G) - SQRT[diam(G)]]	definitions
		April 21, 2004. July 2005, for large enough diameter this follows from the proposition listed below conjecture 17.  October 12, 2006. Benny John.
E	106.	If G is a simple connected graph, then a(G) ≤ n - domination(G)]	definitions
		April 21, 2004.
		Lower bounds on the matching number of connected bipartite graphs, m(G).
		note: Graffiti.pc was asked to focus on lower bounds for the matching number, which are sharp for some connected bipartite graphs and thus some conjectures were made for all graphs (see 113 & 127)
E	112.	If G is a connect bipartite graph, then m(G) ≥ CEILING[freq(D(G))/2]	definitions  reference
		June, 2004. DeLaVina and Gramajo June 2004.
T	113.	If G is a simple connected graph, then m(G) ≥ CEILING[dd(G)/2]	definitions  reference
		June, 2004. DeLaVina and Gramajo (June 2004) proved this for connected bipartite graphs. Jan 2005.  Craig Larson proved this for all simple graphs with no isolated vertices.
E	114.	If G is a connect bipartite graph, then m(G) ≥ minimum { 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.
T	124	If G is a connected X,Y bigraph such that |X| £ |Y|, then m(G) ≥ minimum{CEILING[1 + median of degrees], |X|}	definitions
		December 2004.  I. Gramajo, Feb 2005.
T	125	If G is a connected X,Y bigraph such that |X| £ |Y|, then m(G) ≥ minimum{1 + k, |X|}, where k is the (n-|X|-1)th degree of the ordered degree sequence.	definitions
		December 2004.  I. Gramajo, Feb 2005.
T	127	If G is a simple connected graph, then m(G) ≥ minimum{1 + ecc(centers), minimum of disteven(G)}	definitions
		December 2004.  I. Gramajo, Mar 2005.
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.
T	135.	If G is a simple connected graph, then path(G) ≥ girth/d(G)	definitions
		July 12, 2005. B. Waller
		2nd run for Lower bounds on the tree number of simple connected graphs, tree(G). See 68-85 for 1st run. Note: the program repeated some conjectures, but I do not repeat them here.
	Note:	Clearly b(G)  ≥  f(G)  ≥ tree(G) ≥ path(G).
E	140.	If G is a simple connected graph, then tree(G) ≥ 1 + maximum of l(v)	definitions
		July 19, 2005.
E	147.	If G is a simple connected graph, then tree(G) ≥ n(G)*t(G)	definitions
		July 19, 2005.
			Next List
		2nd Run for Lower bounds for maximum number of leaves over all spanning trees, 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.
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.
E	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.
			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.
		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
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	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).
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).
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.
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.
		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.
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.
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.
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.
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.
		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.
T	288.	If G is a simple connected graph, then gt(G) ≤ p(G) + m(G)	definitions
		Feb. 23  2006.  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.
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.
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:
		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.
		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.
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
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. In [DLPW3] we simplified the proof. [DLPW3] DeLaVina, Larson, Pepper, and Waller, Graffiti.pc on the 2-domination number of a tree, preprint 2009.
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.
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 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 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 409b & 409c 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.
		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.
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).
		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	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.
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	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	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	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."