Ermelinda DeLaVina (delavinae@uhd.edu)
| Next List | |||
| Lower bounds for maximum number of leaves over all spanning trees, Ls(G) | |||
| O | 2. | If G is a simple connected graph, then Ls(G) ≥ 2(average of l(v) - 1) | definitions reference |
| 1996 |
| Next List | |||
| Lower bounds on the bipartite number of simple connected graphs, b(G). | |||
| 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 wowII #13. | |||
| O | 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.
|
|||
| Next List |
| Lower bounds on the path number of simple connected graphs, path(G). | |||
| O | 34. | If G is a simple connected graph, then path(G) ≥ CEIL[distavg(C,V) + distavg(M,V)] | definitions |
| July 15, 2003. | |||
| 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. O (7), T(3), F(10) | ||
| 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. | |||
| O | 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)). | |||
| 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. | ||
| 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. | |||
| O | 61. | If G is a simple connected graph, then f(G) ≥ res(G)+ CEIL[diam(G)/3] | definitions |
| Mar 25, 2004. | |||
| 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. | |||
| Next List | |||
| Lower bounds on the tree number of simple connected graphs, tree(G). | |||
| Note: | Clearly b(G) ≥ f(G) ≥ tree(G) ≥ path(G). | ||
| 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. | |||
| O | 76. | If G is a simple connected graph, then tree(G) ≥ freq[Tmax(v)]/FLOOR[degavg(G)] | definitions |
| Apr 04, 2004. | |||
| 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. | |||
| Next List | |||
| Upper bounds on the bipartite number of simple connected graphs, b(G). | |||
| 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. | |||
| Next List | |||
| Upper bounds on the independence number of simple connected graphs, a(G). | |||
| 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. | |||
| 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. |
|||
| 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. | |||
| 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. |
|||
| 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. |
|||
| 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) | |||
| O | 129 | Let G be a connected X,Y bigraph such that |X| £ |Y|,. Then m(G) ≥ |X|/(D(Y)-1) | definitions |
| December 2004. | |||
|
| |||
| O | 130 | Let G be a connected X,Y bigraph such that |X| £ |Y|,. Then m(G) ≥ |X|/(S(G)-1) | definitions |
| December 2004. | |||
|
| |||
| Lower bounds on the path number of simple connected graphs, path(G). #'s 31, 31a, and 35 were repeated from 1st run for path. | |||
| O | 133. | If G is a simple connected graph, then path(G) ≥ rad(G)+ [average of l(v)]^cC4 | definitions |
| July 12, 2005. | |||
| 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. | |||
| 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). | ||
| 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. | |||
| 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. |
|||
| 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. | |||
| 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. | |||
| 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. | |||
| 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| appeared 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. | |||
| 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. | |||
| 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. | |||
| Lower bounds for Ls(G) + b(G) | |||
| 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 reference for proof of Ls(G) + b(G) ≥ n + CEIL[0.5*maximum of l(v)]. | |||
| 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. | |||
| O | 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. | |||
| 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.
| |||
| 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. | |||
| O | 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. | |||
| 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. | |||
| O | 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. | |||
| 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. | |||
| O | 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. | |||
| O | 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.... |
|||
| O | 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. | |||
| O | 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. | |||
| O | 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. | |||
| 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. | |||
| O | 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. | |||
| O | 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. | |||
| O | 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. | |||
| 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. | |||
| 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. | |||
| Dalmatian Heuristic | |||
| Lower bounds for Total Domination gt | |||
| 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 |
| Feb. 23, 2007. | |||
| O | 235. |
If G is a simple connected graph, then
gt(G)
≥
(2/3)
ecc(B)
+ cbipartite(G). |
definitions |
| Feb. 23, 2007. | |||
| O | 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. | |||
| O | 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. | |||
| 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. | |||
| 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. | |||
| 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. | |||
| O | 248. |
If G is a simple connected graph such that girth(G) ≥ 6, then
gt(G)
≥ SQRT[2*
p(G)] |
definitions |
| Feb. 23, 2007. | |||
| 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) |