Graceful Tree Verification Project中文版
project (aka GTV) aims to verify the graceful conjecture by distributed
volunteer computing. The graceful tree conjecture is an important open
problem in graph theory. Via this project, we can verify this
conjecture on trees with size restriction, try to find a possible
counter-example, and get statistics about graceful trees. For more
detail, please visit Mathematical Background.
This project is temporary in pause. A paper resuming results and
algorithms of this project is available on arXiv:
A Computational Approach to the Graceful Tree Conjecture.
Here is the most current computation code: gtvb.cpp (2010/10/23)
If you want to know what we have done, please have a look at Current Status.
If you want to have a look at results produced so far, please go to Project Result.
If you are interested by this project and want to participate, please visit Guide for Participants. You can also benchmark your machine following a guide in CPU Benchmark.
If you have any doubt, you may find an answer on Project FAQ.
If you want to know more about who am I and why I build this project, you can have a look at Personal Introduction.
For any question or problem, please contact me via firstname.lastname@example.org. You can also find me at Distributed Computing Forum in Chinese (English Section).
Pages will now only be updated occasionally, due to severe procrastination of the author.
An archive is on Project News Archive.
2008/11/22 GTV Project is on Beta.
2008/11/22 This website is set up, thanks to phchenjie!
2008/11/27 Participant BiscuiT has returned the first valid result.
2008/12/10 All blocks for Beta are distributed.
2009/01/21 Beta test is over, and the project starts today! We have verified that every tree containing 32 nodes is graceful.
2009/02/12 Blocks for verification of trees with 33 nodes are all
distributed out! We now start to distributed blocks of trees with 34
2009/04/27 All blocks concerning n=33 are returned. We have verified that every tree containing 33 nodes is graceful.
2009/05/10 A new improved client is available!
2009/06/05 Blocks for verification of trees with 34 nodes are all
distributed out! We now start to distributed blocks of trees with 35
2009/08/23 All blocks concerning n=34 are returned. We have verified that every tree containing 34 nodes is graceful.
2010/02/21 All blocks concerning n=35 are returned. We have verified that every tree containing 35 nodes is graceful.
A Brief Introduction to Graceful Trees
This project aims to verify an important open problem in graph theory,
the graceful tree conjecture, by distributed volunteer computing.
So, what are graceful trees?
As you can see from above, this is a tree with 31 nodes. Its vertices
are labelled from 0 to 30 without repetition or omission. This is
called a labelling on vertices.
If you look at numbers beside each edge, you will find that it is the
difference of labels of its two endpoints. This is called a labelling
on edges induced by a labelling on vertices.
There are 30 edges on this tree. If we look carefully at labels on
edges, we'll find that every number from 1 to 30 appears once and only
once. A labelling on vertices that induce such a labelling on edges is
called graceful labelling of this tree.
More generally, a tree with n vertices has n-1 edges. If a labelling on
vertices, in which every number from 0 to n-1 appears once and only
once, can induce a labelling on edges where every number from 1 to n-1
appears once and only once, this labelling on vertices is called a
If a tree has at least one graceful labelling, it is called a graceful tree. By definition, the tree above is graceful.
This definition of gracefulness is restricted to trees. It can be extended to general simple graphs.
You may think that graceful labellings are rare things, it's just by
luck that this tree happens to be graceful. But in fact, it has been
proved that every tree with at most 31 vertices is graceful.
There is a famous conjecture in graph theory called the graceful tree
conjecture. It hypothesizes that every tree is graceful. It's still an
open problem. Your calculation can help us to verify this conjecture on
some trees, which can possibly lead to a counter-example.
But if the graceful tree conjecture is right, no counter-example can be
found. At this case, your calculation still helps us to accumulate
useful statistics on graceful trees, which might help researches on
Join Us to Verify the Graceful Tree Conjecture!
As the number of trees to verify grows exponentially, in order to
verify the graceful tree conjecture on trees with growing number of
vertices, we need your help!
If you are interested, please have a look at Guide for Participants. We are eager to see your participation!
If you want to know more on graceful trees and graceful labelling, please visit Mathematical Background.