Note, in the new version of Bondy and Murty's text, GTM 244,
the authors revisit these unsolved problems in Appendix A,
and have increased the number of unsolved problems to 100.
Some of these problems have been solved (and thus the title of this webpage is slightly incorrect) and
I won't claim to be familiar with all current results.
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.)
Please note that I much prefer comments sent by e-mail to those sent by telehone, as I very frequently have trouble deciphiring messages left on my telephone.
If I receive comments on the new problems, I will of course post those that seem suitable
(and, at that point, I would presumably post the problem to which the comment refers).
Note, however, the publisher does have a site for the text,
http://blogs.springer.com/bondyandmurty/,
and it would seem reasonable that one should post comments there.
Also, I'm not giving you all of the references in
Bondy
and Murty or the new text
Bondy
and Murty 2007.
You should get yourself a copy of the new text (and the old text, if you can find it).
12345678910111213141516171819202122232425
Comments on Problems from the 2007 text will be placed in:
New Problems from GTM 244 as I receive them.
If a problem is in both texts, I will try to cross-reference,
by placing a
[red] number after the statement of the problem for the 2007 numbering,
and a [green] number for the 1976 numbering.
Julio Subocz notes that this is also called Berge's conjecure or the Berge-Sauer conjecture and, in a conference in Lisboa (November 1995), Y. H. Hamidoune cited a
proof (approximately 65 pages) by Taskinov of the conjecture.
Yair Caro: Solved by Taskinov in 1982 and the proof is not 65 pages.
V.A.Taskinov, Three regular parts of four regular graphs.Math. Notes 36(1984), 612-623 .
Alon + Kallai + Friedland have several extensions.
Taskinov also wrote an earlier paper:
V.A.Taskinov, Regular subgraphs of regular graphs.Sov.Math.Dokl.26(1982), 37-38 .
In this paper he proved the following :
Let 0<k<r be positive odd integers. Then every r-regular graph contains
a k-regular subgraph (Here, the graph need not be simple).
1. Zhang, Li Min, 4-regular graphs without 3-regular subgraphs. Graph theory and its applications: East and West( Jinan, 1986), 691--699, Ann. New York Acad. Sci, Volume 576. New York Acad. Sci., New York, 1989.
2. Tashkinov, V. A.3-regular subgraphs of 4-regular graphs. (Russian)
Mat. Zametki 36(1984), no. 2, 239--259.
Communicated by
Yair Caro:
Yuansheng Yang, Jianhua Lin, Chunli Wang,and Kaifeng Li.
On Kotzig's conjecture concerning graphs with a unique regular
path-connectivity.Discrete Mathematics 211(2000), 287-298. Abstract:
Kotzig (see Bondy and Murty, Graph Theory with Applications, North-Holland,
Amsterdam, 1976) conjectured that there exists no graph with the property
that every pair of vertices is connected by a unique path of length k,k<2.
Kotzig (Graph Theory and Related Topics, Academic Press, New York, 1979,
pp. 358-367) has proved this conjecture for 2<k<9. Xing and Hu (Discrete
Mathematics 135(1994), 387-393) have proved it for k>11. Here we prove this
conjecture for the remaining cases k=9,10,11.
Yair Caro:
L.Pyber, JCTB 66(1996), proved that the edges of every connected graph
on n vertices can be covered by at most n/2 + O(n3/4) paths.
Communicated by
Yair Caro:
Nathaniel Dean and Mekkia Kouider.
Gallai's conjecture for disconnected graphs.Discrete Mathematics 213(2000), 43-54. Abstract:
The path number p(G) of a graph G is the minimum number of paths needed to
partition the edge set of G. Gallai conjectured that p(G)<=(n+1)/2 for every
connected graph G of order n. Because of the graph consisting of disjoint
triangles, the best one could hope for in the disconnected case is p(G)<=2n/3.
We prove the sharper result that p(G)<=u/2+2g/3 where u is the number of odd
vertices and g is the number of nonisolated even vertices.
Communicated by
Yair Caro:
Fan Genghua. Subgraph coverings and edge switchings. JCTB 84(2002), 54-83. Abstract:
By using the so-defined circuit/path transformations together with an edge-switching method, the following conjectures were proved in this paper.
(i) The edges of a connected graph on n vertices can be covered by at most ceiling(n/2) paths, which was conjectured by Chung.
(ii) The edges of a 2-connected graph on n vertices can be covered by at most ceiling((2n-1)/3) circuits, which was conjectured by Bondy.
An immediate consequence of (ii) is a theorem of Pyber that the edges of a graph on n vertices can be covered in at most n-1 edges and circuits, which was conjectured by Erdös, Goodman and Pósa.
6. Prove: Every 2-edge-connected simple graph G
on n vertices is the union of
n-1 cycles.
(P. Erdös, A.W. Goodman, L. Pósa, 1966)
There, reference to an earlier work of Pyber is also given.
Julio Subocz:
We relax the condition 3-regular subgraph, in the form:
Let us call a graph 3-sum-0 if the degrees are multiples of 3.
I think that this idea is due to Alon-Kallai-Friedland,
Every four-regular graph plus an edge contains a three regular
subgraph,
J.Comb.Th.(B) 37(1984), 92-93.
Let g(n) be the maximum possible number of edges in a simple graph
of n vertices which contains no 3-sum-0-subgraph. Then
g(4) = 5, g(5) = 8, g(6) = 10, g(7) = 13, but
g(n) = 2n, for all n >= 8.
This was obtained with the aid of a computer program.
There are only
seven known UPC-graphs (unipancyclic graphs) having
respectively 3, 5, 8, 8, 14, 14, 14 vertices (Entringer).
It is proved that there are only four outerplanar UPC-graphs having
3, 5, 8, 8
vertices respectively.
It is conjectured that the above 7 graphs are the only UPC-graphs.
Essentially there was no progress since 1986 !!
The only available papers on the subject so far are :
Shi, Y.B., Yap, H.P,. and Teo, S.K., On uniquely r-pancyclic graphs,
Graph Theory and Its Applications: East and West, (Jinan, 1986),
487-499,
Ann. New York Acad. Sci., 576, New York Acad. Sci. New York, 1989.
MR 93d:05088
Shi, Y.B., Some theorems of uniquely pancyclic graphs,
Discrete Math. 59(1986), 167-180. MR 87j:05103
from
Klas Markstrom:
A note on uniquely pancyclic graphs, technical report No 8 2000,
Department of Mathematics,
Umeå University, submitted to Discrete Mathematics.
I have shown that there
are no such graphs on less than 56 vertices other than the seven previously
found. The proof is basically a computer search. I also give some bounds
for the number of edges in a uniquely pancyclic graph.
Communicated by Chunhui Lai:
Carol T. Zamfirescu, "We introduce the class of (2)-pancyclic graphs, which are simple undirected finite connected graphs of order n having exactly two cycles of length p for each p satisfying 3 ≤ p ≤ n, analyze their properties, and give several examples of such graphs, among which are the smallest."
Carol T. Zamfirescu, Discrete Applied Mathematics,
Volume 161, Issues 7–8, May 2013, Pages 1128–1136.
Communicated by Chunhui Lai:
Bu, Yuehua (Zbl 1212.05127). The enumeration of uniquely pancyclic digraph with the least arcs. (Chinese. English summary).
[J] Math. Pract. Theory 39, No. 4, 189-193(2009). ISSN 1000-0984
Summary: A uniquely pancyclic digraph D is an oriented graph of order v that contains a uniquely directed cycle of each length n for 3 ≤ n ≤ v. Let g(v) denote the least number of arcs in all uniquely pancyclic directed graphs of order v. Let N(v) denote the number of uniquely pancyclic and non-isomorphic digraphs of order v which have g(v) arcs. In this paper, we determine the values of N(v) for all 3≤ n≤ 8.
Communicated by Chunhui Lai:
George, John C.; Khodkar, Abdollah; Wallis, W. D.
Pancyclic and bipancyclic graphs. (English) Zbl 06567214.
SpringerBriefs in Mathematics. Cham: Springer (ISBN 978-3-319-31950-6 pbk;
978-3-319-31951-3 ebook). xii, 108 p. (2016).
From Yair Caro:
E. Boros, Y. Caro, Z.Furedi and R.Yuster: Covering non-uniform hypergraphs,
Journal of Combinatorial Theory,
Series B 82(2001), 270-284.
The authors prove
f(n) ≤ n + 1.98 sqrt(n) (this is a part of a much more general Turan-type
problem considered).
A lower bound due to Lai and other shows f(n) ≥ n + sqrt(2n).
See also:
Chunhui Lai, Graphs without repeated cycle lengths. Australasian Journal of Combinatorics 27(2003), 101 - 105.
In this paper, it is proved that f(n) ≥ n+36t for t=1260r+169, (r ≥ 1)
and n ≥ 540t2+(175811t+7989)/2. Consequently,
$\liminf\sb {n \to \infty} {f(n)-n \over \sqrt n} ≥ \sqrt {2 +
{2 \over 5}}.$ We make the following conjecture:
From Lai Chunhui:
Let f2(n) be the maximum number of edges in a 2-connected
graph on n vertices in which no two cycles have the same length.
In 2001, E. Boros, Y. Caro, Z. F\"uredi and R. Yuster [Covering non-uniform hypergraphs, Journal of Combinatorial Theory,
Series B 82(2001), 270-284.] improved this lower bound
significantly: f2(n) ≥ n + sqrt{n} - O(n9/20).
and conjectured that
\ $\lim \frac{f2 (n)-n}{\sqrt{n}}=1$.
It is easy to see that this Conjecture implies the (difficult)
upper bound in the Erdos Turan Theorem (see [E. Boros, Y. Caro, Z. Füredi and R. Yuster, 2001]).
Further comments from Chunhui Lai, August 15, 2011:
Let Sn be the set of simple graphs on n vertices in which no two
cycles have the same length. A graph G in Sn is called a simple
maximum cycle-distributed graph (simple MCD graph) if there exists no
graph G'∈Sn with |E(G')|>|E(G)|. A planar
graph G is called a generalized polygon path (GPP) if G* formed
by the following method is a path: corresponding to each interior face
f of ~G (~G is a plane graph of G) there is a
vertex f* of G*;
two vertices f* and g* are
adjacent in G* if and only if the intersection of the boundaries
of the corresponding interior faces of ~G is a simple path of
~G. In this paper, we prove that there exists a simple MCD
graph on n vertices such that it is a 2-connected graph being not a
GPP if and only if n∈{10, 11, 14, 15, 16, 21, 22}. We also prove
that, by discussing all the natural numbers except for 75 natural
numbers, there are exactly 18 natural numbers, for each n of which,
there exists a simple MCD graph on n vertices such that it is a
2-connected graph. (see [Shi, Yong-Bing; Tang, Yin-Cai; Tang, Hua;
Gong, Ling-Liu; Xu, Li, Two classes of simple MCD graphs, Akiyama, Jin
(ed.) et al., Discrete geometry, combinatorics and graph theory. 7th
China-Japan conference, CJCDGCGT 2005, Tianjin, China, November 18--20,
2005, Xi'an, China, November 22--24, 2005. Revised selected papers.
Berlin: Springer. Lecture Notes in Computer Science 4381, 177-188
(2007). ISBN 978-3-540-70665-6/pbk], Zbl 1149.05316)
Further from Lai Chunhui:
Lai, Chunhui(PRC-ZNU-MIF); Liu, Mingjing(PRC-ZNU-MIF)
Some open problems on cycles. (English summary)
J. Combin. Math. Combin. Comput. 91(2014), 51–64.
(MR3287706 Reviewed) 05C35
Additional references from Lai Chunhui:
Joey Lee and Craig Timmons,
A note on the number of edges in a Hamiltonian graph
with no repeated cycle length,
Australas. J. Combin. 69(2)(2017), 286-291.
Chunhui Lai,
On the size of graphs without repeated cycle lengths,
Discrete Appl. Math. 232(2017), 226-229.
13. (Solved)
Find a (6,5)-cage.
An (m,n)-cage is an m-regular graph
with
girthn and, subject to this,
with the least possible number of vertices.
The Petersen graph is a (3,5)-cage and has 10 vertices.
The Heawood graph is a (3,6)-cage and has 14 vertices.
The Mcgee graph is a (3,7)-cage and has 24 vertices.
The Tutte-Coxeter graph is a (3,8)-cage and has 30 vertices.
The Robertson graph is a (4,5)-cage and has 19 vertices.
The (4,6)-cage has 26 vertices.
The Robertson-Wegner graph is a (5,5)-cage and 30 vertices.
From James R. Lee:
A large amount of progress has been made in recent
years. The most promising direction seems to be to relate the bandwidth
of a graph to its local density, which is the least D such that every ball
of radius r in G has at most rD points, i.e. |B(v,r)| ≤ rD for all
v, r, and where the ball is taken in the shortest path metric of G. It is
easy to see that D is a lower bound on the bandwidth bw(G).
There are some graphs on n vertices with constant density which have
bandwith log(n). Thus the gap between bw(G) and D(G) is at least log(n).
It is conjectured (by many people, most recently probably by Nati Linial
in his talk at the last ICM) that the gap is at mostlog(n), i.e.
bw(G) = O(D(G) logn) for any graph. No progress was made until Feige (2000)
proved that the gap is at most polylog, i.e. bw(G) = O(D(G) log3.5(n)
using embeddings of the graph in euclidean space.
The question is even wide open for trees. Fan Chung (1988) proved that the gap
is at least log(n) for certain trees. Gupta (2001) showed that it is most
log2.5(n).
Hajo Broersma
sent the following e-mail message (19 June 1997):
Dear colleague,
Since you either attended the EIDMA Workshop on Hamiltonicity of
2-Tough Graphs or at least were invited to do so, we guess you are
interested in the fact that we have refuted the conjecture that every
2-tough graph is hamiltonian. In fact, we found examples of t-tough
nontraceable graphs for arbitrary t<9/4. We already wrote a preliminary
paper. If you are interested in receiving a postscript file, just let
us know.
Best wishes,
Doug Bauer, Hajo Broersma, Henk Jan Veldman.
21(b). It was conjectured that every (3/2)-tough graph has a 2-factor
(Chvátal, 1971).
A recent e-mail message from
Erik Engbers, a
student at U. Twente, points out that this was settled
in the negative by a result of H. Enomoto,
B. Jackson and
P.Katerinis.
The following
theorem appears in their article:
Let k>=1. For any positive real number s,
there exists a (k-s)-tough graph G
with k|V(G)| even and |V(G)| >= (k+1) and
which has no k-factor.
H. Enomoto,
B. Jackson and
P.Katerinis.
Toughness and the existence of k-factors,
Journal of Graph Theory, 9(1985), 87-95.
The following interesting result was proven
by Enomoto (1985):
If G is k-tough, |V(G)|>=k+1 and k|V(G)| is even,
then G has a k-factor.
This result is generalized in several ways by
C. Chen and P. Katerinis.
I thank Mr. Engbers for helping make my file
more current.
Jan van der Heuvel
wrote his Ph.D. Thesis on toughness problems.
I should have remembered
the J-E-K result from there.
The
binding number of a graph G
is defined by
Yair Caro:
I finally got an information concerning problem #23 by Payan. (This was
done via GRAPHNET).
Erdos, Payan, Hobbs proved that the conjecture is true
for (n-k)-regular graphs when k < -2 + 2sqrt(2n), where
|V(G)| = n. Disc. Math. 42(1982), 57-61 (Information from
Arthur Hobbs).
Klas Markstrom:
The folkman number f(3,5) has been determined, f(3,5)= 15. This
result and information on bounds for some other folkman numbers is
published in:
Konrad Piwakowski, Stanislaw P. Radziszowski and Sebastian Urbanski,
Computation of the Folkman number Fe(3,3;5).
Journal of Graph Theory 32(1999), pages 41-49.
Department of
Mathematical Sciences Florida Atlantic University
777 Glades Road Boca Raton, Florida 33431-0991
USA