Determine R(Kn,Z3) for
n=7 (mod 9).
In general given a graph and an integer k such that k|e(G) we denote the
zero-sum ramsey number by R(G,Zk) which is the smallest n such that for
mapping f : E(Kn,) --> Zk there exists a copy of G such that f(G)=0 (mod
where f(G) is the sum of the weights of the edges of G.
There are many known results on the subject but for R(Kn,Z3) the
situation is rather intrigiung as except of n=7 (mod 9) in all other cases
where 3| (n choose 2), R(Kn,Z3) is now known and for n=7 (mod 9) we know it is
either n+3 or n+4
Caro, Y. Binomial coefficients and zero-sum Ramsey numbers.JCTA 80(1997), 368-373.
Let G be a graph and k>1 be an integer.
A set of vertices D in G is called non-zero (mod k) dominating set of G
if for every vertex v in G the following holds : | N[v] intersection D |
is not congruent to 0(mod k). Note that N[v] is the closed neighborhood of v in
It is known (Sutner 1989, Caro 1996 in a general setting) that every
graph G has a non-zero (mod 2) dominating set (and hence non-zero (mod
k) dominating set for k even).
There are several papers written recently on odd-domination in graph
(the minimum cardinality of non-zero (mod 2) dominating set).
Question: is it true that every graph G has a non-zero (mod k)
dominating set for every integer k>1?.
If this question is too hard, then what for the case G is a tree? or
60. Abderrahim Boussairi (personal communication, October 2001).
Let T be a tournament with n points (n>13),and suppose that every
subtournament of T with n-3 points is self-complementary. Prove that T is (the directed graph of) a linear ordering or T is the tournament obtained from a
linear ordering by reversing the arc from the first verex to the last vertex.
Comments from Boussairi:
The result is true if we replace n-3 by n-4 (or by n-h when n is large enough) and can be easily obtained using the results of .
The result is false for n-1 or n-2. For this, consider the arc-transitive
tournament [Payley digraph] formed on the points of GF(p) (where p is a prime number such
that p=3(mod 4) and GF(p) is the galois field) by the following rule : if a,b are in GF(p) then there is an arc directed from a to b when b-a is a
non-zero quadratic residue in GF(p).
For n-3, Y.Boudabbous and I proved  the result for a large class of
1. Y. Boudabbous et A. Boussairi. Reconstruction des tournois et
dualité. C.R.Acad. Sci.Paris.t.320, Série I(1995), p.397-400.
2. G. Lopez et C. Rauzy. Reconstruction of binary relations from their
restrictions of cardinality 2,3,4 and (n-1) ,I and II Zeitschr.f. Math.logiK
und Grundlagen d.Math.Bd 38(1992), p.27-37.
61. A distance-degree condition and non-separating trees.
Comment (SCL): The 12-vertex graphs in JGT30 could be written Cay(Z12;3,4,6), and
Cay(Z12;2,3,8). The first has six digons, but the second satisfies the
hypotheses for Jackson's conjecture, and not the conclusion.
Multiplying by invertible elements of Z12 we get
Cay(Z12;9,4,6), Cay(Z12;9,8,6) (with digons) and
Cay(Z12;2,9,8), Cay(Z12;10,9,4) (oriented graphs).
An obvious triviality: It is easy to construct a k-diregular disconnected digraph on 4k+2 vertices. Take the disjoint union of two k-diregular tournaments on 2k+1 vertices. Probably this influenced the choice of 4k+1 for this conjecture.
Suppose we look at the (4k)! cyclic permutations of the vertices of a k-diregular oriented graph D on 4k+1 vertices. If π is a permutation and πiπi+1 is a arc of D, then we would expect πi+1πi+2 to be an arc of D with probability k/(4k-1). Now, we can't expect that all of these probabilities are independent, but let's pretend they are. Then, the expected number of directed Hamilton cycles would be (4k)!(k/(4k-1))4k+1 and these numbers increase fairly quickly. For k=4, this predictor gives 3648 cycles. Of course, even if the average is high, it doesn't say much about any individual graph. But it does perhaps indicate that looking for a random counterexample might not work.
I've looked a little at applying simulated annealing to find a 16-vertex or 17-vertex oriented
graph with a smallish number of Hamilton cycles. For 16 vertices, the number came down to around 4300 Hamilton cycles, and for 17 vertices, around 8000 (although I haven't run the case n=17 for very long).
A counterexample for k = 3 may or may not lead to counterexamples for k ≥ 4. Jackson's conjecture may still be of interest. Here's another reference (about bipartite directed graphs):
MR0617348 (82i:05051)Zhang, Cun Quan. The longest paths and cycles in bipartite oriented graphs.
(Chinese. English summary)
J. Math. Res. Exposition 1981, First Issue, 35-38.
"Let D be a bipartite oriented graph in which the indegree and outdegree of each vertex are at least k. The result given in this paper is that D contains either a cycle of length at least 4k or a path of length at least 4k+1. B. Jackson [Ann. Discrete Math. 8 (1980), 275-277; MR0597185 (82a:05051)] conjectured that if |V(D)| ≤ 4k, then D contains a Hamiltonian cycle. Evidently, the result of this paper implies the result given by Jackson."
From: Georgi Guninski (February 2013)
CC'ing Nathann Cohen.
The oriented non-hamiltonian circulants in the paper appear to
have the property that reversal of any edge results in a hamiltonian digraph.
According to  p 7 (by coincidence exactly after Jackson's conjecture)
this is a problem of Thomassen, 1987
Problem 18 : Is there a nonhamiltonian oriented graph in which the reversal
of any edge results in a hamiltonian digraph? (Thomassen, 1987)