Ermelinda DeLaVina (delavinae@uhd.edu)
| Dalmatian Heuristic (conjectures 1-189) | Next List | ||
| 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. |
|||
| O | 2. | If G is a simple connected graph, then Ls(G) ≥ 2(average of l(v) - 1) | definitions reference |
| 1996 | |||
| 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 | |||
| Dalmatian Heuristic | Next List | ||
| 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 | |||
| Dalmatian Heuristic | Next List | ||
| 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.. | |||
| O | 19. | If G is a simple connected graph, then b(G) ≥ FLOOR(average of ecc(v)+maximum of l(v)) | definitions |
| July 3, 2003. June 22, 2005, note: if average of ecc(v) <= diam -1, then this conjecture follows from conjecture #13. | |||
| 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 increase 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 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 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. | |||
| 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). | |||
| 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 | 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. | |||
| Dalmatian Heuristic | Next List |
| 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 Theorem, 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. | |||
| O | 34. | If G is a simple connected graph, then path(G) ≥ CEIL[distavg(C,V) + distavg(M,V)] | definitions |
| July 15, 2003. | |||
| 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. | |||
| Dalmatian Heuristic | Next List | ||
| 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. | |||
| O | 40. | If G is a simple connected graph on more than one vertex, then f(G) ≥ CEIL[(p(G)+b(G)+1)/2] | definitions |
| Mar 05, 2004. Mar 6, 2004, DeLaVina: For a connected graph on more than one vertex it is easily shown that f(G) ≥ b(G)/2 + 1. Thus, in the special case that path covering is one, the result follows. | |||
| 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 | |||
| Dalmatian Heuristic | Next List | ||
| 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 and, 47 were repeated with conjectures 57-67. | ||
| E | 57. | If G is a simple connected graph, then f(G) ≥ tree(G) | definitions |
| Mar 25, 2004. | |||
| O | 58. | If G is a simple connected graph, then f(G) ≥ CEIL[ b(G)/average of l(v)] | definitions |
| Mar 25, 2004. This conjecture seems to be similar to conjecture 91. | |||
| O | 59. | If G is a simple connected graph, then f(G) ≥ CEIL[sqrt[res(G)*b(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.. | |||
| O | 61. | If G is a simple connected graph, then f(G) ≥ res(G)+ CEIL[diam(G)/3] | definitions |
| Mar 25, 2004. | |||
| 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. | |||
| O | 63. | If G is a simple connected graph, then f(G) ≥ CEIL[(minimum of disteven(v) + b(G) + 1)/3] | definitions |
| Mar 25, 2004. | |||
| O | 64. | If G is a simple connected graph, then f(G) ≥ CEIL[(sqrt[a(G) * (1 + (n mod D(G))] ] | definitions |
| Mar 25, 2004. | |||
| O | 65. | If G is a simple connected graph, then f(G) ≥ distmin(A) + CEIL(distmin(M)/3], where A is the set of vertices of minimum degree and M is the set of vertices of maximum degree. | definitions |
| Mar 25, 2004. | |||
| O | 66. | If G is a simple connected graph, then f(G) ≥ 2*CEIL[even_modemin(G) /degavg(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. | |||
| Dalmatian Heuristic | Next List | ||
| 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. . | |||
| O | 72. | If G is a simple connected graph, then tree(G) ≥ CEIL[average of ecc(v) + maximum of l(v) /3] | definitions |
| Apr 04, 2004. | |||
| 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 |
|
Apr 04, 2004. May 2004 DeLaVina see
counterexample.
Note #42 of wowII is still open f(G) ≥ CEIL(2distavg(B,V)). |
|||
| 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. | |||
| O | 76. | If G is a simple connected graph, then tree(G) ≥ freq[Tmax(v)]/FLOOR[degavg(G)] | definitions |
| Apr 04, 2004. | |||
| 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 | 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 | 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 | 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. | |||
| O | 84. | If G is a simple connected graph, then tree(G) ≥ 2rad(G)/d(G) | definitions |
| Apr 04, 2004. | |||
| O | 85. | If G is a simple connected graph, then tree(G) ≥ CEIL[sqrt(1 + 2*minimum of disteven(v))] | definitions |
| Apr 04, 2004. | |||
| Dalmatian Heuristic | Next List | ||
| 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. | |||
| O | 91. | If G is a simple connected graph, then b(G) ≤ 1 + f(G) * (CEIL[average of l(v) ])/2 | definitions |
| April 10, 2004. This conjecture seems to be similar to conjecture 58, but tighter for large b. | |||
| Dalmatian Heuristic | Next List | ||
| 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. |
|||
| 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. | |||
| O | 96. | If G is a simple connected graph, then a(G) ≤ 1 + minimum disteven(v)*(maximum of l(v) -1) | definitions |
| April 21, 2004. | |||
| 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 | |||
| O | 100. | If G is a simple connected graph, then a(G) ≤ CEIL[(maximum of l(v) + 0.5*length(G))/2] | definitions |
| April 21, 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. |
|||
| O | 103. | If G is a simple connected graph, then a(G) ≤ FLOOR[b(G) - LN[average of ecc(v)] | definitions |
| April 21, 2004. July 2005, for large enough diameter this follows from the proposition listed below conjecture 17. | |||
| 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) ≤ 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. |
|||
| O | 108. | If G is a simple connected graph, then a(G) ≤ maximum disteven(v) + 2*FLOOR[alphacore(G)/3] | definitions |
| April 21, 2004. |
|||
| O | 109. | If G is a simple connected graph, then a(G) ≤ FLOOR[(residue(G)+2b(G))/3] | definitions |
| April 21, 2004. |
|||
| 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. |
|||
| O | 111. | If G is a simple connected graph, then a(G) ≤ CEIL[1 + |N(S)|* (average of l(v)- 1)], where S is the set of maximum degree vertices of the complement of the graph G the neighborhood is taken in the complement. | definitions |
| April 21, 2004. |
|||
| Dalmatian Heuristic | |||
| 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 connected 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 connected 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 connected 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 connected 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 connected 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 connected 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 | |||
|
| |||
| Dalmatian Heuristic | |||
| 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. | |||
| O | 133. | If G is a simple connected graph, then path(G) ≥ rad(G)+ [average of l(v)]^cC4 | definitions |
| July 12, 2005. | |||
| 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 | |||
| O | 136. | If G is a simple connected graph, then path(G) ≥ (1+girth)/D(R) | definitions |
| July 12, 2005. | |||
| O | 137. | If G is a simple connected graph, then path(G) ≥ 4/p(G) | definitions |
| July 12, 2005. | |||
| O | 138. | If G is a simple connected graph, then path(G) ≥ (2+u(G))*distmin(M(G2)) | definitions |
| July 12, 2005. | |||
| 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. | |||
| Dalmatian Heuristic | |||
| 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. | |||
| O | 141. | If G is a simple connected graph, then tree(G) ≥ (1/2)*girth - 1+ maximum of l(v) | definitions |
| July 19, 2005. | |||
| O | 142. | If G is a simple connected graph, then tree(G) ≥ (2/3)*girth + ecc(B) | definitions |
| July 19, 2005. | |||
| O | 143. | If G is a simple connected graph, then tree(G) ≥ (girth + 1)/σ(G) | definitions |
| July 19, 2005. | |||
| O | 144. | If G is a simple connected graph, then tree(G) ≥ girth -1 + ecc(Centers) | definitions |
| July 19, 2005. | |||
| O | 145. | If G is a simple connected graph, then tree(G) ≥ 2*ecc(B)/lmin(G) | definitions |
| July 19, 2005. | |||
| O | 146. | If G is a simple connected graph, then tree(G) ≥ 2*ecc(B)/rad(G2) | 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. | |||
| Dalmatian Heuristic | 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 reference |
| Aug 8, 2005. Independently, in [KV] it is noted that equality holds in trees if and only if the it has at most one vertex of degree more than 2. | |||
| O | 154. | If G is a simple connected graph, then Ls(G) ≥ (1 + maximum order of radial circles)/ minimum order of radial circles. | definitions |
| Aug 8, 2005. Note that this conjecture proposes a sufficient condition for improvement of conjecture 5. | |||
| O | 155. | If G is a simple connected graph, then Ls(G) ≥ 1 + number of distinct orders of radial circles. | 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. | |||
| O | 157. | If G is a simple connected graph, then Ls(G) ≥ (f1(G) + SQRT[2* maximum {|E(R(v))|: v is a center of 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. | |||
| O | 160. | If G is a simple connected graph, then Ls(G) ≥ maximum of l(v) + maximum T(v)*cC4(G). | definitions |
| Aug 8, 2005. | |||
| O | 161. | If G is a simple connected graph, then Ls(G) ≥ maximum of l(v) of G. | definitions |
| Aug 8, 2005. | |||
| O | 162. | If G is a simple connected graph, then Ls(G) ≥ freq of minimum of l(v)*FLOOR[1 /d(G)]. | definitions |
| Aug 8, 2005. | |||
|
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. | |||
| O | 165. | If G is a simple connected graph, then Ls(G) ≥ CEIL[Sqrt[2*|N(M)-M|]], where M is the set of vertices of maximum degree. | definitions |
| Aug 8, 2005. During the summer of 2005, the invariants Ls(G) and |N(M)-M| occurred in conjectures for Craig Foster's independent summer UHD student research project. The theme of those conjectures turned to the question is there a constant c such that Ls(G) ≥ c* |N(M)-M|. Craig's examples show that if a c exists, then c ≤ 1/4. He constructs graphs such that for k ≥ 1, L(G) = k + 2.and |N(M)-M| = 4k. | |||
| O | 166. | If G is a simple connected graph, then Ls(G) ≥ |N(M)-M|]/SQRT[rad(G)], where M is the set of vertices of maximum degree. | definitions |
| Aug 8, 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. | |||
| O | 169. | If G is a simple connected graph, then Ls(G) ≥ 1 + maximum of disteven(v) - minimum of disteven(v). | definitions |
| Aug 8, 2005. | |||
| 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. | |||
| O | 171. | If G is a simple connected graph, then Ls(G) ≥ (-1 + maximum of disteven(v) )/distavg(B), where B is the set of boundary vertices. | definitions |
| Aug 8, 2005. | |||
| O | 172. | If G is a simple connected graph, then Ls(G) ≥ -1 + D(B)+ distmin(M2), where B is the boundary and M2 is the set of maximum degree vertices of the second power graph of G. | definitions |
| Aug 8, 2005. | |||
| Dalmatian Heuristic | 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. |
|||
| O | 174. | If G is a simple connected graph on at least 2 vertices, then Ls(G) + b(G) ≥ n + maximum of l(v) -1. | definitions reference |
| Aug 8, 2005. Since 2a(G) ≥ b(G), if 174 is correct then Graffiti's #7 on wowII would follow from 174. See Theorem 4 in reference for a proof of Ls(G) + b(G) ≥ n + CEIL[0.5*maximum of l(v)]. | |||
| 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. | |||
| O | 176. | If G is a simple connected graph on at least 2 vertices, then Ls(G) + b(G) ≥ n + distmin(M2), where M2 is the set of vertices of maximum degree of G2. | definitions |
| Aug 8, 2005. | |||
| O | 177. | If G is a simple connected graph on at least 2 vertices, then Ls(G) + b(G) ≥ 2a(G) +σ(G). | definitions reference |
| Aug 8, 2005. Waller proved that Ls(G) + b(G) ≥ 2a(G) + 1, see reference. | |||
| O | 178. | If G is a simple connected graph on at least 2 vertices, then Ls(G) + b(G) ≥ maximum of l(v) + maximum of {|N(e)|: e an edge of G}. | definitions |
| Aug 8, 2005. Note: Since Ls(G) ≥ maximum of {N(e): e an edge of G} -2 and b(G) ≥ maximum of l(v) + 1, it follows that Ls(G) + b(G) ≥ maximum of l(v) + maximum of {N(e): e an edge of G} -1, thus this conjecture proposes a slightly stronger bound that the one easily deduced. | |||
| O | 179. | If G is a simple connected graph on at least 2 vertices, then Ls(G) + b(G) ≥ D(G) + domination(G) + maximum of l(v). | definitions |
| Aug 8, 2005. | |||
| O | 180. | If G is a simple connected graph on at least 2 vertices, then Ls(G) + b(G) ≥ 1 + a(G) + maximum of disteven(v) . | definitions |
| Aug 8, 2005. | |||
| O | 181. | If G is a simple connected graph on at least 2 vertices, then Ls(G) + b(G) ≥ a(G) + degavg(B(G2)) . | definitions |
| Aug 8, 2005. | |||
| O | 182. | If G is a simple connected graph on at least 2 vertices, then Ls(G) + b(G) ≥ D(B(G2)) + diam(G) . | definitions |
| Aug 8, 2005. | |||
| O | 183. | If G is a simple connected graph on at least 2 vertices, then Ls(G) + b(G) ≥ D(G2) + 2*rad(G2) . | definitions |
| Aug 8, 2005. | |||
| O | 184. | If G is a simple connected graph on at least 2 vertices, then Ls(G) + b(G) ≥ D(G2) + 2*distavg(B(G2),V(G2)) . | definitions |
| Aug 8, 2005. | |||
| O | 185. | If G is a simple connected graph on at least 2 vertices, then Ls(G) + b(G) ≥ D(G2) + 2*distavg(G2) . | definitions |
| Aug 8, 2005. | |||
| O | 186. | If G is a simple connected graph on at least 2 vertices, then Ls(G) + b(G) ≥ |N(C(G2))| + 2*ecc(C(G2)), where C(G2 ) is the set of center vertices of the second power graph. | definitions |
| Aug 8, 2005. | |||
| 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. 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 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. | |||
| O | 189. |
If G is a simple connected graph with n > 1 such that
maximum { disteven(v) : disteven(v) is the number of vertices at even distance from v } ≤ 1 + σ(G), then G has a Hamiltonian path. |
definitions |
| Jan 12, 2006. | |||
| O | 190. | If G is a simple connected graph with n > 1 such that 0.5(LS(G)+1) ≤ σ(G), then G has a Hamiltonian path. | definitions |
| Jan 12, 2006. Note that
LS(G) = n -
gc.
where gc
is the connected domination number of G. Then this conjecture is
equivalent to
If G is a simple connected graph with n > 1 such that [n - gc+ 1]/2 ≤ σ(G), then G has a Hamiltonian path.
|
|||
| O | 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 #3) 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 #3 is not satisfied for paths. | |||
| 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 193; frequency of λmax(G) = 18 and 1+ Σ(G) = 16. | |||
| O | 194. | If G is a simple connected graph with n > 1 such that a(G) ≤ 1 + λavg(G) , then G has a Hamiltonian path. | definitions |
| Jan 12, 2006. | |||
| 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). | |||
| O | 198a. | If G is a simple connected graph with n > 1 such that b(G) ≤ 2 + eccavg(G), then G has a Hamiltonian path. | definitions |
| Jan 12, 2006. This too was eventually superseded. | |||
| O | 199. | If G is a simple connected graph with n > 1 such that tree(G) - 2 ≤ κ(G), then G has a Hamiltonian path. | definitions |
| Jan 12, 2006. | |||
| O | 200. | If G is a simple connected graph with n > 1 such that tree(G) =CEIL[1 + λavg(G)], then G has a Hamiltonian path. | definitions |
| Jan 12, 2006. | |||
| 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). | |||
| 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 | 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. | |||
| O | 209. | If G is a simple connected graph with n > 1 such that (1/6)* [1 + (2)*|E(G)|] ≤ frequency of λmax(G), then G has a Hamiltonian path. | definitions |
| Jan 12, 2006. | |||
| 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. | |||
| O | 213. | If G is a simple connected graph with n > 1 such that 2 + the lower median of degree sequence of G ≤ g2 (G), then G has a Hamiltonian path. | definitions |
| Jan 12, 2006. | |||
| 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 216 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. | |||
| O | 217. | If G is a simple connected graph with n > 1 such that L(G) ≤ 4*cresidue=2(G) + 2, then G has a Hamiltonian path. | definitions |
| Jan 12, 2006. | |||
| 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 (50 T 8 F 20 O 22) | |||
| 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. | |||
| O | 232. |
If G is a simple connected graph, then
gt(G)
≥
0.5*[radius(G) + ecc(B)
] |
definitions |
| Feb. 23, 2007. | |||
| O | 233. |
If G is a simple connected graph, then
gt(G)
≥
(2/3) * (1+ecc(B)
) |
definitions reference |
| Feb. 23, 2007. June 2007, in the reference it is proven that for a tree T, g(T) ≥ (1/2) * (1+ecc(B) ). A similar agreement for trees yields gt(T) ≥ (3/4) * (1+ecc(B) ). | |||
| 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. | |||
| O | 235. |
If G is a simple connected graph, then
gt(G)
≥
(2/3) ecc(B)
+ cbipartite(G). |
definitions |
| Feb. 23, 2007. | |||
| 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. |
|||
| O | 241. |
If G is a tree, then
gt(G)
≥ FLOOR[number of components(<N[S]>)
+ distavg(C)], where <N[S]> is the subgraph induced by the closed
neighborhood of the set of vertices of degree two and C is the set of center
vertices. |
definitions |
| Feb. 23, 2007. | |||
| O | 242. |
If G is a tree, then
gt(G)
≥ (1/2)[number of components(<N[S]>
+ eccavg(G)], where <N[S]> is the subgraph induced by the closed
neighborhood of the set of vertices of degree two. |
definitions |
| Feb. 23, 2007. | |||
| O | 243. |
If G is a simple connected C4-free graph, then
gt(G)
≥ 1 + number of components(<M>), where
<M> is the subgraph induced by the set
of vertices of maximum degree. |
definitions |
| Feb. 23, 2007. Feb 2009: DFW we can prove this for trees. | |||
| O | 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. | |||
| 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. |
|||
| O | 247. |
If G is a simple connected degree-regular graph, then
gt(G)
≥ 2*
p(G) |
definitions reference |
| Feb. 23, 2007. May 2007: Qi Liu and Doug West proved this in case the degree is at most 3, 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: Independently B. Waller and R. Pepper communicated proofs. | |||
| 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. | |||
| O | 251. |
If G is a simple connected graph such that girth(G) ≥
5, then
gt(G)
≥ 1 + upper_median(G). |
definitions |
| Feb. 23, 2007. | |||
| O | 252. |
If G is a simple connected C4-free graph, then
gt(G)
≥ modemin(G) |
definitions |
| Feb. 23, 2007. | |||
| O | 253. |
If G is a simple connected graph such that girth ≥
5, then
gt(G)
≥ 1 + modemin(G) |
definitions |
| Feb. 23, 2007. | |||
| 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. | |||
| O | 255. |
If G is a simple connected graph, then
gt(G)
≥ 2*|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. | |||
| O | 256. |
If G is a simple connected graph, then
gt(G)
≥ 2*|N(A)|/[maximum of {N(e):
e an edge of G}],
where A is the set of vertices of minimum degree. |
definitions |
| Feb. 23, 2007. | |||
| 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. | |||
| O | 258. |
If G is a simple connected graph, then
gt(G)
≥ 2*evenmax(G)/L(G), where
evenmax(G) = maximum {even(w) : even(w) = |{u : dist(w,u} is even}|}. |
definitions |
| Feb. 23 , 2007. | |||
| O | 259. |
If G is a simple connected graph, then
gt(G)
≥ 2*|N(M)-M|/L(G), where M is the
set of vertices of maximum degree. |
definitions |
| Feb. 23, 2007. | |||
| O | 260. |
If G is a simple connected graph, then
gt(G)
≥ 2*|N(B)-B|/L(G), where B is the
set of vertices of maximum maximum eccentricity. |
definitions |
| Feb. 23, 2007. | |||
| O | 261. |
If G is a simple connected graph, then
gt(G)
≥ 2*|N(S)-S|/L(G), where S is the
set of vertices of degree two. |
definitions |
| Feb. 23, 2007. | |||
| 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. | |||
| O | 267. |
If G is a simple connected graph such that girth(G) ≥
5, then
gt(G)
≥ CEIL[distavg(A,V)],
where A is the set of minimum degree vertices. |
definitions |
| Feb. 23, 2007. | |||
| O | 268. |
If G is a simple connected graph, then
gt(G)
≥ FLOOR[1+distavg(C)],
where C is the set of center vertices. |
definitions |
| Feb. 23, 2007. | |||
| O | 269. |
If G is a simple connected C4-free graph, then
gt(G)
≥ CEIL[1+distavg(C)],
where C is the set of center vertices. |
definitions |
| Feb. 23, 2007. | |||
| 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. | |||
| O | 271. |
If G is a simple connected graph, then
gt(G)
≥ CEIL[SQRT[2*distmax(M)]],
where M is the set of vertices of maximum degree. |
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 connected 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. (34 T 9 F 12 O 14- 2/19/09) | |||
| R | 279. |
If G is a simple connected graph such that n(G)> 2, then
gt(G) ≤
2*g(G)) |
definitions |
| Mar. 1, 2007. | |||
| R | 280. |
If G is a simple connected graph such that n(G)> 2, then
gt(G) ≤
FLOOR[(2/3)*n(G)] |
definitions |
| Mar. 1, 2007. | |||
| O | 281. |
If G is a simple connected graph such that n(G)> 2, then
gt(G) ≤
[frequency of
λmin(G)] + m(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. | |||
| 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. | |||
| O | 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. | |||
| 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. | |||
| O | 287. |
If G is a simple connected graph such that n(G)> 2, then
gt(G) ≤
k+ m(G),
where k is the first step in which a zero appears in the Havil-Hakimi process. |
definitions |
| Mar. 1, 2007. | |||
| T | 288. |
If G is a simple connected graph such that n(G)> 2, 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. |
|||
| 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. | |||
| O | 290. |
If G is a simple connected graph such that n(G)> 2, then
gt(G) ≤
k*D(G), where k
is the first step in which a zero appears in the Havil-Hakimi process. |
definitions |
| Mar. 1, 2007. | |||
| O | 291. |
If G is a simple connected graph such that n(G)> 2, then
gt(G) ≤
k + frequency tmin(v),
where k is the first step in which a zero appears in the Havil-Hakimi process. |
definitions |
| Mar. 1, 2007. | |||
| 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 such that n(G)> 2, 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: This conjecture follows as a corollary to a result of Chellali and Haynes: If T is a tree on n > 2 vertices with s support vertices, then gt(T) ≤ [n(T) +s]/2. Mar. 30, 2007. Stephen Hartke, Qi Liu, Doug West and Hehui Wu communicated a proof of If G is a simple connected graph such that n(G)> 2, then gt(G) ≤ [n(G) + l ]/2, where l is the minimum number of leaves overall spanning trees of G. Note: 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). Note: In [DHHS] Dankelmann et. al proved.: If T is a tree, then gr(T) ≤ [n(T) + l + 1]/2, where l is the number of leaves of T. gr(T) is the restrained domination number, which is the smallest dominating set S such that every vertex in V-S is adjacent to a vertex in S and in V-S. But, large enough paths and stars show that restrained domination number and the total domination number are not related.. |
|||
| O | 298. |
If G is a simple connected graph such that n(G)> 2, then
gt(G) ≤
annihilation(G)+ cC4(G). |
definitions |
| Mar. 1, 2007. | |||
| O | 299. |
If G is a simple connected graph such that n(G)> 2, then
gt(G) ≤
annihilation(G)+ |S|, where S is the set of
vertices of degree two. |
definitions |
| Mar. 1, 2007. | |||
| O | 300. |
If G is a simple connected graph such that n(G)> 2, then
gt(G) ≤
(1/2)*[n(G) + frequency of λmin(G)] |
definitions |
| Mar. 1, 2007. | |||
| T | 301. |
If G is a simple connected graph such that n(G)> 2, then
gt(G) ≤
w(G) + frequency of λmax(G)) |
definitions |
| Mar. 1, 2007. | |||
| O | 302. |
If G is a simple connected graph such that n(G)> 2, then
gt(G) ≤
minimum of disteven(v) + 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. | |||
| O | 304. |
If G is a simple connected graph such that n(G)> 2, then
gt(G) ≤
(1/2)*[(frequency of λmax(G))
+ maximum of NG(e)] |
definitions |
| Mar. 1, 2007. | |||
| O | 305. |
If G is a simple connected graph such that n(G)> 2, then
gt(G) ≤
CEIL[(2/3)*maximum of |NG(e)|] |
definitions |
| Mar. 1, 2007. | |||
| T | 306. |
If G is a simple connected graph such that n(G)> 2, 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. | |||
| O | 308. |
If G is a simple connected graph such that n(G)> 2, then
gt(G) ≤ (1/2)*[maxine(G)
+ minimum of |NG(e)|] |
definitions |
| Mar. 1, 2007. | |||
| O | 309. |
If G is a simple connected graph such that n(G)> 2, then
gt(G) ≤ (1/2)*[maximum {disteven(v) - even horizontal(v): v in V(G)}
+ minimum of |NG(e)|] |
definitions |
| Mar. 1, 2007. | |||
| O | 310. |
If G is a simple connected graph such that n(G)> 2, then
gt(G) ≤
CEIL[1 + Tdistmin(v)/3] |
definitions |
| Mar. 1, 2007. | |||
| F | 311. |
If G is a simple connected graph such that n(G)> 2, 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 | |||
| Sufficient conditions on a simple connected graphs for every minimal Total Dominating Set is a minimum Total Dominating Set. A graph with this property will be said to be Well Total Dominated. | |||
| 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. | |||
| O | 314. | Let G is a simple connected graph with n > 1. If G is triangle-free and path number ≤ 4, then G is well total dominated. | definitions |
| Mar. 4, 2007. | |||
| O | 315. | Let G is a simple connected graph with n > 1. Let P be the pendant vertices of G. If a(G) = |P|, then G is well total dominated. | definitions |
| Mar. 4, 2007. | |||
| O | 316. | Let G is a simple connected graph with n > 1. Let P be the pendant vertices of G. If |P| ≥ degavg(G), then G is well total dominated. | definitions |
| Mar. 4, 2007. | |||
| O | 317. | Let G is a simple connected graph with n > 1. If tree number ≥ |E(G)|, then G is well total dominated. | definitions |
| Mar. 4, 2007. | |||
| O | 318. | Let G is a simple connected graph with n > 1. If maximum disteven(v) ≥ |E(G)|, then G is well total dominated. | definitions |
| Mar. 4, 2007. | |||
| O | 319. | Let G is a simple connected graph with n > 1. If maximum disteven(v) = g(G), then G is well total dominated. | definitions |
| Mar. 4, 2007. | |||
| O | 320. | Let G is a simple connected graph with n > 1. If maximum disteven(v) = Tdistmin(G), then G is well total dominated. | definitions |
| Mar. 4, 2007. | |||
| O | 321. | Let G is a simple connected graph with n > 1. If eccavg(G) ≥ (1/3)*Tdistmax(G), then G is well total dominated. | definitions |
| Mar. 4, 2007. | |||
| O | 322. | Let G is a simple connected graph with n ≥ 5. If λmax(G) ≤ 1, then G is well total dominated. | definitions |
| Mar. 4, 2007. | |||
| O | 323. | Let G is a simple connected graph with n > 1. If maximum of {|NG(e)|: e an edge of G} ≤ 1 + maximum {distodd(v) - odd horizontal(v): v in V(G)}, then G is well total dominated. | definitions |
| Mar. 4, 2007. | |||
| O | 324. | Let G is a simple connected graph with n > 1. If maximum of {|NG(e)|: e an edge of G} ≤ 1 + residue(G), then G is well total dominated. | definitions |
| Mar. 4, 2007. | |||
| O | 325. | Let G is a simple connected graph with n > 1. If minimum of {|NG(e)|: e an edge of G} ≤ 1 + number of components of <N[S}> where S is the set of vertices of degree two, then G is well total dominated. | definitions |
| Mar. 4, 2007. | |||
| O | 326. | Let G is a simple connected graph with n > 1. If 3*m(G) ≤ |E(S)| where S is the set of vertices of degree two, then G is well total dominated. | definitions |
| Mar. 4, 2007. | |||
| O | 327. | Let G is a simple connected graph with n > 1. If 3*g(G) = gi(G), then G is well total dominated. | definitions |
| Mar. 4, 2007. | |||
| O | 328. | Let G is a simple connected graph with n > 1. If 4*m(G) ≤ frequency of maximum{K(v): K(v) is the number of K4 incident to a vertex v}, then G is well total dominated. | definitions |
| Mar. 4, 2007. Note that if the graph has no K4, then the right hand side is n. | |||
| 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. | |||
| 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. | |||
| O | 340. | If T is a tree on n > 2 vertices, then γt ≤ number of components of <N(L) ∪ L> + modemin(T)* γ(T), where L is the set of leaves of T | definitions |
| Feb. 18, 2009. | |||
| O | 341. | If T is a tree on n > 2 vertices, then γt ≤ ⌈½A(T)⌉*σ(T) | definitions |
| Feb. 18, 2009. | |||
| O | 342. | If T is a tree on n > 2 vertices, then γt ≤ A(T) + ⌈half of number of isolates of <S(T)>⌉, where S(T) is the set of support vertices of T | definitions |
| Feb. 18, 2009. | |||
| O | 343. | If T is a tree on n > 2 vertices with degree 2 vertices, then γt ≤ A(T)+ ⌈half of number of components of <D2>⌉, where D2={v| deg(v) = 2} | definitions |
| Feb. 18, 2009. | |||
| O | 344. | If T is a tree on n > 2 vertices, then γt ≤ A(T) -1 + number of components of <N(L) ∪ L >, where L is the set of leaves of T | definitions |
| Feb. 18, 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. |
|||
| 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. |
|||
| O | 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. | |||
| O | 348. | If T is a tree on n>2 vertices, then γT(T) ≥ 2⁄3 |N(D2(T)) - D2(T)|, where D2={v| deg(v) = 2}. | definitions |
| Feb. 18, 2009. | |||
| O | 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. | |||
| O | 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. | |||
| O | 351. |
If T is a tree on n>2 vertices, then γT(T) ≥
number of components of <S(T) ∪ L
> + number of components of <N(D2(T)) ∪ D2(T)
>,
where S(T) is the set of support vertices, L is the set of leaves, and D2={v| deg(v) = 2}. |
definitions |
| Feb. 18, 2009. | |||
| O | 352. | If T is a tree on n>2 vertices, then γT(T) ≥ number of components of <N(D2(T)) ∪ D2(T) > + ⌈ ½ eccavg(M)⌉, where M is the set of vertices of maximum degree and D2={v| deg(v) = 2}. | definitions |
| Feb. 18, 2009. | |||
| O | 353. | If T is a tree on n>2 vertices, then γT(T) ≥ number of components of <D2(T) > + half of the order of a largest component of <M >, where D2={v| deg(v) = 2} and M is the set of vertices of maximum degree. | definitions |
| Feb. 18, 2009. | |||
| O | 354. | If T is a tree on n>2 vertices, then γT(T) ≥ ½|C| * number of components of <N(D2(T)) >, where D2={v| deg(v) = 2} and C is the set of all centers of T. | definitions |