Ermelinda DeLaVina (delavinae@uhd.edu)
| Lower bounds for maximum number of leaves over all spanning trees, Ls(G) | |||
| Note: there is now a second list for Ls(G). | |||
| T | 1. | If G is a simple connected graph, then Ls(G) ≥ n + 1 - 2m(G) | definitions reference |
| 1996. In 1984, Hedetniemi and Laskar [HL] proved that
for simple connected graphs Ls(G) ≥ n - 2m(G).
In 1996, Fajtlowicz proved that for connected
graphs on at least two vertices Ls(G) ≥ n + 1 - 2m(G)
and later send the following. Dec 12, 2004 Fajtlowicz. Let T be a spanning tree containing a maximum matching. Then Graffiti's conjecture follows (for graphs with at least one edge) from the Lemma. Let T be a n-vertex tree with L endpoints and n > 1. If T has a matching with m edges then L > n - 2m. Proof: We can assume that n > 3. *Suppose T has two leaves adjacent to a vertex u of degree > 2. Let T' be the tree obtained from T by deletion of one of these leaves,* and let n', L' and m' be the corresponding invariants of T'. Since n' > 1, by induction on n we have that L' > n' - 2m'. Because deg(u) > 2, it follows that L' = L-1, and m' = m. Thus L - 1 > n - 1 - 2m' , i.e., L > n - 2m. Suppose now that T has a leaf adjacent to a vertex of degree 2 and let T' be the tree obtained from T by deleting this leaf and its unique neighbor *u*. Clearly m'= m-1 in this case and L' = L if the degree of the other neighbor of u is 2 and L-1 otherwise. In either of these two cases we have L >= L' > n' - 2m' >= n - 2 - 2 (m-1) = n - 2m and the theorem again follows by induction on n, because n' > 1. |
|||
| T | 3. | If G is a simple connected graph, then Ls(G)≥ gi(G) * maximum temp(v) | definitions |
| 1996. Mar. 17, 2004: Ryan
Pepper " Here, MID is the number of vertices in a minimum independent
dominating set. Take any vertex v of max degree D from graph G with n
vertices and remove all vertices adjacent to v leaving G'. Now, any
independent dominating set of G' must include v and so is also an
independent dominating set of G. But there are at most n-D vertices in any
independent dominating set of G'. Therefore, MID <= n-D, since MID is
cardinality of a minimum independent dominating set. The rest of proof is as
even more of an exercise than this and goes as follows. For any
graph, max(temp) <= D/(n-D), D is max degree. So,
MID(max(temperature)) <= (n-D)D/(n-D) = D <= Max number of leaves of spanning tree. The last inequality because, starting from a vertex x of maximum degree, we can build a spanning tree by including first all vertices of distance one from x, then all vertices of distance two from x, etc .... This will give spanning tree with a vertex of maximum degree D, and every tree has at least as many leaves as its maximum degree." |
|||
| T | 4. | If G is a simple connected graph, then Ls(G) ≥ minimum of |NG(e)| - 1 | definitions reference |
| 1996. DeLaVina 1996 | |||
| T | 5. | If G is a simple connected graph, then Ls(G) ≥ maximum{| S(v, rad(G)) |: v is a center of G} | definitions reference |
| 1996. DeLaVina and Fajtlowicz 1996 | |||
| T | 6. | If G is a simple connected graph, then Ls(G) ≥ 1 + n -m(G)- a(G) | definitions reference |
| 1996. DeLaVina 1996 | |||
| T | 7. | If G is a simple connected graph, then Ls(G) ≥ maximum of l(v) -1 + n - 2a(G) | definitions reference |
| 1996. DeLaVina, Fajtlowicz, Waller (2002) | |||
| T | 8. | If G is a simple connected graph, then Ls(G) ≥ maximum of disteven(v) - a(G) | definitions reference |
| 1996. DeLaVina 1996 | |||
| Lower bounds for the path covering number of trees, p(T). | |||
| E | 9. | If T is a tree, then p(T) ≥ D(T) -1 | definitions reference |
| 2001 | |||
| E | 10. | If T is a tree, then p(T) ≥ CEIL(L(T)/2) | definitions reference |
| 2001 | |||
| E | 11. | If T is a tree, then p(T) ≥ 2a(T) - n | definitions reference |
| 2001 | |||
| E | 12. | If T is a tree, then 2a(T) - n ≥ maximum of disteven(v) - minimum of disteven(v) | definitions reference |
| 2001 | |||
| Lower bounds on the bipartite number of simple connected graphs, b(G). | |||
| T | 13. | If G is a simple connected graph, then b(G) ≥ diam(G) + maximum of l(v) -1 | definitions reference |
| July 3, 2003. DeLaVina and Waller 2004. | |||
| T | 14. | If G is a simple connected graph, then b(G) ≥ diam(G) + fG(1) -1 | definitions reference |
| July 3, 2003. DeLaVina and Waller 2003 | |||
| R | 15. | If G is a simple connected graph, then b(G) ≥ 2rad(G) | definitions reference |
| July 3, 2003. This was proven by Fajtlowicz, 1988. Waller sent an alternate proof 2003. | |||
| T | 16. | If G is a simple connected graph, then b(G) ≥ 2(rad(G)-1) + maximum of l(v) | definitions reference |
| July 3, 2003.
July 26, 2003 Bill Waller shows, by proof similar to Favaron's for a(G) ≥ rad(G), that b(G) ≥ 2rad(G) + maximum of l(v) - 5. Mar. 17, 2004: Ryan Pepper communicated that he could prove f(G) ≥ diam(G) + maximum of l(v) - 3. Note: A second run of the program was conducted for forest number (see conjectures 57-67.) Mar. 25, 2004: In a second run for forest the program conjectured f(G) ≥ diam(G) + maximum of l(v) - 2. It is conjecture 67. Nov. 25, 2006 The conjectured relation follows for a tree T since diam(T) ≥ 2rad(T) -1 and by wowII #13 it follows that b(T) ≥ diam(T) + maximum of l(v) -1. Jan. 2008: DRW | |||
| T | 17. | If G is a simple connected graph, then b(G) ≥ a(G) + CEIL(diam(G)/3) | definitions |
| July 3, 2003. Independently proven by Benny John, UHD (Dec. 2005) and David Schindl,Gerard Univ (Jan. 2006). | |||
| T | 18. | If G is a simple connected graph, then b(G) ≥ a(G) + CEIL(sqrt(distmax(M))) | definitions |
| July 3, 2003. July 2005, for large enough diameter this follows from conjecture #17. Feb. 21, 2006 Benny John generalized Schindl's proof of 17 to prove #18.. | |||
| T* | 20. | If G is a simple connected graph, then b(G) ≥ n/FLOOR[degavg(G)] | definitions reference |
| July 3, 2003.
Mar 06, 2004, Bill Waller observes that for graphs that are p-regular and Kp-free, f(G) ≥ n/FLOOR[degavg(G)] (see conjecture #50 below) follows from Fajtlowicz's result on the independence ratio that for graphs with max. degree at most p and Kq-free, a(G)/n ≥ 2/(p+q). Mar. 07, 2004, Fajtlowicz sent a proof of f(G) ≥ n/degavg(G), see conjecture #50. |
|||
| F | 22. | If G is a simple connected graph, then CEIL(2dist(B,V)))≥ CEIL(2distavg(V)) | definitions reference |
|
July 3, 2003. DeLaVina and Waller July 4, 2003; see the
counterexample (drawn with Waller's GraphDraw program) Also note this conjecture was a by-product of dalmatian implemented in Graffiti.pc. See On Some History of the Development of Graffiti (ps 32MB) (zipped ps 1MB) |
|||
| F | 23. | If G is a simple connected graph, then b(G) ≥ FLOOR[a(G) + distavg(M)/2] | definitions reference |
|
July 3, 2003. July 2005. See counterexample; b =
19, a(G)= 15, distavg(M) = 10. Note: This counterexample also serves as a counterexample to b(G) ≥ a(G) + rad(G) -1, which in our paper we listed as an open but unnumbered conjecture of G.pc. | |||
| F | 24. | If G is a simple connected graph, then b(G) ≥ l(G) + CEIL[minimum of disteven(v)/3] | definitions |
| July 3, 2003. May 27, 2004 DeLaVina. Take two copies of complete(9) and enumerate the vertices of each 0, 1, 2, ... , 8. Join vertices 3, 4, and 5 of one copy to vertices 3, 4, and 5 of the other copy; and join vertices 6, 7, and 8 of one copy to vertices 6, 7, and 8 of the other copy. Bipartite number is 4, every vertex has 7 of vertices at even distance, and maximum of local independence is 2. | |||
| F | 25. | If G is a simple connected graph, then b(G) ≥ 2CEIL[(1 + minimum of disteven(v))/3] | definitions |
| July 3, 2003. May 27, 2004 DeLaVina. Same counterexample as in #24. Bipartite number is 4, and every vertex has 7 of vertices at even distance. | |||
| F | 26. | If G is a simple connected graph, then b(G) ≥ CEIL[1 + dd(G)0.25] | definitions |
| July 3, 2003. Mar. 6, 2004. (DeLaVina) The only counterexample that I know of at the moment has over 4000 vertices. It would be helpful to know if there is a smaller one. | |||
| F | 28. | If G is a simple connected graph, then b(G) ≥ distmin(A)+ (distmin(M))0.25 | definitions |
| July 3, 2003. May 2004 see the counterexample. Bipartite number is 4, minimum distance between minimum degree vertices is 3, and minimum distance between maximum degree vertices is 2. | |||
| T | 27. | If G is a simple connected graph, then b(G) ≥ (minimum of |N(e)|)1-t(G) | definitions |
| July 3, 2003.
** Mar. 17 2004: thanks to Ryan Pepper for alerting me to a typo in this
statement. Mar. 19, 2004: Pepper sent a proof of a bound on b in terms of the degree of an edge which is stronger for triangle-free graphs, and notes that for t(G) ≥ 1, 1 ≥ (minimum of |N(e)|)1-t(G). | |||
| T | 29. | If G is a simple connected graph, then b(G) ≥ distmax(A)+ 1/(n mod D(G)) | definitions |
| July 3, 2003. The expression on the right is undefined for some graphs. The conjecture is made for those graphs for which is is defined. June 2005, this follows from b(G) ≥ diam(G)+ 1. | |||
| F | 30. | If G is a simple connected graph, then b(G) ≥ distmin(A)+ |EG(M(G))|0.25 | definitions |
| July 3, 2003. June 2005, Barbell(18,2) is a counterexample. Take two copies of K(18) and bridge them by an edge. | |||
| Lower bounds on the path number of simple connected graphs, path(G). | |||
| R | 31. | If G is a simple connected graph, then path(G) ≥ 2rad(G) - 1 | definitions reference |
| July 15, 2003. This is Chung's Lemma, see reference. | |||
| R | 31a. | If G is a simple connected graph, then path(G) ≥ 2ecc(Centers) + 1 | definitions reference |
| Summer 2003. This is offers an improvement over Chung's Theorem see wowII #31, when rad(G) = ecc(centers). June 2005, Waller noticed that conjecture follows from a Theorem of Basco and Tuza (see reference). | |||
| F | 32. | If G is a simple connected graph, then path(G) ≥ distavg(A) + 0.5 eccavg(M) | definitions |
| July 15, 2003. Aug 2005, the path on 5 vertices is a counterexample, path = 5, distavg(A) = 4 and the average of eccentricity of maximum degree vertices is 8/3; this may have resulted from an initially unnoticed computational error(s) for average of distances or eccentricities in earlier code. | |||
| F | 33. | If G is a simple connected graph, then path(G) ≥ CEIL[2distavg(M,V)] | definitions |
| July 15, 2003. Oct 2005 see the counterexample. Path number is 7,distavg(M,V = avg dist = 3.56. | |||
| R | 35. | If G is a simple connected graph, then path(G) ≥ 1 + diam(G) | definitions reference |
| July 15, 2003. This could also have been labeled an exercise, but since it was noted in the cited reference we include it here as a rediscovery. | |||
| F | 36. | If G is a simple connected graph, then path(G) ≥ 2rad(G)/dp(G) | definitions |
| July 15, 2003. DeLaVina, June 2005 see the counterexample. Path number is 5, radius is 3, and dp is 1. | |||
| Lower bounds on the forest number of simple connected graphs, f(G). | |||
| Note: |
Clearly b(G) ≥ f(G) ≥ path(G), and note that f(G)
and path(G) were not available to the program when lower bounds for b(G) were
generated.
| ||
| E | 37. | If G is a simple connected graph, then f(G) ≥ path(G) | definitions |
| Mar 05, 2004. | |||
| F | 38. | If G is a simple connected graph, then f(G) ≥ CEIL[0.5(res(G)+b(G))] | definitions |
| Mar 05, 2004. May 2004 see the counterexample. Forest number is 6, bipartite is 10, and residue is 3. | |||
| F | 39. | If G is a simple connected graph, then f(G) ≥ a(G) +CEIL[(1/3) distavg(B,V))] | definitions |
| Mar 05, 2004. Nov. 2005 As stated this conjecture is false see the counterexample, but I still think there may be a constant less than 1/3 for which the relation may be true. For the counterexample forest is 21, independence number is 20 and average distance from the boundary is slightly more than three. | |||
| F | 41. | If G is a simple connected graph, then f(G) ≥ CEIL[distavg(V)*(1 + sqrt(p(G)) ] | definitions |
| Mar 05, 2004. June 2005, binary stars with 5 leaves on each end and interior path of length at least 8 are counterexamples. Path covering number is 9, and increasing the length of the interior path increases the average distance, which shows that the difference between the left and right of the inequality can be arbitrarily large. | |||
| F | 43. | If G is a simple connected graph, then f(G) ≥ FLOOR[sqrt[path(G)*(b(G)-1)]] | definitions |
|
Mar 05, 2004. Mar 06, 2004, DeLaVina: It is easy shown that for graphs on
more than one vertex, f(G) ≥ sqrt[path(G)*(b(G)+2)/2],
since f(G) ≥ path(G) and f(G) ≥ b(G)/2
+ 1, the +1 we get for connected graphs on more than one vertex.
Mar. 6, 2004, Ryan Pepper's counterexample follows: "Take a path on 7 vertices and alternately label its vertices red and blue (pendants are red). Join both vertices of an empty graph on two vertices to every vertex that is red and take another empty graph on two vertices and join both of them to every vertex that is blue. This gives you a bipartite graph on 11 vertices. So, b(G)=11, and f(G) >= p(G) >= 7.". Further he showed that f(G) = 7. | |||
| F | 44. | If G is a simple connected graph, then f(G) ≥ a(G) + FLOOR[(1/2) average of ecc(v)] | definitions |
| Mar 05, 2004. July 2005, DeLaVina see the counterexample. Forest number is 17, independence number is 13, and average eccentricity is 12.1905. | |||
| F | 45. | If G is a simple connected graph, then f(G) ≥ FLOOR[path(G) - 1 + (1/3)(n mod D(G)) ] | definitions |
| Mar 05, 2004. Mar 06, 2004, DeLaVina: K3 with K12 attached to each vertex is a counterexample. f = 5, path = 4, n = 36, D(G) = 24. | |||
| F | 46. | If G is a simple connected graph, then f(G) ≥ FLOOR[path(G) - 1 + (1/3)(n mod D(G)) ] | definitions |
| Mar 05, 2004. Mar 06, 2004, DeLaVina: K3 with K12 attached to each vertex is a counterexample. f = 5, path = 4, n = 36, D = 13. | |||
| R | 47. | If G is a simple connected graph, then f(G) ≥ diam(G) + fG(1) -1 | definitions reference |
| Mar 05, 2004. This is a rediscovery since Waller and I knew it to be true from our work on b(G). DeLaVina and Waller 2003, see #14 above. | |||
| T | 48. | If G is a simple connected graph, then f(G) ≥ girth(G) + fG(1) -1 | definitions reference |
| Mar 05, 2004. The proof is similar to that of #47. DeLaVina and Waller 2004. *must check algorithm for circumference. | |||
| F | 49. | If G is a simple connected graph, then f(G) ≥ CEIL[ 2 + (1/6)*length(G) ] | definitions |
| Mar 05, 2004. Mar. 08, 2004, Ryan Pepper: a path on 38 vertices is a counterexample. | |||
| T* | 50. | If G is a simple connected graph, then f(G) ≥ n/FLOOR[degavg(G)] | definitions reference |
| Mar 05, 2004.
Note conj. #20 of wowII is b(G) ≥ n/FLOOR[degavg(G)].
Mar 06, 2004, Bill Waller observes that for graphs that are p-regular and Kp-free, f(G) ≥ n/FLOOR[degavg(G)] follows from Fajtlowicz's result on the independence ratio that for graphs with max. degree at most p and Kq-free, a(G)/n ≥ 2/(p+q).[F] Mar 07, 2004, DeLaVina: I came across a paper [BB] (see reference link) by Bau and Beineke on n(G) - f(G), which they called the decycling number of a graph. In their paper they cite a result of Zheng and Lu in [ZL] that for cubic graphs without triangles and n not 8, f => n - ceil[n/3] (settling a conjecture by Bondy, Hopkins and Staton [BHS].) Zheng and Lu's bound for cubic triangle-free graphs is an improvement over the above. Bau and Beineke also cite other results on the decycling number, they write "A sharp upper bound for the decycling number of cubic graphs has been obtained in [LZ] by Liu and Zhao and that for connected graphs with maximum degree 3 has been obtained in [AMT]." Mar. 07, 2004, Fajtlowicz sent a proof of f(G) ≥ n/degavg(G) "The algorithm is as the proof which essentially shows how to find a forest of size n/A, where A is the average degree. Proof: We can assume that G has no isolated points. Let's order vertices at random and starting with empty set F, let us keep adding to F a vertex v, if F + {v} is an induced forest. We add suitable vertices to F in order they are listed. Let d be the degree of v. The probability that v will eventually land in F is at least 2/(d+1), because that's the probability that v is the first or the second on the list of v +{neighbors of v}. Adding such vertices keeps F acyclic. Let f(v) = 1 if v is in F and zero otherwise. By linearity, The expected value of f is at least R = sum 1/d, where the summation is over the degree sequence D, because for d >= 1, 2/(d+1) >= 1/d. Since that is the expected value then there is at least one ordering for which |F| is at least R. This is a version of Caro-Wei bound for forests rather than the independence number and the idea of the proof is the same as Shearer's proof of their result. Let H be the harmonic mean of D, i.e., H = n/R and A the average of D. Then f >= n/A follows from the inequality of arithmetic-harmonic means which says that A >= H. f >= R f/n >= R/n = 1/H >= 1/A i.e, f >= n/A Siemion" |
|||
| F | 51. | If G is a simple connected graph, then f(G) ≥ diam(G) + FLOOR[(1/3)*dd(G) ] | definitions |
| Mar 05, 2004. Mar 06, 2004, DeLaVina: progressive-join(complete(9), complete(9)) is a counterexample. f = 4, diam = 2, dd = 9. | |||
| F | 52. | If G is a simple connected graph, then f(G) ≥ CEIL[(1/2)*[dd(G) + 1 + (n mod D(G))] ] | definitions |
| Mar 05, 2004. Mar 06, 2004, DeLaVina: progressive-join(complete(9), complete(9)) is a counterexample. f = 4, n = 18, D = 17, dd = 9. | |||
| F | 53. | If G is a simple connected graph, then f(G) ≥ 2*CEIL[modemin(G) /degavg(G)] | definitions |
| Mar 05, 2004. DeLaVina, Mar. 23, 2004; see the counterexample (drawn with Waller's GraphDraw program) | |||
| F | 54. | If G is a simple connected graph, then f(G) ≥ CEIL[distavg(V) +(1/2)*minimum of disteven(v)] | definitions |
| Mar 05, 2004. DeLaVina, Mar. 23, 2004; Take two copies of complete(9) and enumerate the vertices of each 0, 1, 2, ... , 8. Join vertices 3, 4, and 5 of one copy to vertices 3, 4, and 5 of the other copy; and join vertices 6, 7, and 8 of one copy to vertices 6, 7, and 8 of the other copy. Forest number is 4, average distance is slightly less than 1.5, but every vertex has 7 of vertices at even distance. | |||
| F | 55. | If G is a simple connected graph, then f(G) ≥ CEIL[minimum of disteven(v) -1 + |N(A)|/3], where A is the set of vertices of minimum degree. | definitions |
| Mar 05, 2004. Mar 06, 2004, DeLaVina: progressive-join(complete(9), complete(9)) is a counterexample. f = 4 and minimum of disteven(v) = 1. There are two vertices of min. degree, 10, and |N(A)| = 16. | |||
| F | 56. | If G is a simple connected graph, then f(G) ≥ CEIL[sqrt[distmax(A)*(1+degavg(G))]], where A is the set of vertices of minimum degree. | definitions |
| Mar 05, 2004. DeLaVina, Mar. 23, 2004; the counterexample to #54 is also a counterexample to #56 | |||
| 2nd run on Lower bounds on the forest number of simple connected graphs, f(G). | |||
| Note: |
Clearly b(G) ≥ f(G) ≥ tree(G) ≥ path(G), and note that
this (for the second run) time b(G), tree(G)
and path(G) were available to the program when lower bounds for f(G) were
generated;
Also for the second run for forest should reflect the counterexamples listed above
and now also includes the local independence invariants and the domination
number. conjectures 39, 42, 47 | ||
| E | 57. | If G is a simple connected graph, then f(G) ≥ tree(G) | definitions |
| Mar 25, 2004. | |||
| F | 60. | If G is a simple connected graph, then f(G) ≥ domination(G) + FLOOR[tree(G)/2] | definitions |
| Mar 25, 2004. April 22, 2006. See the counterexample. Forest number is 6, domination number is 4, and tree number is 6.. | |||
| F | 62. | If G is a simple connected graph, then f(G) ≥ domination(G) + maximum of l(v) -1 | definitions |
| Mar 25, 2004. Oct 2005 see the counterexample. Forest number is 5, domination number =3, and max local indep is 4. | |||
| T | 67. | If G is a simple connected graph, then f(G) ≥ diam(G) + maximum of l(v) -2 | definitions reference |
| Mar 25, 2004. This is related to
the discussion of conjecture 16. Mar 27, 2004. DeLaVina and Waller. | |||
| Lower bounds on the tree number of simple connected graphs, tree(G). | |||
| Note: | Clearly b(G) ≥ f(G) ≥ tree(G) ≥ path(G). | ||
| E | 68. | If G is a simple connected graph, then tree(G) ≥ path(G) | definitions |
| Apr 04, 2004. | |||
| F | 69. | If G is a simple connected graph, then tree(G) ≥ maximum of l(v) + FLOOR[sqrt(domination(G))] | definitions |
| Apr 04, 2004. May 2004 see the counterexample. Tree number is 4, maximum of local independence is 3, and domination is 4. | |||
| F | 70. | If G is a simple connected graph, then tree(G) ≥ FLOOR[distavg(C,V)] + maximum of l(v) | definitions |
| Apr 04, 2004. June 2005 see the counterexample. Tree number is 12, maximum of local independence is 11, and floor of average distance from the center is 2. | |||
| F | 71. | If G is a simple connected graph, then tree(G) ≥ FLOOR[distavg(B,V)/3] + maximum of l(v) | definitions |
| Apr 04, 2004. Oct 2005, see the counterexample. Tree number is 16, max of local independence is 15, and average distance from the boundary is slightly more than 6. . | |||
| F | 73. | If G is a simple connected graph, then tree(G) ≥ FLOOR[average of ecc(v)/2] + maximum of l(v) | definitions |
| Apr 04, 2004. June 2005 see the counterexample. Tree number is 13, maximum of local independence is 12, and average of eccentricities is 4.25. | |||
| F | 74. | If G is a simple connected graph, then tree(G) ≥ CEIL(2distavg(B,V)) | definitions reference |
| Apr 04, 2004. May 2004 DeLaVina see counterexample. | |||
| F | 75. | If G is a simple connected graph, then tree(G) ≥ b(G)/FLOOR[degavg(G)] | definitions |
| Apr 04, 2004. July 2005, DeLaVina. Take a clique on p vertices and to each vertex attach a path on p vertices by the endpoint of the path for a total of p(p+1) vertices. The tree number is 2(p+1), the bipartite number is p^2 + 2 , and the average degree is less than 3. For p at least 5, the graph serves as a counterexample. | |||
| F | 77. | If G is a simple connected graph, then tree(G) ≥ distavg(C,V) + ecc(B) + 1, where B is the set of vertices of boundary vertices. | definitions |
| Apr 04, 2004. April 22, 2006 see the counterexample. Tree number is 6, distavg(C,V) is 7/6, and ecc(B) is 4.. | |||
| F | 79. | If G is a simple connected graph, then tree(G) ≥ (n mod 2)* CEIL(2distavg(V)) | definitions |
| Apr 04, 2004. Oct 2005 see the counterexample. Path number is 7, n = 25, avg dist = 3.56. | |||
| F | 78. | If G is a simple connected graph, then tree(G) ≥ CEIL[path(G)/3 + maximum of l(v) -1] | definitions |
| Apr 04, 2004. June 2005 see the counterexample. Tree number is 7, maximum of local independence is 6, and path number is 7. | |||
| F | 80. | If G is a simple connected graph, then tree(G) ≥ CEIL[sqrt[2*sqrt[|N(M)| + 1]]], where M is the set of vertices of maximum degree of the complement of G. | definitions |
| Apr 04, 2004. Oct. 28, 2005. Large barbells, beginning with Barbell(32,2), are counterexamples; the tree number is 4 and the is |N(M)| equal to the number of the vertices. | |||
| F | 81. | If G is a simple connected graph, then tree(G) ≥ CEIL[sqrt[2*(1+sqrt[|N(A)|)]]], where A is the set of vertices of minimum degree. | definitions |
| Apr 04, 2004. This statement must have a typo, since even fairly small cliques are counterexamples. | |||
| F | 82. | If G is a simple connected graph, then tree(G) ≥ 2*CEIL[(2*ecc(B) + 1)/3], where B is the set of vertices of boundary vertices. | definitions |
| Apr 04, 2004. April 22, 2006 see the counterexample. Tree number is 8 and ecc(B) is 6. | |||
| F | 83. | If G is a simple connected graph, then tree(G) ≥ 1 + distavg(C,V) * minimum of l(v) | definitions |
| Apr 04, 2004. August 16, 2005, see the counterexample. Tree number is 6, minimum of local independence is 3, and average distance from centers is 2. | |||
| Upper bounds on the bipartite number of simple connected graphs, b(G). | |||
| E | 86. | If G is a simple connected graph, then b(G) ≤ 2 + n - w(G) | definitions |
| April 10, 2004. | |||
| F | 87. | If G is a simple connected graph, then b(G) ≤ 1 + minimum of l(v) + D(G) | definitions |
| April 10, 2004. Oct 2005, see the counterexample. Bipartite number is 8, min of local independence is 2, and D(G) = 4. | |||
| F | 88. | If G is a simple connected graph, then b(G) ≤ 1 + average of l(v) + average degree of G. | definitions |
| April 10, 2004. Dec. 2005, the join of discrete 2 and K(m,m) is a counterexample to this conjecture but it is still open as to whether or not the relation holds without the 1, that is b(G) ≤ average of l(v) + average degree of G is still open. | |||
| E | 89. | If G is a simple connected graph, then b(G) ≤ 2a(G) | definitions |
| April 10, 2004. | |||
| F | 90. | If G is a simple connected graph, then b(G) ≤ f(G) * (FLOOR[2average of l(v)])/2 | definitions |
| April 10, 2004. Oct 2005, see the counterexample. Bipartite number is 6, forest number is 5, and average of local independence is 14/9. | |||
| Upper bounds on the independence number of simple connected graphs, a(G). | |||
| R | 92. | If G is a simple connected graph, then a(G) ≤ FLOOR[( n + p)/2] | definitions reference |
| April 21, 2004. This is equivalent to conjecture #11 which as described in the reference I knew was correct for all simple graphs. | |||
| E | 93. | If G is a simple connected graph, then a(G) ≤ f(G) -1 | definitions |
| April 21, 2004. | |||
| F | 95. | If G is a simple connected graph, then a(G) ≤ CEIL[f(G) -LN(path(G))] | definitions |
| April 21, 2004. April 2006, see the counterexample. a(G) is 7, forest number is 8, and path number is 8. | |||
| T | 97. | If G is a simple connected graph, then a(G) ≤ maximum of l(v) - d(G) | definitions |
| April 21, 2004. Fajtlowicz April 2004 | |||
| F | 98. | If G is a simple connected graph, then a(G) ≤ maximum of disteven(v) + FLOOR[p(G)/2] | definitions |
| April 21, 2004. DeLaVina May 2004; see counterexample. | |||
| E | 99. | If G is a simple connected graph, then a(G) ≤ b(G) -minimum of l(v) | definitions |
| April 21, 2004. DeLaVina April 2004 | |||
| T | 101. | If G is a simple connected graph, then a(G) ≤ FLOOR[(n + alphacore(G))/2] | definitions |
| April 21, 2004. March 14, 2008. This follows from a(G) ≤ [matching(G) + alphacore(G)]/2 a result with R. Pepper. | |||
| T | 102. | If G is a simple connected graph, then a(G) ≤ CEIL[b(G) - SQRT[diam(G)]] | definitions |
| April 21, 2004. July 2005, for
large enough diameter this follows from the proposition listed below
conjecture 17.
October 12, 2006. Benny John. |
|||
| F | 104. | If G is a simple connected graph, then a(G) ≤ rad(G) + maximum of l(v) + |N(S) - S| -1, where S is the set of minimum degree vertices of the complement of the graph G and the neighborhood is taken in the complement. | definitions reference |
| April 21, 2004. Fajtlowicz April 2004. This relation was interesting in light of his theorem rad(G) + maximum of l(v) -2 ≤ a(G) in our Griggs and Graffiti paper (see reference link). #104 is false as Fajtlowicz noted "You can construct d-regular graph of small radius, say 3 or 4 with close to d^3 vertices. Then a will much more than d, but loc ind is at most d and the term |N(S) - S| is 0", see an example. He then asks for the smallest S such that a counterexample is possible. | |||
| F | 105. | If G is a simple connected graph, then a(G) ≤ tree(G)*SQRT[domination(G)] - 1 | definitions |
| April 21, 2004. April 2004.
Bill Waller proved that a(G)
≤ tree(G)*domination(G) - 1.
Nov. 2005, see the
counterexample.
Independence
number is 16, tree number is 12, and domination is 2. Note that this
counterexample belongs to a family of graphs with independence number
3k+1, tree number 2k + 2, and domination 2 for k a
positive integer. For large k, members of the family will make the
difference a(G) - tree(G)*SQRT[domination(G)]
large. |
|||
| E | 106. | If G is a simple connected graph, then a(G) ≤ n - domination(G)] | definitions |
| April 21, 2004. |
|||
| F | 107. | If G is a simple connected graph, then a(G) ≤ maximum disteven(v)* CEIL[distavg(B,V)/2] | definitions |
| April 21, 2004. Oct
2005, see the counterexample.
independence
number is 6,
maximum disteven(v) is 5, and distavg(B,V) is
about 1.99. |
|||
| F | 110. | If G is a simple connected graph, then a(G) ≤ FLOOR[(residue(G)+1)* average of l(v) - 1] | definitions |
| April 21, 2004. Oct
2005, see the counterexample.
independence
number is 7, average of local independence is 11/7, and residue is 4. |
|||
| Lower bounds on the matching number of connected bipartite graphs, m(G). | |||
| note: Graffiti.pc was asked to focus on lower bounds for the matching number, which are sharp for some connected bipartite graphs and thus some conjectures were made for all graphs (see 113 & 127) | |||
| E | 112. | If G is a connect bipartite graph, then m(G) ≥ CEILING[freq(D(G))/2] | definitions reference |
| June, 2004. DeLaVina and Gramajo June 2004. | |||
| T | 113. | If G is a simple connected graph, then m(G) ≥ CEILING[dd(G)/2] | definitions reference |
| June, 2004. DeLaVina and
Gramajo (June 2004) proved this for connected bipartite graphs. Jan 2005. Craig Larson proved this for all simple graphs with no isolated vertices. |
|||
| E | 114. | If G is a connect bipartite graph, then m(G) ≥ minimum { modemax(G), frequency of mode} | definitions reference |
| June, 2004. DeLaVina and Gramajo July 2004. In light of this and conjectures #115 and #116, we proved the more general statement m(G) ≥ minimum {d(S), |S|} | |||
| E | 115. | If G is a connect bipartite graph, then m(G) ≥ minimum {D(G), freq(D(G))} | definitions reference |
| June, 2004. DeLaVina and Gramajo July 2004. See #114. | |||
| E | 116. | If G is a connect bipartite graph, then m( |