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

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.

Comments from Boussairi:
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.


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)

Department of Mathematical Sciences
Florida Atlantic University
777 Glades Road
Boca Raton, Florida 33431-0991
USA

Office: Room 286, Science & Engineering
Phone: (561) 297-3350
Fax: (561) 297-2436
URL: http://www.math.fau.edu/locke/unsolv3.htm

Last modified March 14, 2005, by S.C. Locke.