# Unsolved Problems (Part 3)

How to contact me.
Problems from Bondy and Murty 1976 are listed on two other pages: Problems 1-25, Problems 26-50. Comments on problems from the new Bondy and Murty text might appear at Problems from GTM 244: Graph Theory, 2007. Also, see: http://blogs.springer.com/bondyandmurty/.

This page lists a few new problems. If you find that one of them has been solved (or even that some reasonable progress has been made), please e-mail me. (How to contact me.)

57 58 59 60 61 62 63

Problems 1-25, Problems 26-56.
57. From Yair caro.

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 every mapping f : E(Kn,) --> Zk there exists a copy of G such that f(G)=0 (mod k) , 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 and R(K7,Z3)=11.

See, e.g.:
Caro, Y. Binomial coefficients and zero-sum Ramsey numbers. JCTA 80(1997), 368-373.

For a general reference to zero-sum ramsey numbers see:
Caro.Y , Zero-sum Problems - A Survey. Discrete Mathematics 152(1995), 93-113.
58. Thomas Bohme (personal communication, March 2000) asks the folllowing: Given a set F of graphs and a positive integer k, is there a constant c that depends on F and k such that every k-connected graph on n vertices with no minor in F must have a cycle of length at least cn. For example, if F={K5,K3,3} and k=4, then Tutte's theorem guarantees c=1. Bohme would like a proof that doesn't depend on the embedding. Bohem at al. have a proof that for every surface S, there is a constant c depending only on S, such that every 4-connected graph G with n vertices embedded on S has a cycle of length at least cn. The proof uses Tutte's theorem on a planar 4-connected graph obtained from G to find a long path in G, and then uses a theorem of Bondy and Locke to prove that G has a long cycle.
59. Yair Caro (personal communication, August 2001).

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 G . 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 k=3?
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.

• 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 [2].
• 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 [1] the result for a large class of tournaments.

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.

A graph G is t-cohesive if G is connected, has at least two vertices, and for every pair of distinct vertices, u and v, d(u)+d(v)+d(u,v) >= t.

Locke, Voss and Tracy, MAA Monthly 108(2001), pages 470-472, show that every (2k)-cohesive graph contains a non-separating path on k vertices.

Abreu and Locke, (CGTC33, 2002), show that every (2k+2)-cohesive graph contains a non-separating copy of any tree T on k vertices, as long as the diameter of T is at most 4.

