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

See, e.g.:

Caro, Y.

For a general reference to zero-sum ramsey numbers see:

Caro.Y ,

58. Thomas Bohme (personal communication, March 2000) asks the folllowing: Given a set

59. Yair Caro (personal communication, August 2001).

Let

If this question is too hard, then what for the case

60. Abderrahim Boussairi (personal communication, October 2001).

Let

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 [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.

2. G. Lopez et C. Rauzy.

61. A

A graph

Locke, Voss and Tracy,

Abreu and Locke, (CGTC33, 2002), show that every

It is fairly easy to show that any

(i) Show that we can eliminate small vertices by induction.

(ii) Show the graph has a copy

(iii) Show that either some vertex of

(iv) Consider the largest component that can occur in

Simple examples show that there are

Here is an alternate form of the question. For a given tree

(i) if

(ii) if diameter

(iii)

Ajit A. Diwan and Namrata P. Tholiya,

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

Thus, the situation now is that

August 26, 2010: A little more work (two to three pages) shows that

One additional paper has since appeared:

W. Mader.

Abstract from MathSciNet: The main result of this paper is as follows: Let

It is obvious that one can find a minimum length cycle

It is also possible to construct examples in which

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,

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.

J.W. Suurballe, R.E. Tarjan.

R. Bhandari.

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

B. Jackson,

___________

Dear Stephen Locke, Bill Jackson,

Adrian Bondy

I am an amateur interested in experimental mathematics.

A conjecture by Jackson is: Conjecture 5.42 Every

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

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:

Best regards

-- Georgi Guninski (February 2013)

___________

Comment (SCL): The 12-vertex graphs in JGT30 could be written Cay(

Cay(

Cay(

An obvious triviality: It is easy to construct a

Suppose we look at the

I've looked a little at applying simulated annealing to find a 16-vertex or 17-vertex oriented

_______________

A counterexample for

MR0617348 (82i:05051)Zhang, Cun Quan.

Author's summary:

"Let

_________________

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

Note: See Adám's conjecture: http://math.fau.edu/locke/Unsolv2.htm#J46

Florida Atlantic University

777 Glades Road

Boca Raton, Florida 33431-0991

USA

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

Last modified February 4, 2013, by S.C. Locke.