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 reference |
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. In 2017, P. Mafuta proved that If G is a simple 2-connected, C4-free graph with d ≥ 0.5LS(G), then G is Hamiltonian, see reference. Feb. 2019, in 2013 in [SM] Mukwembi proved that for claw-free graphs, if δ(G) > 12(LS(G) + 1), then G is Hamiltonian. [PM] P. Mufuta, Leaf number and Hamiltonian C_4-free graphs, Afrika Matematika 28:1067-1074, 2017. [SM] S. Mukwembi, Minimum degree, leaf number and traceability, Czechoslovak Mathematical Journal, 63 (2), 539-545, 2013.
|
|||
T | 190a. | If G is a simple connected graph with n > 1 such that LS(G)-1 ≤ σ(G), then G has a Hamiltonian path. | definitions |
Jan 12, 2006.
At some point in the program's execution, this conjecture (appeared together
with #190) was eventually superseded by some combination of other conjectures,
however, since we thought about this conjecture, it is included on this
list.
June 2013, in [M1], using theorems of Griggs and Wu, and of Dirac, Mukwembi proved that if ( δ ≥ 5 ) and ( δ ≥ L -1 ), then G is Hamiltonian and in [M2] he extended this to if (δ ≥ 3 \) and \( δ ≥ L -1 \), then G is Hamiltonian. [M1] Simon Mukwembi, Minimum degree, leaf number and Hamiltonicity, American Mathematical Monthly, 115, (2013). [M2] Simon Mukwembi, On spanning cycles, paths and trees, Discrete Applied Mathematics, 2217-2222, (2013). |
|
||
T | 191. |
If G is a simple connected graph with n > 1 such that
2 * lower median of degree sequence of G - 1 ≤ min { deg(v) + deg(u) : v and u are not adjacent }, then G has a Hamiltonian path. |
definitions |
Jan 12, 2006. June 2010, Richard Stong (CCR, La Jolla). | |||
T | 192. | If G is a simple
connected graph with n > 1 such that
Σ(G) ≤ upper median of degree sequence of G, then G has a Hamiltonian path. |
definitions |
Jan 12, 2006. Note one can rewrite the
hypothesis of this conjecture as n - σ(G)
- 1 ≤ upper median of degree sequence of G], where σ(G)
is the 2nd smallest of the degree sequence of G. The following
theorem is an analogue to Chvatal's condition for hamiltonian cycle
(see D. West's Intro. to Graph Theory.) from which below it is proven
that the conjecture follows. Theorem (Chvatal's). Let G be a simple graph with degree sequence d1≤ d2≤ ...≤ dn with n at least 3. If for i < (n+1)/2 we have that di ≥ i or dn+1-i ≥ n-i. , then G has a Hamiltonian path. Lemma. If n is at least 2, then [n - σ(G) - 1 ≤ upper median of degree sequence of G] implies Chvatal's condition. Proof. Assume that n is at least 2 and n - σ(G) - 1 ≤ upper median of degree sequence of G . Observe that our assumption implies d(n+2)/2 ≥ upper median of degree sequence of G ≥ n - σ(G) - 1. If i = 1, then since the graph is connected the Chvatal's condition clearly holds. So suppose 2 ≤ i < (n+1)/2. Then clearly σ(G) ≤ di. Now, if di < i, then i ≥ σ(G) + 1, which is equivalent to n -1- σ(G) ≥ n - i. Since i < (n+1)/2, it follows that n +1 - i ≥ (n+3)/2. Thus, dn+1-i ≥ d(n+3)/2 ≥ d(n+2)/2 ≥ n - σ(G) - 1 ≥ n - i. QED
|
|||
F | 193. | If G is a simple connected graph with n > 1 such that 1+ Σ(G) ≤ frequency of λmax(G) then G has a Hamiltonian path. | definitions |
Jan 12, 2006. The Harris and Mossinghoff graph which is a smallest 2-connected and claw-free that has no hamiltonian path also served as a counterexample to Sophie's number 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. | |||
F | 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 reference |
Feb. 23, 2007. Feb 2009: DFW we can prove this for trees. 2016 Desormeaux and Henning give a counterexample, see counterexample and prove that the lowerbound holds for clique-trees. | |||
F | 244. |
If G is a simple connected graph, then
gt(G)
≥ [1 + components(<M>)]/median(G),
where <M> is the subgraph induced by the set of vertices of maximum degree. |
definitions |
Feb. 23, 2007. June 2018, E. DeLaVina & A. Melgar. | |||
F | 245. |
If G is a simple connected graph such that δ(G) ≥
3, then
gt(G)
≥
FLOOR[eccavg(M)], where M is
the set of vertices of maximum degree. |
definitions |
Feb. 23, 2007. May 4, 2007: DeLaVina. See counterexample. gt(G) = 4 and eccavg(M)=5. | |||
F | 246. |
If G is a tree, then
gt(G)
≥ m(G)
- 1 |
definitions reference |
Feb. 23, 2007.
DeLaVina March 2007: counterexample Let H be P5 with a
spike at the center vertex. Let G(k) be the union of K1,
P2 and k copies of H. Now take a K1
and join it to one vertex of degree one in each of the k+2 components
of G(k). Let the resulting graph be denoted by G(k). Then the
matching number is 3k+2, and the total domination number is 2k+2
. See G(2).
March 2007: R. Pepper proved that the size of a minimum maximal matching bounds the total domination number below for trees, see reference. |
|||
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. | |||
T | 251. |
If G is a simple connected graph such that girth(G) ≥
5, then
gt(G)
≥ 1 + upper_median(G). |
definitions reference |
Feb. 23,2007. In 2016 Desormeaux and Henning proved this conjecture, see reference. | |||
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 reference |
Feb. 23, 2007. In 2016 Desormeaux and Henning proved this this bound whenever girth ≥ 7 , see reference. | |||
F | 254. |
If G is a simple connected graph, then
gt(G)
≥ 2*|N(C)|/[maximum of {N(e):
e an edge of G}],
where C is the set of vertices that are centers of G. |
definitions |
Feb. 23, 2007. August 18, 2009. This counterexample was among the graphs in the newly augmented database of G.pc. The graph is connected, gt(G) = 3, |N(C)| = 14, and maximum of {N(e): e an edge of G} = 8. | |||
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. | |||
T | 285. |
If G is a simple connected graph such that n(G)> 2, then
gt(G) ≤ m(G)*
frequency of minimum{T(v):
v a vertex},
where T(v) is the number of triangles incident to vertex v. |
definitions |
Mar. 1, 2007.Oct 2012,
Henning and Yeo settled this conjecture in [HY] where they show that
f G is a simple connected graph such that n(G)> 2, then
gt(G) ≤ m(G)
+
frequency of minimum{T(v):
v a vertex} -1,
where T(v) is the number of triangles incident to vertex v. [HY] Michael A. Henning, Anders Yeo, Total domination and matching numbers in graphs with all vertices in triangles, Discrete Mathematics, 313 (2013) 174-181. |
|||
F | 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. Feb. 2019, in [HW17] this bound is improved to gt(G) ≤ [p(G)-1]/2 + m(G) when the graph has minimum degree is at least 3. [HW17] Michael A. Henning and Kirsti Wash, Matchings, path covers and domination, Discrete Mathematics 340 (2017), no. 1, 3207-3216. |
|||
F | 289. |
If G is a simple connected graph such that n(G)> 2, then
gt(G) ≤
p(G) + CEIL[(1/2)*b(G)] |
definitions |
Mar. 1, 2007. April 19, 2007: R. Pepper, see counterexample. | |||
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. June 8, 2012, I believe I have an argument for maximum degree 3 and n at least 12. | |||
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. It is not
difficult to see that FLOOR(n(G)/2) £ annihilation(G)
and it is known that if minimum degree is at least 3 then
gt(G) ≤
n(G)/2. Thus, if minimum degree is at least three
then
gt(G) ≤
annihilation(G).
From this we see that the only unsettled case is when minimum degree
is at most 2, which includes trees. Note that for G a tree cC4(G)
= 1, and the conjecture restricted to trees becomes
gt(G) ≤
annihilation(G)+ 1 if G is a tree. Nov 2012, Desormeaux, Haynes and Henning proved that if G is a tree on n(G)³ 2, then gt(G) ≤ annihilation(G)+ 1, see [DHH]. [DHH] Wyatt J. Desormeaux, Teresa W. Haynes and Michael A. Henning, Relating the annihilation number and the total domination number of a tree, Discrete Applied Mathematics, article in press available online Oct 2012. |
|||
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. See [CEL2011].
June 2011: in [LM2011] Vadim E. Levit · Eugen Mandrescu proved that G is a Konig-Egervary graph if and only if every maximum independent set is critical. [CEL2011] C.E. Larson, The critical independence number and an independence decomposition, European Journal of Combinatorics, Vol. 32, Issue 2, February 2011, pp. 294-300. [LM2011] V. Levit and E. Mandrescu, Critical Independent Sets and König–Egerváry Graphs, Graphs and Combinatorics, 2011 pp. 1-8. |
|||
Dalmatian Heuristic | |||
Upper bounds on Total Domination number gt of a Tree | |||
R | 330. |
If T is a tree on n > 2 vertices, then
γt ≤ κv(T) + number of isolated vertices of T γt ≤ n(T) - Δ(T) - 1 + 3/rad(T) γt ≤ ⌈ ((2/3)(n(T)-1))⌉ γt≤ 2γ(T) γt ≤ n(T) - γ(T) γt ≤ γ2(T) |
definitions |
Feb. 18, 2009. 6 of the 20 upper bounds were obvious rediscoveries, but for completion I list them here. Note, that they appeared on the list implies that the others on the list did not follow from the rediscoveries. | |||
T | 331. |
If T is a tree on n > 2 vertices,
then γt
≤ 2α(T) - number of isolates of <N(S(T))>, where S(T) is the set of support vertices of T
|
definitions |
Feb. 18, 2009. Mar 3,
2009 B. Waller. Note: γt ≤ 2α(G) is an exercise for all simple graphs. |
|||
T | 332. |
If T is a tree on n > 2 vertices, then γt
≤ ½[n(T) + number of isolates of <S(T)>], where S(T) is the set of support vertices of T. |
definitions reference |
Feb. 18, 2009. April 2009,
this conjecture
proposes a strengthening of a result of Chellali & Haynes that for a tree
γt
≤ ½[n(T) + |S(T)|]. In [DLPW2], we prove the stronger bound that
for a non-star tree
γt
≤ (n + |S*(T)|)/2 - (L - |S(T)| )/2.
[DLPW2] E. DeLaVina, C. E. Larson, R. Pepper, & B. Waller, On total domination and support vertices of a tree, preprint 2009. |
|||
T | 333. | If T is a tree on n > 2
vertices, then γt
≤ |S(T)| + ⌈ κv(T)/2 ⌉, where
S(T) is the set of support vertices of T.
|
definitions |
Feb. 18, 2009. April 2009, since κv(T)
= n(T)-L, this conjecture proposes a strengthening of a result of
Chellali & Haynes that for a tree
γt
≤ ½[n(T) + |S(T)|]. Note for a non-star tree |S(T)| + κv(T)/2
= |S(T)| + (n(T)-L)/2
= (n + |S(T)|)/2 - (L - |S(T)|)/2. So this too proposes and
improvement over Chellali & Haynes that for a tree
γt
≤ ½[n(T) + |S(T)|]. In [DLPW2], we prove the stronger bound that for a
non-star tree γt
≤ (n + |S*(T)|)/2 - (L - |S(T)| )/2. [DLPW2] E. DeLaVina, C. E. Larson, R. Pepper, & B. Waller, On total domination and support vertices of a tree, preprint 2009. |
|||
T | 334. | If T is a tree on n > 2 vertices, then γt ≤ number of isolates of <S(T)> + vc(T), where S(T) is the set of support vertices of T. | definitions |
Feb. 18, 2009. July 2009. [DLPW2] E. DeLaVina, C. E. Larson, R. Pepper, & B. Waller, On total domination and support vertices of a tree, preprint 2009. |
|||
F | 335. | If T is a tree on n > 2 vertices with degree 2 vertices, then γt ≤ number of isolates of <S(T)> + γ(T) * order of a largest component of <D2>, where S(T) is the set of support vertices of T and D2={v| deg(v) = 2} | definitions |
Feb. 18, 2009. May 2009, P. Feit's 34-vertex counterexample to conjecture 240 is also a counterexample to 335. Note γt(T)= 14, γ(T)=13 and all degree 2 vertices are isolates. | |||
F | 336. | If T is a tree on n > 2
vertices, then γt
≤ number of isolates of <S(T)> + γ(T) + |EB(T)| ,
where EB(T) = {(uv}=e ∈E(T): deg(u)=deg(v)} called here the balanced edges of the graph. |
definitions |
Feb. 18, 2009. May 2009, a larger version of P. Feit's 34-vertex counterexample to conjecture 240 is also a counterexample to 336. Note γt(T)= 18, γ(T)=17 and no edges are balanced. | |||
F | 337. | If T is a tree on n > 2 vertices, then γt ≤ |S(T)| + ⌈ half of nonzero minimum of maximum{k, |Dk(T)|}⌉, where S(T) is the set of support vertices of T and Dk(T) = {v: deg(v) =k} | definitions |
Feb. 18, 2009. May 2009, there must have been an issue in my interpretation of the conjecture or a computational error, since there is a 9 vertex counterexample. | |||
F | 338. | If T is a tree on n > 2 vertices, then γt ≤ diam(T)* ⌈|S(T)|/3⌉ | definitions |
Feb. 18, 2009. May 2009, there must have been an issue in my interpretation of the conjecture or a computational error, since there is an 11 vertex counterexample. | |||
F | 339. | If T is a tree on n > 2 vertices, then γt ≤ ecc(B) + modemax(T)* γ(T) | definitions |
Feb. 18, 2009. May 2009, this counterexample has γt(T)= 10, ecc(B)=3, γ(T) = 6 and modemax(T) = 1. | |||
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. |
|||
T | 347. | If T is a tree on n > 2 vertices, then γT(T) ≥ half of order of a largest component of <D2(T)> + -1 +|S(T)|, where D2={v| deg(v) = 2} and S(T) is the set of support vertices of T. | definitions |
Feb. 18, 2009. 2012 Hongxing Jiang. | |||
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. | |||
T | 349. | If T is a tree on n>2 vertices, then γT(T) ≥ rad(T) -1 + number of components of <N(D2(T)) ∪ D2(T) >, where D2={v| deg(v) = 2}. | definitions |
Feb. 18, 2009. 2012 Hongxing Jiang. | |||
T | 350. | If T is a tree on n>2 vertices, then γT(T) ≥ ½[diam(T) + number of components of <N(D2(T)) ∪ D2(T) >], where D2={v| deg(v) = 2}. | definitions |
Feb. 18, 2009. 2012 Hongxing Jiang. | |||
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 |
Feb. 18, 2009. | |||
T | 355. | If T is a tree on n>2 vertices, then γT(T) ≥ κv/(ecc(C) - 1), where C is the center of T. | definitions |
Feb. 18, 2009.
Feb. 2009: R. Pepper.
Note: if ecc(C) > 2, then this follows from γT(T) ≥ ⌈ 1 + ½*κv⌉ (Chellali & Haynes [CH2]). So it was enough to prove this for ecc(C) = 2. |
|||
O | 356. | If T is a tree on n>2 vertices, then γT(T) ≥ |C|* distavg(L) , where C is the center of T and L is the set of leaves of T. | definitions |
Feb. 18, 2009. | |||
T | 357. | If T is a tree on n>2 vertices, then γT(T) ≥ ecc(C) + |N(B)| -1 , where C is the center of T and B is the boundary of T. | definitions |
Feb. 18, 2009. Feb. 2009: DPW. | |||
O | 358. | If T is a tree on n>2 vertices, then γT(T) ≥ ½ * ecc(C) + number of isolates of <S(T)> , where C is the center of T and S(T) is set of support vertices of T. | definitions |
Feb. 18, 2009. | |||
O | 359. | If T is a tree on n>2 vertices, then γT(T) ≥ ½ * ecc(C) + number of components of <S(T) ∪ L> , where C is the center of T, S(T) is set of support vertices of T and L is the set of leaves. | definitions |
Feb. 18, 2009. | |||
O | 360. | If T is a tree on n>2 vertices, then γT(T) ≥ number of components of <S(T) ∪ L> + ½ * distavg(C,V), where C is the center of T, S(T) is set of support vertices of T and L is the set of leaves. | definitions |
Feb. 18, 2009. | |||
O | 361. | If T is a tree on n>2 vertices, then γT(T) ≥ number of isolates of <S(T)> + |C|, where S(T) is the set of support vertices of T and C is the center of T. | definitions |
Feb. 18, 2009. | |||
O | 362. | If T is a tree on n>2 vertices, then γT(T) ≥ number of components of <S(T) ∪ L> + 1⁄3 * [1 + rad(T)], where S(T) is set of support vertices of T and L is the set of leaves. | definitions |
Feb. 18, 2009. | |||
O | 363. |
If T is a tree on n>2 vertices, then γT(T) ≥ number of isolates of <S(T)> + ½ * distavg(B), where S(T) is the set of support vertices of T and B is the boundary of T. |
definitions |
Feb. 18, 2009. | |||
O | 364. | If T is a tree on n>2 vertices, then γT(T) ≥ |S(T)| + ½ * |E(D2(T))|. | definitions |
Feb. 18, 2009. | |||
O | 365. | If T is a tree on n>2 vertices, then γT(T) ≥ number of isolates of <S(T)> + 1⁄3 * |E(D2(T))|. | definitions |
Feb. 18, 2009. | |||
T | 366. | If T is a tree on n>2 vertices, then γT(T) ≥ 2⁄3 *dd(T). | definitions |
Feb. 18, 2009. Feb. 2009. DLPW | |||
O | 367. | If T is a tree on n>2 vertices such that the most frequently occurring degree is two, then γT(T) ≥ 4⁄3 *dd(T). | definitions |
Feb. 18, 2009. | |||
F | 368. | If T is a tree on n>2 vertices, then γT(T) ≥ 1 + k, where k corresponds to the kth step for a zero in the Havil-Hakimi process of a degree sequence. | definitions |
Feb. 18, 2009. April 27, 2009: Pepper & Waller see counterexample for which γT(T) = 8 and k = 8. | |||
O | 369. | If T is a tree on n>2 vertices, then γT(T) ≥ ddmode(T) + (n mod 2)*k, where k corresponds to the kth step for a zero in the Havil-Hakimi process of a degree sequence. | definitions |
Feb. 18, 2009. | |||
T | 370. | If T is a tree on n>2 vertices, then γT(T) ≥ 2μ'(T)/Δ(T), where μ(G) denotes the matching number of G, and we define μ'(T) = maximumv∈V{ deg(v) + μ(<V(T) - N(v)>). | definitions |
Feb. 18, 2009. 2012 Hongxing Jiang. | |||
T | 371. | If T is a tree on n>2 vertices, then γT(T) ≥ 2vc(T)/Σ(T) | definitions |
Feb. 18, 2009. August 2009, if
Σ(T)=2 or
Σ(T)=1, then T is a path or star, and the relation
clearly holds. So assume
Σ(T) ≥ 3. In [DLPW2], we prove that
γT(T) ≥ vc(T) - (k-1)
where k is the number of components of the subgraph induced by a
minimum total dominating set.
Since k £
γT(T)
/2, -k
≥
-γT(T)/2.
Now by the above
γT(T) ≥ vc(T) - (k-1) ≥
vc(T)
-γT(T)/2
+1,
which yields
γT(T) ≥ (2/3)(vc(T)
+1). Since we can assume that Σ(T)≥ 3, the
conjecture follows. [DLPW2] DeLaVina, Larson, Pepper, and Waller, On total domination and support vertices of a tree, preprint 2009. |
|||
O | 372. | If T is a tree on n>2 vertices, then γT(T) ≥ vc(T)/(p(T) - 1) | definitions |
Feb. 18, 2009. August 2009, similar to the argument above for Conjecture 371, when p(T) ≥ 3, the conjecture follows from γT(T) ≥ (2/3)(vc(T) +1). | |||
O | 373. | If T is a tree on n>2 vertices, then γT(T) ≥ 2⁄3 *distavg(B,V), where B is the set of vertices of maximum eccentricity | definitions |
Feb. 18, 2009. | |||
O | 374. | If T is a tree on n>2 vertices, then γT(T) ≥ distavg(B) + median(T) | definitions |
Feb. 18, 2009. | |||
O | 375. | If T is a tree on n>2 vertices, then γT(T) ≥ ecc(B) + lower median(T) | definitions |
Feb. 18, 2009. | |||
O | 376. | If T is a tree on n>2 vertices, then γT(T) ≥ number of isolates of <M> + |Dmin-total(T)|, where Dmin-total(T) = {v: Tdist(v) is minimum}. | definitions |
Feb. 18, 2009. | |||
O | 377. | If T is a tree on n>2 vertices, then γT(T) ≥ number of isolates of <M> + upper median(T). | definitions |
Feb. 18, 2009. | |||
O | 378. | If T is a tree on n>2 vertices, then γT(T) ≥ number of components of <M> + distavg(D2(T)). | definitions |
Feb. 18, 2009. | |||
O | 379. | If T is a tree on n>2 vertices, then γT(T) ≥ number of components of <M> + 1⁄3 *dd(T). | definitions |
Feb. 18, 2009. DPW: we can show that γT(T) ≥ number of components of <M> + 1. | |||
O | 380. | If T is a tree on n>2 vertices, then γT(T) ≥ |Deven(T)|/(ecc(C) - 1), where C is the center of T and Deven(T) is the set of vertices whose degree is an even number. | definitions |
Feb. 18, 2009. | |||
O | 381. | If T is a tree on n>2 vertices, then γT(T) ≥ number of isolates of <N(S(T))>/(Δ(S(T))-1) | definitions |
Feb. 18, 2009. | |||
Dalmatian Heuristic | |||
Upper bounds on 2-domination number g2 of a connected graph | |||
T | 382a. |
If G is a connected graph n > 2 vertices, then
γ2 ≤ 2a-ac. |
definitions |
Jan. 2010. DeLaVina & Hemmati.
It is easy to see that γ2
≤ 2a,
and the independence
number is not an upper bound for the 2-domination number; so we note the
corollary, if G has a unique maximum independent set, then γ2
≤ a. In
[DLPW3] we simplified the proof. [DLPW3] DeLaVina, Larson, Pepper, and Waller, Graffiti.pc on the 2-domination number of a tree, preprint 2009. |
|||
O | 382b. |
Let G be a connected graph n > 2 vertices.
γ2 ≤ -1 + a*(d + |A1|) , where d is the minimum degrees and A1 is the set of vertices that are adjacent to exactly one non-minimum degree vertex. |
definitions |
Jan. 2010. The only cases that do
not follow from γ2
≤ 2a
are when d=2
and
|A1| =
0,
or
d=1 and
|A1| =
1.
In either case, if the independence-core is not empty, γ2
≤ 2a-ac
≤ 2a -
1. Here is an
example
of a graph for which the conjectured relation is sharp,
d=1,
|A1| =
1
and ac=0.
|
|||
O | 382c. |
If G is a connected graph n > 2 vertices, then
γ2 ≤ [a*eccavg(A)+ |B|]/2, where A is the set of minimum degree vertices and B is the set of periphery vertices. |
definitions |
Jan. 2010. A special case of this would suggest a sufficient condition for γ2 ≤ a + |B|/2. Namely, if the minimum degree vertices have eccentricity two, then γ2 ≤ a + |B|/2. Here is an example of a graph for which the conjectured relation is sharp, there is one minimum degree vertex of eccentricity 2, d=3, |B| = 2, a=3, and γ2 = 4. If the average of the eccentricities of the minimum degree vertices is at least four then this follows from γ2 ≤ 2a.
|
|||
O | 382d. |
If G is a connected graph n > 2 vertices, then
γ2 ≤ [diam(G)(a+ |X|)]/2, where X is the set of vertices whose local independence is maximum. |
definitions |
Jan. 2010. A special case of this would suggests that if the diameter of G is two, then γ2 ≤ a + |X|. Here is an example of a graph for which the conjectured relation is sharp, diam(G) = 2, |X| = 1, a=3, and γ2 = 4. If the diameter at least four then this follows from γ2 ≤ 2a. |
|||
O | 382e. |
If G is a connected graph n > 2 vertices, then
γ2 ≤ Maxine + γ. |
definitions |
Jan. 2010. March 2010 DeLaVina, Larson & Pepper observe that it is easily proven that γk+1 - γk≤ a , from which one sees that γ2 ≤ a + γ. Later in [DLPW3] we proved that γa+b ≤ γa+ab, where is ab the b-independence number (the order of a largest subset of vertices that induces a subgraph with maximum degree at most b-1). | |||
F | 382f. |
Let G be a connected graph n > 2 vertices.
γ2 ≤ a + |A|*ck4., where A is the set of vertices that achieve the minimum of local independence and ck4 is the number of vertices incident to the most K4 subgraphs. |
definitions |
Jan. 2010. DeLaVina March 2010: the counterexample has γ2 = 17, a = 13, l=1 and ck4 =1 | |||
T | 383a. |
If G is a connected graph n > 2 vertices, then
γ2 ≤ n - a (G[A]), where A is the set of non-minimum degree vertices. |
definitions |
Jan. 2010. Feb. 2010 DPW. This together
with conjecture 384 led us to the stronger statement. If G is a connected graph n > 2 vertices, then γ2
≤ n
- a (G[A]), where A is the set of
non-pendant vertices.
Pepper later generalized this & 383b to If G is a connected graph n > 2 vertices, then γk ≤ n - a (G[Ak]), where Ak is the set of vertices of degree at least k. (see [DLPW3]) |
|||
T | 383b. |
If G is a connected graph n > 2 vertices, then
γ2 ≤ n - a + |P|, where P is the set of pendants (i.e. vertices of degree 1). |
definitions |
Jan. 2010. DPW. This together
with conjecture 384 led us to the stronger statement. If G is a connected graph n > 2 vertices, then γ2 ≤ n - a (G[A]), where A is the set of non-pendant vertices. Pepper later generalized this and 383a to If G is a connected graph n > 2 vertices, then γk ≤ n - a (G[Ak]), where Ak is the set of vertices of degree at least k. (see [DLPW3]) |
|||
T | 384a. |
If G is a connected graph on n > 2 vertices and
kv
cut vertices, then
γ2 ≤ FLOOR(n - kv/2). |
definitions |
Jan. 2010. March 2010 (see [DLPW3]).. | |||
O | 384b. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ FLOOR(n - |T |/2), where T = {k : some vertex of G has exactly k triangles incident to it}. |
definitions |
Jan. 2010. See an
example of
graph for which this is sharp and no other conjecture on this 2-domination
is sharp.
|
|||
E | 385a. |
If G is a connected graph n > 2, then
γ2 ≤ n - D(G[N(M)-M]). where M is the set of maximum degree vertices. |
definitions |
Jan. 2010. DeLaVina, Feb 2010. Inspired by 385a,b&c, a more general statement follows, namely, If G is a connected graph n > 2, then γ2 ≤ n - D(G[N(S)-S]). where S is any subset of vertices . | |||
E | 385b. |
If G is a connected graph n > 2, then
γ2 ≤ n - D(G[N(Ad )-Ad ]). where Ad is the set of minimum degree vertices. |
definitions |
Jan. 2010. DeLaVina, Feb 2010. Inspired by 385a,b&c, a more general statement follows, namely, If G is a connected graph n > 2, then γ2 ≤ n - D(G[N(S)-S]). where S is any subset of vertices . | |||
E | 385c. |
If G is a connected graph n > 2, then
γ2 ≤ n - D(G[N(B)-B]). where B is the set of periphery vertices. |
definitions |
Jan. 2010. DeLaVina, Feb 2010. Inspired by 385a,b&c, a more general statement follows, namely, If G is a connected graph n > 2, then γ2 ≤ n - D(G[N(S)-S]). where S is any subset of vertices . | |||
E | 386a. |
If G is a connected graph on n > 2, then
γ2 ≤ n - maximum{|N(u) Ç N(u)| : u and v distinct vertices of G }. |
definitions |
Jan. 2010. DeLaVina Feb. 2010 | |||
E | 386b. |
If G is a connected graph on n > 2, then
γ2 ≤ 2(n - S(G)). where S(G) is the 2nd largest entry of the ordered (non-decreasing) degree sequence. |
definitions |
Jan. 2010. March 2010 DLPW. | |||
O | 387. |
If G is a connected graph on n > 2, then
γ2 ≤ n - m + 1. where m is the (upper) median of the degree sequence. |
definitions |
Jan. 2010. May 2010 we have proved partial results on this; see [DLPW3]. | |||
T | 388. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ (n + a (G[A2 ]))/2, where A2 is the set vertices of degree at most two. |
definitions |
Jan. 2010. March 11, 2010 DeLaVina, Pepper & Vaughan. May 18, 2010. M. Henning & W. Goddard communicated an independent proof of this conjecture. | |||
O | 389a. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ |M|*(q + |A2|) -1, where A2 is the set vertices of degree at most two, M is the set of vertices of modemin degree and q is the 1st quartile degree . |
definitions |
Jan. 2010. | |||
F | 389b. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ q*|M| + a (G[A2]), where A2 is the set vertices of degree at most two, M is the set of vertices of modemin degree and q is the 1st quartile degree . |
definitions |
Jan. 2010. DeLaVina March 2010: the counterexample has γ2 = 9, q = 1, |M|= 4 and a (G[A]) = 4. | |||
T | 390. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ p(G) + m(G). |
definitions |
Jan. 2010. Feb. 2010 DeLaVina, Pepper & Waller see [DLPW3]. | |||
O | 391. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ p(G) + 1 + m(G[T]) + |E(G[A3])|, where T is the set vertices of degree two and A3 is the set of vertices of degree at least three. |
definitions |
Jan. 2010. | |||
T | 392a. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ m(G[A3]) + |V-A3|, where A3 is the set vertices of degree at least three. |
definitions |
Jan. 2010. March 11,
2010. DeLaVina, Pepper & Vaughan. Our argument generalized to
γk ≤ m(G[A2k-1]) + |V-A2k-1|, where A2k-1 is the set vertices of degree at least 2k-1. May 18, 2010. M. Henning & W. Goddard communicated another independent proof of this conjecture and its generalization. Note: In an effort to organize conjectures, I've grouped all involving matching and small degrees under 392. |
|||
O | 392b. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ m(G[V - Ad ]) + |Ad | + |{v : |N(v) Ç A2 | = 1}| , where Ad is the set of vertices of minimum degree and A2 is the set of vertices of degree 2. |
definitions |
Jan. 2010. | |||
O | 392c. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ m(G[V - Ad ]) + |Ad | + kv(G), where Ad is the set of vertices of minimum degree and kv is the number of cut vertices. |
definitions |
Jan. 2010. Note: For trees this follows trivially since |V| ≤ m(G[V - L ]) + |L | + |V| - |L| = m(G[V - L ]) + |L | + kv(G). | |||
O | 392d. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ m(G) + m(G[V - N(N(P))]) + |Ad |, where Ad is the set of vertices of minimum degree and P is the set of pendants. |
definitions |
Jan. 2010. Note: If minimum degree is at least three, then this follows from conjecture 392a. | |||
O | 392e. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ m(G) + m(G[N(A2)]) + |Ad |, where Ad is the set of vertices of minimum degree and A2 is the set vertices of degree two. |
definitions |
Jan. 2010. Note: If minimum degree is at least three, then this follows immediately from conjecture 392a. | |||
O | 392f. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ m(G) + m(G[N(A2)]) + |{v : |N(v) Ç N(A) | = 1}|, where A is the set of vertices of minimum degree and A2 is the set vertices of degree two. |
definitions |
Jan. 2010. Note: If minimum
degree is at least three, then this follows from conjecture 392a.
|
|||
O | 393a. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ | V - N(N(P))| + m(G[N(N(P))]) + |P |, where P is the set of pendants. |
definitions |
Jan. 2010. Note: If minimum degree is greater than one, then this follows trivially. | |||
O | 393b. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ | V - N(N(P))| + |E(G[N(P)]) | + |{v : |N(v) Ç N(P) | = 1}|, where P is the set of pendants. |
definitions |
Jan. 2010. Note: If
minimum degree is greater than one, then this follows trivially.
|
|||
O | 393c. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ | V - N(N(P))| + |N(P) | + |{v : |N(v) Ç N[P] | = 1}|, where P is the set of pendants. |
definitions |
Jan. 2010. Note: If minimum degree is greater than one, then this follows trivially. | |||
O | 393d. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ µ(G[V - N(N(P))]) + a (G[V-M]) + |M4|, where P is the set of pendants, M is the set of maximum degree vertices and M4 is the set of vertices each of which is incident with the maximum number of K4. |
definitions |
Jan. 2010. Note: If
minimum degree is greater than one, then this follows trivially.
|
|||
O | 394. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ m(G) + |E(G[A2])| + |M |, where M is the set of vertices of min local independence and A2 is the set vertices of degree two. |
definitions |
Jan. 2010. | |||
O | 395a. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ |M| + m(G[V-Ad ]) + m(G[N(A2)]), where M is the set of vertices of modemin degree, Ad is the set of minimum degree vertices and A2 is the set vertices of degree two. |
definitions |
Jan. 2010. | |||
O | 395b. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ |M |+ d(G[V-A]) + |V-A3|, where M is the set of vertices of modemin degree, A is the set of minimum degree vertices and A3 is the set vertices of degree at least three. |
definitions |
Jan. 2010. | |||
O | 396. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ ddmode + |M | + |E(A3, V-A3)|, where M is the set of vertices of modemin degree and A3 is the set vertices of degree at least three. |
definitions |
Jan. 2010. | |||
T | 397a. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ |V - N(P)| + |{v : |N(v) Ç [V - N(P)] | = 1}| , where P is the set of pendants. |
definitions |
Jan. 2010. March 20101. DeLaVina Proof: If minimum degree is greater than one, then this follows trivially. So assume P is not empty. Let D' = {v : | N(v) Ç [V - N(P)]| =1}. Then V-N(P) is a 2-dominating set unless some vertex v in N(P) is adjacent to only one vertex in V-N(P), but then v is in D'. Thus, [V-N(P)] È D' is a 2-dominating set. qed. [DLPW3] | |||
T | 397b |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ |V - N(P)| + m(G[N(P)]) , where P is the set of pendants. |
definitions |
Jan. 2010. April
2010 [DLPW3].
|
|||
O | 397c |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ |V - N(P)| + γ(G2), where P is the set of pendants. |
definitions |
Jan. 2010. If minimum degree
is greater than one, then this follows trivially.
|
|||
O | 398. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ |E(G[V - NN((P))])| + |{v : |N(v) Ç [V - N(P)] | = 1}| + |E(P,V-P)| , where P is the set of pendants. |
definitions |
Jan. 2010. Note: If minimum degree is greater than one, then this follows trivially. | |||
O* | 399a. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ WP(G) + FLOOR[a (G[C])/2], where C is the center. |
definitions |
Jan. 2010. Early in the
run for this batch of conjectures the program conjectured γ2
≤ WP(G)
+ 1 and later added 399a and 399b, which are attempts to suggest
sufficient conditions for when γ2
≤ WP(G). *May 2012, in [DP12] we proved that a2 ≤ WP(G) + 1, so here (since γ2 ≤ a2 ) it simply remains to settle γ2 ≤ WP(G) whenever the a (G[C]) = 1. [DP12] E. DeLaVina, R. Pepper, Graffiti.pc on the 2-independence number of a graph, preprint 2012. |
|||
O* | 399b. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ WP(G) + FLOOR[3/a (G[A3])], where A3 is the set vertices of degree at least three. |
definitions |
Jan. 2010. Early in the
run for this batch of conjectures the program conjectured γ2
≤ WP(G)
+ 1 and later added 399a and 399b, which are attempts to suggest
sufficient conditions for when γ2
≤ WP(G). *May 2012, in [DP12] we proved that a2 ≤ WP(G) + 1, so here (since γ2 ≤ a2 ) it simply remains to settle γ2 ≤ WP(G) whenever the a (G[A3]) ³ 4. [DP12] E. DeLaVina, R. Pepper, Graffiti.pc on the 2-independence number of a graph, preprint 2012. |
|||
O | 399c. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ (2/3)WP(G) + 2|M|, where M is the set vertices of minimum local independence. |
definitions |
Jan. 2010. | |||
F | 400a. |
If G is a connected graph on n > 2 vertices, then
γ2 ≤ A(G) + FLOOR[1/ddk4], where A(G) is the annihilation number and ddk4 is the number of different values that occur in the sequence k1, k2, ...kn where ki is the number of K4 incident to vertex i. |
definitions |
Jan. 2010. Early in the
run for this batch of conjectures the program conjectured γ2
≤ A(G)
+ 1 and later added 400a, 400b and 400c which seem attempts to suggest
sufficient conditions for when γ2
≤ A. April 2020, in [YZKS19] it is shown that the 2-domination can be artitrarily larger than the annihilation number. Let k be at least 4; one family which we will call G(4,k) of their counterexamples is found by taking k /ge 4 copies of a cycle on 4 verties and adding a vertex w and connecting w with an arbitrary but fixed vertex in each cycle, and lastely add an pendant to each vertex of degree 2. The number of vertices of G(4,k) is 7k+1, γ2(G(4,k)) = 5k , A(G(4,k)) = 4k + FLOOR(2k/3) and the difference is FLOOR(k/3); see counterexample. Feb. 2019, in [DHR14] Desormeaux et. al, proved that for trees the following holds γ2 ≤ A(G) + 1. [DHR14] Desormeaux WJ, Henning MA, Rall DF, Yeo A (2014) Relating the annihilation number and the 2-domination number of a tree. Discrete Math 319: 15–23. [YZKS19] Jun Yue, Yiping Zhu, Sandi Klavzar and Yongtang Shi (2019) The annihilation number does not bound the 2-domination number from the above, Discrete Math, article in press. |
|||
F | 400b. |
Let G be a connected graph on n > 2 vertices. Then
if G has more than n(n-1)/4 edges, then γ2 ≤ A(G) + (n mod 3 ), if G has at most n(n-1)/4 edges, then γ2 ≤ A(G) + (n mod 3 )+ 1, where A(G) is the annihilation number . |
definitions |
Jan. 2010. Early in the
run for this batch of conjectures the program conjectured γ2
≤ A(G)
+ 1 and later added 400a, 400b and 400c which seem attempts to suggest
sufficient conditions for when γ2
≤ A. April 2020, in [YZKS19] it is shown that the 2-domination can be artitrarily larger than the annihilation number. Let k be at least 4; one family which we will call G(4,k) of their counterexamples is found by taking k /ge 4 copies of a cycle on 4 verties and adding a vertex w and connecting w with an arbitrary but fixed vertex in each cycle, and lastely add an pendant to each vertex of degree 2. The number of vertices of G(4,k) is 7k+1, γ2(G(4,k)) = 5k , A(G(4,k)) = 4k + FLOOR(2k/3) and the difference is FLOOR(k/3). Feb. 2019, in [DHR14] Desormeaux et. al, proved that for trees the following holds γ2 ≤ A(G) + 1. [DHR14] Desormeaux WJ, Henning MA, Rall DF, Yeo A (2014) Relating the annihilation number and the 2-domination number of a tree. Discrete Math 319:15–23.[YZKS19] Jun Yue, Yiping Zhu, Sandi Klavzar and Yongtang Shi (2019) The annihilation number does not bound the 2-domination number from the above, Discrete Math, article in press. |
|||
O* | 400c. |
Let G be a connected graph on n > 2 vertices. Then γ2
≤ FLOOR[3A(G)
/dispmin],
where A(G) is the annihilation number . |
definitions |
Jan. 2010. Early in the
run for this batch of conjectures the program conjectured γ2
≤ A(G)
+ 1 and later added 400a, 400b and 400c which seem attempts to suggest
sufficient conditions for when γ2
≤ A.
Feb. 2019, in [DHR14] Desormeaux et. al, proved that for trees the following holds γ2 ≤ A(G) + 1. [DHR14] Desormeaux WJ, Henning MA, Rall DF, Yeo A (2014) Relating the annihilation number and the 2-domination number of a tree. Discrete Math 319:15–23. |
|||
O | 401a. |
Let G be a connected graph on n > 2 vertices. Then
γ2 ≤ 1+ FLOOR[Tdistmax/dispavg].
|
definitions |
Jan. 2010.
|
|||
O | 401b. |
Let G be a connected graph on n > 2 vertices. Then
γ2 ≤ FLOOR[3*Tdistmax / freq[Tmax(v)]]. |
definitions |
Jan. 2010.
|
|||
O | 402. |
Let G be a connected graph on n > 2 vertices. Then
γ2 ≤ 2[isolates(G[Ad ]) + |{v : |N(v) Ç AD | = 1}| + γt ] , where Ad is the set of vertices of minimum degree and AD is the set of maximum degree vertices. |
definitions |
** | Jan. 2010.
|
||
Dalmatian Heuristic | |||
Bounds on sets related to H (the union of all maximum critical independent sets) for trees. | |||
T | 403. | Let G be a tree on n > 2 vertices and H the union of all maximum critical independent sets of G. Then number of isolates(G[H]) = ac(G). | definitions |
Jan. 2010. Larson proved that this identity holds for Konig-Egarvy graphs. | |||
O | 404. | Let G be a tree on n > 2 vertices and H the union of all maximum critical independent sets of G. Then number of peN(H) ≤ 2(|S|-1), where S is the set of support vertices of G. | definitions |
Jan. 2010. | |||
O | 405. | Let G be a tree on n > 2 vertices and H the union of all maximum critical independent sets of G. Then number of peN(H) ≤ 2a(G[V-L]), where L is the set of leaves of G. | definitions |
Jan. 2010. | |||
O | 406. | Let G be a tree on n > 2 vertices and H the union of all maximum critical independent sets of G. Then number of peN(H) ≤ peN(V-L) - 2, where L is the set of leaves of G. | definitions |
Jan. 2010. | |||
O | 407. | Let G be a tree on n > 2 vertices and H the union of all maximum critical independent sets of G. Then number of peN(H) ≤ 2p(G). | definitions |
Jan. 2010. | |||
Dalmatian Heuristic | |||
Upper Bounds on the order of H (the union of all maximum critical independent sets) for connected graphs. | |||
T | 408. | Let G be a connected graph on n > 2 vertices and H the union of all maximum critical independent sets of G. Then |H| ≤ 2a(G[V-N(P)]) - ac(G). | definitions |
June 2010. June 2010, DeLaVina&Larson, note that a(G[V-N(P)]) = a(G) unless G has a component of P2, thus the conjecture is equivalent to |H| ≤ 2a(G) - ac(G), which we prove and also characterize that the graphs for which equality holds are Konig-Egervary graphs. | |||
T | 409a. | Let G be a connected graph on n > 2 vertices; let M be the set of maximum degree vertices and H the union of all maximum critical independent sets of G. If D(G) > n/2, |H| ≤ n-|M|. | definitions |
June 2010. June 2010, DeLaVina&Larson, proved the stronger statement that for M be the set of whose degree is greater than n/2, we have |H| ≤ n-|M|. which settles 409b & 409c also. | |||
T | 409b. | Let G be a connected graph on n > 2 vertices and H the union of all maximum critical independent sets of G. If d(G) > n/2, |H| =0. | definitions |
June 2010. June 2010, DeLaVina&Larson, proved the stronger statement that for M be the set of whose degree is greater than n/2, we have |H| ≤ n-|M|. which settles 409a & 409c also. | |||
T | 409c. | Let G be a connected graph on 6 > n > 2; let A2 be vertices of degree less than or equal to 2, and H the union of all maximum critical independent sets of G. Then |H| ≤ |A2|. | definitions |
June 2010. June 2010, DeLaVina&Larson, proved the stronger statement that for M be the set of whose degree is greater than n/2, we have |H| ≤ n-|M|. which settles 409b & 409c also. | |||
O | 410a. | Let G be a connected graph on n > 2; let A be the vertices of minimum degree, M the vertices of maximum degree, De the set of vertices that maximize the number of vertices at even distance and H the union of all maximum critical independent sets of G. Then |H| ≤ |V-A| + |V-M| + |E(G[De])|. | definitions |
June 2010. Since
n
≤|V-A|
+ |V-M| this and 410b are trivially true for non-regular
graphs. For regular graphs of degree greater than n/2, |H| = 0
and so the only open question is: if G is k-regular with k ≤ n/2, then |H| ≤ |E(G[De])|? |
|||
O | 410b. | Let G be a connected graph on n > 2; let A be the vertices of minimum degree, M the vertices of maximum degree, De the set of vertices that minimize the number of vertices at even distance and H the union of all maximum critical independent sets of G. Then |H| ≤ |V-A| + |V-M| + |E(G[De])|. | definitions |
June 2010. See the
comment on 410a and note that the only open question is: if G is k-regular with k ≤ n/2, then |H| ≤ |E(G[De])|? |
|||
Dalmatian Heuristic | |||
Lower Bounds on the order of H (the union of all maximum critical independent sets) for connected graphs. | |||
T | 411. | Let G be a connected graph on n > 2 vertices, P the set of pendant vertices and H the union of all maximum critical independent sets of G. Then |H| ≥ isolates(G[V-N(P)]) + peN(V-N(P)) . | definitions |
June 2010. June 2010, with Larson. | |||
O | 412a. | Let G be a connected graph on n > 2 vertices, P the set of pendant vertices and H the union of all maximum critical independent sets of G. Then |H| ≥ cL(G[N(P)]) and if G is also bipartite then, |H| ≥ cL(G[N(P)]) + a(G[V-N(N(P))]). | definitions |
June 2010. The first part is easily true since P Í H and cL(G[N(P)]) £ |N(P)| £ |P|. | |||
O | 412b. | Let G be a connected graph on n > 2 vertices, P the set of pendant vertices, A2 the vertices of degree 2 and H the union of all maximum critical independent sets of G. Then |H| ≥ cL(G[N(P)]) and if G is also bipartite then, |H| ≥ cL(G[N(P)]) + a(G[A2]). | definitions |
June 2010. The first part is easily true since P Í H and cL(G[N(P)]) £ |N(P)| £ |P|. | |||
T | 412c. | Let G be a connected bipartite graph on n > 2 vertices and H the union of all maximum critical independent sets of G. Then |H| ≥ a(G). | definitions |
June 2010. This follows for the larger class of Konig-Egervary graphs because maximum critical independent sets are maximum independent sets. | |||
O | 412d. | Let G be a connected bipartite graph on n > 2 vertices and H the union of all maximum critical independent sets of G. Then |H| ≥ γT(G). | definitions |
June 2010. | |||
O | 412e. | Let G be a connected bipartite graph on n > 2 vertices, P the set of pendant vertices and H the union of all maximum critical independent sets of G. Then |H| ≥ 1 + D(G[N(N(P))]) | definitions |
June 2010. | |||
O | 412f. | Let G be a connected graph on n > 2 vertices, P the set of pendant vertices and H the union of all maximum critical independent sets of G. Then |H| ≥ m(G[V-N(P)]), and if G is also bipartite then, then |H| ≥ number of components of G[V-N(P] + m(G[V-N(P)]). | definitions |
June 2010. | |||
O | 413a. | Let G be a connected graph on n > 2 vertices, A the set of minimum degree vertices and H the union of all maximum critical independent sets of G. Then |H| ≥ k(G)*a(G[V-A]) + m(G[N(N(P))] | definitions |
June 2010. | |||
O | 413b. | Let G be a connected graph on n > 2 vertices, A2 the set of vertices of degree 2 and H the union of all maximum critical independent sets of G. Then |H| ≥ k(G)*cL(G[N(A2)-A2]) + number of pendants | definitions |
June 2010. | |||
F | 414. | Let G be a connected graph on n > 2 vertices and H the union of all maximum critical independent sets of G. Then |H| ≥ ac(G)*FLOOR[1/lower median]. | definitions |
June 2010. August 2010 C. Larson. See counterexample. | |||
O | 415a. | Let G be a connected graph on n > 2 vertices, A2 the set of vertices of degree 2 and H the union of all maximum critical independent sets of G. Then |H| ≥ (epN(A2) -1)*isolates(N(A2)). | definitions |
June 2010. | |||
O | 415b. | Let G be a connected graph on n > 2 vertices, A2 the set of vertices of degree 2, B2 the set of vertices of degree at most 2 and H the union of all maximum critical independent sets of G. Then |H| ≥ (epN(A2) -1)*isolates(B2). | definitions |
June 2010. | |||
O | 415c. | Let G be a connected graph on n > 2 vertices, B2 the set of vertices of degree at most 2 and H the union of all maximum critical independent sets of G. Then |H| ≥ (epN(B2) -1)*isolates(B2). | definitions |
June 2010. | |||
O | 416. | Let G be a connected graph on n > 2 vertices with diameter at most 2, P the set of pendants and H the union of all maximum critical independent sets of G. Then |H| ≥ isolates(N(N(P))) -2. | definitions |
June 2010. | |||
Dalmatian Heuristic | |||
Lower Bounds on the independent domination for connected graphs. | |||
R | 417. |
Let G be a connected graph on n > 3 vertices. Then i(G)
£
n(G) - maximum{deg(v) + m(G[V-N(v)])
: v in V(G) } |
definitions |
Dec. 8 2010.
M. Blidia, M. Chellali, F. Maffray, Extremal graphs for a new upper bound on domination parameters in graphs, Discrete Mathematics, 306 (2006), 2314-2326. |
|||
T | 418a. | Let G be a connected graph on n > 3 vertices, A the set of minimum degree vertices of G. Then i(G) £ a(G[V-A]) + |A| -1. | definitions |
Dec. 8 2010. W. Goddard.
May 2012, just noticed that this is similar to G.pc's #451. |
|||
O | 418b. |
Let G be a connected graph on n > 3 vertices, A the set of minimum degree
vertices of G. Then i(G)
£ a(G[V-A])
+ |E(G[N(A)])|*p(G). |
definitions |
Dec. 8 2010. If |E(G[N(A)])| = 0, then N(A) is an independent set. Take a maximal independent set of of G[V-A] containing N(A) and the claim follows. So suppose E(G[N(A)]) is not empty. If |A| -1 £ |E(G[N(A)])|*p(G), then the inequality follows from 418a. So suppose 0 < |E(G[N(A)])|*p(G) < |A| -1. | |||
O | 418c. |
Let G be a connected graph on n > 3 vertices, A the set of minimum degree
vertices of G. Then i(G)
£ a(G[V-A])
+ |E(G[N(A)])| + |A Ç Ic|.
|
definitions |
Dec. 8 2010. If |A| -1 £ |E(G[N(A)])| + |A Ç Ic|, then the inequality follows from 418a. So suppose 0 < |E(G[N(A)])|+ |A Ç Ic| < |A| -1. | |||
F | 418d. |
Let G be a connected graph on n > 3 vertices, A the set of minimum degree
vertices, M the maximum degree vertices of G, and K_4(G) the vertices incident
to the most K4. Then i(G)
£ |A| *|K4|G)|
+
g(G[V-M]) |
definitions |
Dec. 8 2010. Jan 2011
DeLaVina see counterexample |
|||
F | 418e. |
Let G be a connected graph on n > 3 vertices, A the set of minimum degree
vertices, and D the set of neighbor dominators. Then i(G)
£
|A|
+ diameter(G) + |E(D, V-D)|. |
definitions |
Dec. 8 2010. Jan 2011
counterexample for
424 also refuted 418e. |
|||
T | 419a. |
Let G be a connected graph on n > 3 vertices, A the set of minimum degree
vertices of G. Then i(G)
£ a(G)
- 1/(w(G[N[Ac]]) -1 ). |
definitions |
Dec. 8 2010. For this and
419b if the core of G is empty then the right hand side is a(G)
+1 and so the inequality follows trivially. If the core of G
is not empty, then both w(G[N[Ac]])
and r(G[N[Ac]]) are both at least two,
and the smallest that the right hand side can be is a(G)
- 1. Dec, 2010 Bill Waller proved that For a connected graph G, if the core of G is non-empty, then i(G) £ a(G) - 1. |
|||
T | 419b. |
Let G be a connected graph on n > 3 vertices, A the set of minimum degree
vertices of G. Then i(G)
£ a(G)
- 1/(r(G[N[Ac]]) -1 ). |
definitions |
Dec. 8 2010. Dec 2010 Bill
Waller (see above). |
|||
T | 420a. |
Let G be a connected graph on n > 3 vertices, S the set of support
vertices of G. Then i(G)
£ a(G[V(G)-N(S)])
+ 2*Floor[0.5|E(G[N(S)])|] ). |
definitions |
Dec. 8 2010. Dec 2010Wayne
Goddard proved that i(G)
£ a(G[V(G)-N(S)])
+ |E(G[N(S)])| (so there is still the question of a slight improvement when
|E(G[N(S)])| is odd.) |
|||
O | 420b. |
Let G be a connected graph on n > 3 vertices, A the set of minimum degree
vertices and S the set of support
vertices of G. Then i(G)
£ a(G[V(G)-N(S)])
+ 4(|E(G[N[A]])|-1). |
definitions |
Dec. 8 2010. Note if there are
so pendants then the equality follows trivially since in this case a(G[V(G)-N(S)])
= a(G). |
|||
O | 420c. |
Let G be a connected graph on n > 3 vertices, S the set of support
vertices of G and Tmin be the set of vertices incident with the
fewest triangles . Then i(G)
£ a(G[V(G)-N(S)])
+ 4(|Tmin|-1). |
definitions |
Dec. 8 2010. Note if there are
no pendants then the inequality follows trivially since in this case a(G[V(G)-N(S)])
= a(G); moreover, if the graph is triangle
free then again the inequality follows trivially
since 4(|Tmin|-1) = 4(n(G)-1). |
|||
R | 421a. |
Let G be a connected graph on n > 3 vertices. Then i(G)
£
lmax(G)
(gt(G)-1). |
definitions |
Dec. 8 2010. DeLaVina If G
is a graph on n > 1 vertices i(G)
£
1 + (lmax(G)-1)
(g(G)-1).
|
|||
O | 421b. |
Let G be a connected graph on n > 3 vertices and Ml
the vertices of maximum local independence. Then i(G)
£
g(G)FLOOR[0.5|Nmax(e)| -
1]. |
definitions |
Dec. 8 2010.
|
|||
O | 421c. |
Let G be a connected graph on n > 3 vertices and Ml
the vertices of maximum local independence. Then i(G)
£
g(G)(|N[Ml]| -
3). |
definitions |
Dec. 8 2010.
|
|||
F | 421d. |
Let G be a connected graph on n > 3 vertices and M the vertices of
maximum degree. Then i(G)
£
FLOOR[0.5g2(G)]a(G[N(M)]). |
definitions |
Dec. 8 2010. Pepper Jan. 26,
2011 see counterexample
|
|||
O | 422a. |
Let G be a connected graph on n > 3 vertices and M the vertices of
maximum degree. Then i(G)
£
a(G[V-M)])+2FLOOR[E(G[M])/3]. |
definitions |
Dec. 8 2010.
|
|||
O | 422b. |
Let G be a connected graph on n > 3 vertices and M the vertices of
maximum degree. Then i(G)
£
a(G[M)])+g(G[V-M])2. |
definitions |
Dec. 8 2010.
|
|||
O | 422c. |
Let G be a connected graph on n > 3 vertices and A the vertices of
degree at most n/2. Then i(G)
£
a(G[A)])+2FLOOR[D(G[V-A])/3]. |
definitions |
Dec. 8 2010.
|
|||
O | 422d. |
Let G be a connected graph on n > 3 vertices and D the set of vertices
each of whose closed neighborhood contains the closed neighborhood of some other
vertex. Then i(G)
£
a(G[V-D])+FLOOR[(|E(G[D])|
+ 1)/3]. |
definitions |
Dec. 8 2010.
|
|||
O | 423. |
Let G be a connected graph on n > 3 vertices, M its set of maximum degree
vertices and A its set of minimum degree vertices. Then i(G)
£
|E(G[M])|+ a(G[N[A]])*a(G[V-A]). |
definitions |
Dec. 8 2010.
|
|||
F | 424. |
Let G be a connected graph on n > 3 vertices, M its set of maximum degree
vertices and D the set of vertices each of whose closed neighborhood contains
the closed neighborhood of some other vertex. Then i(G)
£
|E(D,V-D)|+ a(G[M])
+ g(G[V-M]). |
definitions |
Dec. 8 2010. Jan 2011 DeLaVina
see counterexample |
|||
F | 425a. |
Let G be a connected graph on n > 3 vertices, M its set of maximum degree
vertices and D the set of vertices each of whose closed neighborhood contains
the closed neighborhood of some other vertex. Then i(G)
£
|Tmin(G)|+
isol(G[B])
+ g(G[V-N(P)]). |
definitions |
Dec. 8 2010. Jan 2011 counterexample for 424 also refuted 425a. | |||
F | 425b. |
Let G be a connected graph on n > 3 vertices and A the core of G. Then i(G)
£
2|Tmin(G)|(2+c(G[N[A]])),
where c(G[N[A]]) is the order of a largest component of the subgraph induced by
N[A]. |
definitions |
Dec. 8 2010. Jan 2011 counterexample for 424 also refuted 425b. | |||
F | 425c. |
Let G be a connected graph on n > 3 vertices and M the vertices of maximum
local independence of G. Then i(G)
£
2|Tmin(G)|FLOOR[0.5|N[M]|]. |
definitions |
Dec. 8 2010. Jan 2011 DeLaVina see counterexample | |||
O | 425d. |
Let G be a connected graph on n > 3 vertices and P the set of pendants of G. Then i(G)
£
|Tmin(G)|+
sum of K4(v))
+ g(G[V-N(P)]). |
definitions |
Dec. 8 2010. |
|||
O | 425e. |
Let G be a connected graph on n > 3 vertices and D the set of neighbor
dominators of G. Then i(G)
£
4|Tmin(G)|+
|E(G[D])| |
definitions |
Dec. 8 2010.
|
|||
O | 426. |
Let G be a connected graph on n > 3 vertices and M the vertices of
maximum degree. Then i(G)
£
n - g(G[N(M)]). |
definitions |
Dec. 8 2010.
|
|||
O | 427. |
Let G be a connected graph on n > 3 vertices and M the vertices of
maximum degree. Then i(G)
£
|E(C,V-C)| + FLOOR[(2/3)|E(G[V-N(P)])|]. |
definitions |
Dec. 8 2010.
|
|||
F | 428. | Let G be a connected graph on n > 3 vertices and M the vertices of maximum degree. Then i(G) £ g(G[V-N(P)]) + (n mod D(G)) + x, where x = the number of vertices with minimum{deg(v) + m(G[V-N(v)]) : v in V(G) }. | definitions |
Dec. 8 2010. Jan 2011 the
counterexample
for 418d also
refuted this conjecture. |
|||
F | 429. | Let G be a connected graph on n > 3 vertices and M the vertices of maximum degree and Davg(P) average of distance from each periphery vertex of graph. Then i(G) £ Davg(P)*(a(G[N(M)]) + 1) | definitions |
Dec. 8 2010. Jan 2011 the
counterexample
for 421d also
refuted this conjecture.
|
|||
O | 430a. | Let G be a connected graph on n > 3 vertices and C the center of G. Then i(G) £ a(G[N(C)])+2*FLOOR[Caro-Wei -1] | definitions |
Dec. 8 2010.
|
|||
O | 430b. | Let G be a connected graph on n > 3 vertices and C the center of G. Then i(G) £ a(G[N(C)])*residue(G2)+isolates of G[V-M] | definitions |
Dec. 8 2010.
Jan
2011 DeLaVina see counterexample |
|||
O | 430c. | Let G be a connected graph on n > 3 vertices and C the center of G. Then i(G) £ lmax(G)*residue(G2)+ D(G[M]) | definitions |
Dec. 8 2010.
|
|||
O | 431a. | Let G be a connected graph on n > 3 vertices and D the set of vertices of degree two of G. Then i(G) £ residue(G)+ peN(N(D)) + |Tmin(G)|. | definitions |
Dec. 8 2010.
|
|||
O | 431b. | Let G be a connected graph on n > 3 vertices and A the set of vertices of minimum degree of G. Then i(G) £ residue(G)+ g(G[N[A]]) peN(N(D)) + dp(G), where dp(G) is the number pairs of vertices on the periphery at distance two. | definitions |
Dec. 8 2010.
|
|||
O | 431c. | Let G be a connected graph on n > 3 vertices. Then i(G) £ residue(G) * |Tmax(v)| + dd(G). | definitions |
Dec. 8 2010.
|
|||
O | 432a. | Let G be a connected graph on n > 3 vertices. Then i(G) £ annihilation number + minimum{vertices at even distance from v - vertices at odd distance from v}. | definitions |
Dec. 8 2010.
|
|||
O | 432b. | Let G be a connected graph on n > 3 vertices and P the set of pendants of G. Then i(G) £ |V-N(P)|+ minimum{vertices at even distance from v - vertices at odd distance from v}*_bipartite. | definitions |
Dec. 8 2010.
|
|||
O | 433. | Let G be a connected graph on n > 3 vertices and P the set of pendants of G. Then i(G) £ 0.5|N(M)|*FLOOR[2*sum of inverses of degrees of G2]. | definitions |
Dec. 8 2010.
|
|||
O | 434a. | Let G be a connected graph on n > 3 vertices and P the set of pendants of G. Then i(G) £ |M| + 2FLOOR[0.5*SW(Gc)]. | definitions |
Dec. 8 2010.
|
|||
O | 434a. | Let G be a connected graph on n > 3 vertices. Then i(G) £ |M| + 2FLOOR[0.5*SW(Gc)]. | definitions |
Dec. 8 2010.
|
|||
O | 434b. | Let G be a connected graph on n > 3 vertices and M the set of maximum degree vertices of G. Then i(G) £ d(G[M]) + 1 + SW(Gc). If diameter > 2, then i(G) £ d(G[M]) + SW(Gc). | definitions |
Dec. 8 2010.
|
|||
O | 434c. | Let G be a connected graph on n > 3 vertices and M the set of maximum degree vertices of G. Then i(G) £ d(G[V-M]) + 1 + SW(Gc). If d(G) = 1, then i(G) £ d(G[V-M]) + SW(Gc). | definitions |
Dec. 8 2010.
|
|||
O | 434d. | Let G be a connected graph on n > 3 vertices and B the set of vertices of maximum eccentricity of G. Then i(G) £ SW(Gc) - c(G[N[B]]) + 2, where c(G[N[B]]) is the number of components of G[N[B]]. | definitions |
Dec. 8 2010.
|
|||
O | 434e. | Let G be a connected graph on n > 3 vertices and C the center of G, i.e. the set of vertices of minimum eccentricity of G. Then i(G) £ SW(Gc) - ecc(C) + 2, where ecc(C) is the eccentricity of the set C. | definitions |
Dec. 8 2010.
|
|||
Dalmatian Heuristic | |||
Upper Bounds on the 2-independence number for connected graphs. | |||
O | 435. | Let G be a connected graph on n > 3 vertices. Then a2(G)£ SW(G)+CEILING[(1+|E(G2[A])|/3], where SW(G) is the Szekeres-Wilf invariant of the complement graph of G and E(G2[A]) is the edge set of the subgraph of the second power graph of G induced by its minimum degree vertices of G2. | definitions |
Jan. 2012.
|
|||
T | 436a. |
Let G be a connected graph on n > 3 vertices. Then a2(G)£ WP(G) + c(D), where WP(G) is the Welsh-Powell invariant of the complement graph and c(D) is the number of components of the subgraph induced by the set of neighbor dominators of G. | definitions |
Jan. 2012. May 2012, in [DP12] we proved that ak ≤ WP(G) + k - 1 and that a2 ≤ WP(G) whenever the graph G has no neighbor dominators. [DP12] E. DeLaVina, R. Pepper, Graffiti.pc on the 2-independence number of a graph, preprint 2012. |
|||
T | 436b. | Let G be a connected graph on n > 3 vertices. Then a2(G)£ WP(G) + FLOOR[3/radius], where WP(G) is the Welsh-Powell invariant of the complement graph. | definitions |
Jan. 2012. *May 2012, in [DP12] we proved that ak ≤ WP(G) + k-1, so here it simply remains to settle a2 ≤ WP(G) whenever the graph G has has radius at least 4. May 2013, DeLaVina. [DP12] E. DeLaVina, R. Pepper, Graffiti.pc on the 2-independence number of a graph, preprint 2012. |
|||
O* | 436c. | Let G be a connected graph on n > 3 vertices. Then a2(G)£ k*WP(G) + D(G[D]), where D(G[D]) is the maximum degree of the subgraph induced by the nighbor dominators and k is the kth step for a zero in the Havil-Hakimi process. | definitions |
Jan. 2012. *May 2012, in [DP12] we proved that ak ≤ WP(G) + k-1, so here it simply remains to settle a2 ≤ WP(G) whenever the neighbor dominators are isolated in the subgraph that they induce and when k=1. [DP12] E. DeLaVina, R. Pepper, Graffiti.pc on the 2-independence number of a graph, preprint 2012. |
|||
T | 437. | Let G be a connected graph on n > 3 vertices. Then a2(G)£ CEILING[(2/3)n]*p(G). | definitions |
Jan. 2012.
May 2012, Pepper: if the path covering number of G is greater than 1 then the conjecture is trivially true. Now if p(G) =1, that is the graph has a Hamiltonian path, then since the a2(Pn) = CEILING[(2/3)n] the conjecture follows. |
|||
O | 438a. | Let G be a connected graph on n > 3 vertices. Then a2(G)£ a(G) + a(G[V-A]) + |E(G[A])|, where A is the set of vertices of minimum degree of G. | definitions |
Jan. 2012. . | |||
O | 438b. | Let G be a connected graph on n > 3 vertices. Then a2(G)£ a(G) + a(G[V-H2]) + |E(G[H2])|, where H2 is the set of vertices of degree at most 2 in G. | definitions |
Jan. 2012. | |||
O | 439. | Let G be a connected graph on n > 3 vertices. Then a2(G)£ |N(M)| + FLOOR[2(CW(G) -1)], where M is the set of maximum degree vertices and CW(G) is the Caro-Wei invariant of G. | definitions |
Jan. 2012. | |||
T | 440. | Let G be a connected graph on n > 3 vertices. Then a2(G)£ n - g(G[V-A]), where A is the set of minimum degree vertices of G. | definitions |
Jan. 2012. May 2012, Pepper and Waller. | |||
T | 441a. | Let G be a connected graph on n > 3 vertices. Then a2(G)£ n - m(G[N(Ac)]) -1, where Ac is the intersection of all maximum independent sets of G. | definitions |
Jan. 2012. April 2013, DeLaVina & Lazo. | |||
T | 441b. | Let G be a connected graph on n > 3 vertices. Then a2(G)£ n - d(G[N(Ac)]) -1, where Ac is the intersection of all maximum independent sets of G. | definitions |
Jan. 2012. April 2013, DeLaVina & Lazo. | |||
O | 442. | Let G be a connected graph on n > 3 vertices. Then a2(G)£ n - CEILING[path(G[H3])/2, where H3 is the set of vertices of degree at least 3 in G. | definitions |
Jan. 2012. | |||
O | 443. | Let G be a connected graph on n > 3 vertices. Then a2(G)£ sum of disparities - |N(Ac)| -2, where Ac is the intersection of all maximum independent sets of G. | definitions |
Jan. 2012. | |||
O | 444. | Let G be a connected graph on n > 3 vertices. Then a2(G)£ n - FLOOR[dd(K4(v))/2], where dd(K4(v)) is the number of distinct values that appear in the sequence of the number of K4 incident to a vertex. | definitions |
Jan. 2012. | |||
T | 445a. | Let G be a connected graph on n > 3 vertices. Then a2(G)£ a3(G) - D(G[H2]) + 1, where H2 is the set of vertices of degree at most 2 in G. | definitions |
Jan. 2012. April
2012,DeLaVina & Pepper. [DP12] E. DeLaVina, R. Pepper, Graffiti.pc on the k-independence number of a graph, preprint 2012. |
|||
F | 445b. | Let G be a connected graph on n > 3 vertices. Then a2(G)£ a3(G) - FLOOR[c(G[H3]/3], where H3 is the set of vertices of degree at least 3 in G. | definitions |
Jan. 2012. April 2012, DeLaVina & Pepper. Take three copies of K(4,4) linked together by one edge between the first and second copy and one edge between the second and third, and then subdivide the linked edges a2(G)= a3(G) = 14, but c(G[H3] = 3. | |||
O | 446. | Let G be a connected graph on n > 3 vertices. Then a2(G)£ pN(A) + |V\S|, where A is the set of minimum degree vertices and S is the set of support vertices. | definitions |
Jan. 2012. | |||
F | 447a. | Let G be a connected graph on n > 3 vertices. Then a2(G)£ A + FLOOR[g3 /3], where A is the annihilation number and g3 is the3-domination number of G. | definitions |
Jan. 2012. Feb. 2013, DPW see a counterexample. | |||
F | 447b. | Let G be a connected graph on n > 3 vertices. Then a2(G)£ A + FLOOR[R/2], where A is the annihilation number and R is the residue. | definitions |
Jan. 2012. Feb. 2013, DPW see a counterexample. | |||
O | 448a. | Let G be a connected graph on n > 3 vertices. Then a2(G)£ |Hn/2| + |E(G[V-Hn/2])| + r(G), where Hn/2 is the set of vertices of degree greater than n/2 in G. | definitions |
Jan. 2012. | |||
O | 448b. | Let G be a connected graph on n > 3 vertices. Then a2(G)£ |V-A| + |E(G[N(S)])| + r(G), where A is the set of vertices of minimum degree and S is the set of support vertices in G. | definitions |
Jan. 2012. | |||
O | 449. | Let G be a connected graph on n > 3 vertices. Then a2(G)£ |V\H3| + CEILING[(|E(G[H3])|-1)/2], where H3 is the set of vertices of degree at least 3. | definitions |
Jan. 2012. | |||
O | 450. | Let G be a connected graph on n > 3 vertices. Then a2(G)£ pN(A2) + |V\S| + pN(V\H3), where A2 is the set of degree two vertices, S is the set of support vertices and H3 is the set of vertices of degree at least 3. | definitions |
Jan. 2012. | |||
T | 451. | Let G be a connected graph on n > 3 vertices. Then a2(G)£ 2a(V-A) + |A|, where AÍV. | definitions |
Jan. 2012. Note that
the program made several conjectures of this exact form with a variety of
different sets, so I chose to report the stronger conjecture and indeed it
is true. Jan 2012, the more general statement
ak(G)£
ka(V-A) +
|A|, where AÍV
is proven in [DP12]. Note that this is also an improvement over G.pc's
#418a. [DP12] E. DeLaVina, R. Pepper, Graffiti.pc on the k-independence number of a graph, preprint 2012. |
|||
T | 452. | Let G be a connected graph on n > 3 vertices. Then a2(G)£ 2a(G) - m(G[S]), where S is the set of support vertices of G. | definitions |
Jan. 2012. June 2013, Bill Kinnersly settled this during my talk at CanaDAM 2013 in St John's. | |||
Dalmatian Heuristic | |||
Lower Bounds on the 2-independence number for connected graphs. | |||
T | 453. |
Let G be a connected graph on \( n \ge 3 \) vertices, and \( H_{n/2} \) the vertices of degree at most \( \frac{n}{2} \). Then \( \alpha_2(G) \ge 2c(G[H_{n/2}]) - isol(G[H_{n/2}]) \),
where \( c(G[H_{n/2}]) \) is the number of components of the subgraph induced by
\( H_{n/2} \). In this run, the program made the similar conjecture for many different sets. |
definitions |
Jan. 2012. April 2012,
DeLaVina & Pepper. It isn't difficult to see that this relation holds for
any subset of the vertices not only
\( H_{n/2} \). [DP12] E. DeLaVina, R. Pepper, Graffiti.pc on the \( k \)-independence number of a graph, preprint 2012. |
|||
T | 454. | Let G be a connected graph on \( n \ge 3 \) vertices, and \( D \) the set of neighbor-dominators. Then \( \alpha_2(G) \ge 2c(G[D]) \), where \( c(G[D]) \) is the number of components of the subgraph induced by \( D \). | definitions |
Jan. 2012. April 2012,
DeLaVina & Pepper. [DP12] E. DeLaVina, R. Pepper, Graffiti.pc on the \( k \)-independence number of a graph, preprint 2012. |
|||
E | 455. |
Let G be a connected graph on \( n \ge 3 \) vertices, and \( H_2 \) the set
of degree two vertices. Then \( \alpha_2(G) \ge \rho(G[V \setminus H_2]) - \lfloor
\frac{1}{3} \rho(G[V \setminus H_2]) \rfloor \), where \( \rho(G[V \setminus
H_2]) \) is the path covering number of the subgraph induced by the vertices
that are not of degree two. In this run, the program made the similar conjecture for many different sets. |
definitions |
Jan. 2012. April 2012, DeLaVina & Pepper. For any induced path the 2-independence number is about \( 2/3 \) the order of the path. | |||
R | 456. | Let G be a connected graph on \( n \ge 3 \) vertices. Then \( \alpha_2(G) \ge \alpha(G) \). | definitions |
Jan. 2012. | |||
| |||
T | 457. | Let G be a connected graph on \( n \ge 3 \) vertices. Then \( \alpha_2(G) \ge \alpha_c(G) + 2c(G[N[V-A_c]]) \), where \( A_c \) is the core of G. | definitions |
Jan. 2012. June 2013, DeLaVina | |||
T | 458. | Let G be a connected graph on \( n \ge 3 \) vertices. Then \( \alpha_2(G) \ge 2\alpha(G) - |V-D| \), where D is the set of neighbor-dominators. | definitions |
Jan. 2012. April 2012,
DeLaVina & Pepper. [DP12] E. DeLaVina, R. Pepper, Graffiti.pc on the \( k \)-independence number of a graph, preprint 2012 |
|||
T | 459. | Let G be a connected graph on \( n \ge 3 \) vertices. Then \( \alpha_2(G) \ge |A| - |E(G[A])/2| \), where A is any subset of the vertices. | definitions |
Jan. 2012. The program
conjecture this for a variety of sets so I propose the stronger conjecture. June 2013, Pepper wrote the following: "Let R_k, CT_k, a_k be the k-Residue, k-Caro-Tuza, and k-independence respectively. Also, let n be order and m be size. Theorem(s): (Jelen 1999) a_k >= R_k >= CT_k Observation: (Jelen 1999) For k < D, where D means max degree, CT_k = n – m/k Theorem: (Pepper 2004) For k >= D, where D means max degree, R_k = n – m/k Corollaries: a_k >= R_k >= n – m/k Randy and G.pc Conjecture: a_k >= |A| - |E(G[A])|/k Proof: Let A be a set of vertices in graph G. Then a_k(G) >= a_k([A]) >= R_k([A]) >= n([A]) – m([A])/k = |A| - |E(G[A])|/k."
|
|||
under construction....
|