It is fairly easy to show that any (4k-2)-cohesive graph contains a non-separating copy of any tree T on k vertices. A sketch of the proof:
(i) Show that we can eliminate small vertices by induction.
(ii) Show the graph has a copy T' of T.
(iii) Show that either some vertex of G-V(T') is adjacent to every vertex of T' or each component of G-V(T') has a copy of T.
(iv) Consider the largest component that can occur in G-V(T") for some copy T" of T.

Simple examples show that there are (2k-1)-cohesive graphs containing no non-separating subgraph with k vertices.

Question 61. Show that every (2k)-cohesive graph contains a non-separating copy of any tree T on k vertices.

Here is an alternate form of the question. For a given tree T, let f(T) denote the minimum positive integer t so that every t-cohesive graph contains a non-separating copy of T. We already know the following for any tree T on k vertices:
(i) if T is a path, then f(T) = 2k;
(ii) if diameter(T) <= 4, then f(T) <= 2k+2; and
(iii) f(T)<= 4k-2.

Calculate f(T) for other classes of trees. Question 61 asks whether or not f(T)=2k for every tree T on k vertices.

Recent Progress.

Ajit A. Diwan and Namrata P. Tholiya, Non-separating trees in connected graphs, Discrete Mathematics 309(2009), pages 5235-5237. The authors show that if G is a connected graph with minimum degree at least d and if T is a tree on d vertices, then G contains a non-separating copy of T.

Using the Diwan and Tholiya result, and the techniques discussed in the paper of Abreu and Locke, it is not hard to show that if G is a connected (2n+4)-cohesive graph and if T is a tree on n vertices, then G contains a non-separating copy of T. Specifically, if (G,b) is a minimal weakly (2n+4)-cohesive counterexample, then every vertex of G, except possibly b, must have degree at least n. Now, paste together several copies of G by overlaying the images of b.

Thus, the situation now is that 2n ≤ f(T) ≤ 2n+4 for any tree T on n vertices. It remains only to determine the best possible value of f(T) from this narrow range of values.

August 26, 2010: A little more work (two to three pages) shows that 2n ≤ f(T) ≤ 2n+1 for any tree T on n vertices.

One additional paper has since appeared:

W. Mader. Connectivity keeping trees in k-connected graphs. J. Graph Theory 69(2012), 324-329. [MR2898871]

Abstract from MathSciNet: The main result of this paper is as follows: Let m,k ∈ N. Every finite k-connected graph G of minimum degree at least 2(k-1+m)2+m-1 contains a subgraph H of minimum degree at least m-1 such that G -A is k-connected for all A ⊆ V(H) with |A| ≤ m. This result implies that for every finite k-connected graph of minimum degree at least 2(k-1+m)2+m-1 and every tree T of order m, graph G contains a subgraph T' isomorphic to T such that G - V(T') is k-connected. The author also poses related conjectures for digraphs.

Question 62 (Suggested by an email from M. Weis, 2005). Given a 2-connected graph G, and two vertices u and v of G, how can one find a minimum length cycle through u and v in the graph G? Can this be done in polynomial time?

It is obvious that one can find a minimum length cycle C(u) through u in O(n3) time, by simply looking for shortest (u,y)-paths in G-uy for all y in N(u). If v is on C(u), we're done. Similarly, one can find a minimum length cycle C(v) through v, and if u is on C(v), there's nothing left to do. On the other hand, it is easy to build a family of examples, F4, F5, ..., in each of which C(u) and C(v) are 3-cycles, d(u,v) = 1, and yet the length of a shortest cycle through u and v in Fk is k. Simply take tuvw to be a subpath of a k-cycle. Adjoint two new vertices, x and y with N(x) = {t,u} and N(y) = {v,w}.

It is also possible to construct examples in which d(u,v)=q, with a (u,v)-path L of length q, and the remainder of the graph consisting of a vine on L, each of the q-2 vine-paths with length N, and the unique cycle through u and v being hamiltonian.

It would be strange if nobody has previously considered this problem. However, I do not know of a suitable reference, except perhaps:

Toru Kojima and Kiyoshi Ando, Minimum length of cycles through specified vertices with wide-diameter at most d. Ars Combinatoria 58(2001), 245-256.

E-mail from M. Weis, October 6, 2006:

Last year I posed the problem of finding the shortest cycle through two given vertices of a graph; well, I recently learned that the problem has been solved for undirected graphs as early as 1974 by J.W. Suurballe. The problem that Suurballe solved has been stated differently, namely as finding k (vertex)-disjoint paths between two given vertices such that the sum of their length is minimized. A subsequent paper coauthored by R.E. Tarjan solved (as far as I understood) a one-to-all version of the problem. Bhandari supplied a further improved the algorithm in his book "Survivable Networks".

Suurballe's algorithm is based on invoking Dijkstra's Shortest Path Algorithm k times, so the problem can be solved efficiently.

References:

J.W. Suurballe. Disjoint Paths in Networks. Networks 4(1974), 125-145.

J.W. Suurballe, R.E. Tarjan. A Quick Method for finding Disjoint Shortest Paths. Networks 14(1984), 325-336.

R. Bhandari. Survivable Networks: Algorithms for Diverse Routing, Kluwer Academic Publishers (1999)

63. This is just a comment on a question I had asked. If G is an n-dimensional hypercube, and if one removes k red vertices and k blue vertices, k ≤ n-2, must G have a Hamilton cycle?

N. Castaneda, V. Gochev, I. Gotchev, and F. Latour claim to have a proof.
Part 1.

64. (Bill Jackson) Conjecture 5.42 Every k-diregular oriented graph on at most 4 k + 1 vertices, where k ≠ 2 contains a directed Hamiltonian circuit.

B. Jackson, Paths and cycles in oriented graphs. Journal of Graph Theory 5(1981), 145-157. (See Conjecture 5, page 153.)

___________

Dear Stephen Locke, Bill Jackson,

I am an amateur interested in experimental mathematics.

A conjecture by Jackson is: Conjecture 5.42 Every k-diregular oriented graph on at most 4k + 1 vertices, where k ≠ 2 contains a directed Hamiltonian circuit.

Counter example to Jackson's conjecture appears 3-diregular digraph on 12 vertices. It is a circulant digraph, the vertices are 0 .. 11 and vertex i is adjacent to i + 4,i + 9, i + 10 (mod 12).

Non-hamiltonicity was shown with the CASes sage 5.6 and maple 13 and since the digraph is small, brute force search for hamiltonian cycles confirmed it is non-hamiltonian (in less than a second). The inequality in the conjecture doesn't hold.

The edges are: [(0, 4), (0, 9), (0, 10), (1, 5), (1, 10), (1, 11), (2, 0), (2, 6), (2, 11), (3, 0), (3, 1), (3, 7), (4, 1), (4, 2), (4, 8), (5, 2), (5, 3), (5, 9), (6, 3), (6, 4), (6, 10), (7, 4), (7, 5), (7, 11), (8, 0), (8, 5), (8, 6), (9, 1), (9, 6), (9, 7), (10, 2), (10, 7), (10, 8), (11, 3), (11, 8), (11, 9)]

From a discussion I learnt isomorphic digraph with different circulant parameters is in the paper:
http://arxiv.org/pdf/math/9702227v1.pdf S.C. Locke, and D. Witte [now D. Witte Morris]. On non-Hamiltonian circulant digraphs of outdegree three. Journal of Graph Theory 30(1999), 319-331.

Best regards
-- Georgi Guninski (February 2013)

___________

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;3,4,6), Cay(Z12;3,8,6), Cay(Z12;9,4,6), Cay(Z12;9,8,6) (with digons) and
Cay(Z12;2,3,8), Cay(Z12;10,3,4), 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 k-diregular 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.

Author's summary:
"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 [1] 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)

[1]: http://www.math.nctu.edu.tw/hlfu/getCourseFile.php?CID=58&type=browser