Graceful Tree Verification Project

Graceful Tree Verification
中文版

This 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 projectgtv@gmail.com. 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.

News

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 nodes.
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 nodes.
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?

An example of graceful tree

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 graceful labelling.

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 graceful trees.

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.


By FANG Wenjie(aka fwjmath)
Attribution-Noncommercial-No Derivative Works 2.5 China Mainland