Von Koch's conjecture
Daniel Dudley
Given a tree with N nodes (and hence N-1 edges), find a
way to enumerate the nodes from 1 to N and, accordingly,
the edges from 1 to N-1 in such a way that for each edge
K the difference of its node numbers equals to K. The
conjecture is that this is always possible.
More information (incl. diagrams) at:
http://www.hta-bi.bfh.ch/~hew/informatik3/prolog/p-99/
Confer problem/puzzle P92: Von Koch's conjecture.
A web search using Copernic (utilizes 14 search engines)
didn't provide further information.
It is purported that for small trees the problem is easy to
solve by hand. However, for larger trees -- 14 is already
very large -- it is extremely difficult to find a solution.
Does anyone know of a general mathematical solution to the
conjecture? If not, who will rise to the challenge?
Daniel
Edwin Clark
"Daniel Dudley" wrote
>
> Given a tree with N nodes (and hence N-1 edges), find a
> way to enumerate the nodes from 1 to N and, accordingly,
> the edges from 1 to N-1 in such a way that for each edge
> K the difference of its node numbers equals to K. The
> conjecture is that this is always possible.
> Does anyone know of a general mathematical solution to the
> conjecture?
>
This is a well-know problem in graph theory. For more details see
the dynamic survey article on graph labeling by Joseph Gallian in
the Electronic Journal of Combinatorics http://www.combinatorics.org/
The problem you mention is a special case of the problem "which graphs have
a graceful labeling?" Gallian says, "The 'Ringel-Kotzig' conjecture that
all trees are
graceful has been the focus of many papers. Kotzig has called the effort to
prove it a
disease." [In particular you have misnamed the conjecture.] If you look at
Gallian's
paper you will find some of what's known. It seems that the conjecture has
been verified
for trees with at most 27 vertices, but it is still open.
--Edwin Clark
Jim Nastos
> Von Koch's conjecture:
>
> Given a tree with N nodes (and hence N-1 edges), find a
> way to enumerate the nodes from 1 to N and, accordingly,
> the edges from 1 to N-1 in such a way that for each edge
> K the difference of its node numbers equals to K. The
> conjecture is that this is always possible.
This is called the "Graceful labelling problem." The problem
can be stated on graphs in general, and some types of graphs are
known to be graceful (if the graphs has such a labelling, it is
called graceful.)
The long-standing conjecture that all trees are graceful is still
open. The conjectures has been verified for all trees with 16 or
less vertices.
It is known, however, that all "caterpillars" are graceful. (A
caterpillar is a tree which is one long path and any vertex not on
this path is at a distance at most 1 away from the path.)
A "lobster" is like a caterpillar, but vertices can be a distance
of at most 2 away from the main path. A colleague of mine proved in
his MSc thesis that all lobsters with a perfect matching are graceful,
and I believe the proof is constructive (meaning it gives a method to
gracefully label such graphs.)
I don't know much about algorithms to gracefully label trees;
considering the conjecture is open for trees with 17 vertices, I don't
think any efficient method is known. A websearch for "graceful graphs"
or "graceful trees," "graceful labelings" should get you much more
information.
Jim Nastos
Jim Nastos
> Von Koch's conjecture:
If I could make one more point: I've never heard of the graceful
labeling problem refered to as "Von Koch's Conjecture" and the website you
referenced stated that Von Kock was some mathematician interested inthe
problem who the maker of that site knew.
A strange fact is that - as far as I know - the conjecture, although
well known, has an unclear origin. I believe the earliest published
statement of the conjecture is by Ringel and Kotzig in 1964, but the
problem probably goes back before that.
(The problem is most commonly known as the Graceful Labeling Conjecture.
Jim Nastos
Charles Delorme
Dear colleague,
this problem is also known as
Ringel-Kotzig conjecture,
or
Graceful labeling of trees.
I think it remains open, although many families
of trees have been shown to consisist of
``Graceful'' trees,
these trees that admit a graceful labeling.
For example
Hrnciar, Pavel; Haviar, Alfonz
All trees of diameter five are graceful.
[J] Discrete Math. 233, No.1-3, 133-150 (2001).
Surely, a search with the word graceful on Math. Reviews
(Math Sci Net)
or Zentralblatt
will provide you
with other references
--
Charles Delorme tous les mégalomanes
LRI ont une signature
c...@lri.fr à étages