×

Constraint programming models for graceful graphs. (English) Zbl 1160.68565

Benhamou, Frédéric (ed.), Principles and practice of constraint programming – CP 2006. 12th international conference, CP 2006, Nantes, France, September 25–29, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-46267-5/pbk). Lecture Notes in Computer Science 4204, 545-559 (2006).
Summary: The problem of finding a graceful labelling of a graph, or proving that the graph is not graceful, has previously been modelled as a CSP. A new and much faster CSP model of the problem is presented, with several new results for graphs whose gracefulness was previously unknown. Several classes of graph that are conjectured to be graceful only for small instances are investigated: after a certain size, it appears that for some of these classes the search to prove that there is no graceful labelling is essentially the same for each successive instance. The possibility of constructing a proof of the conjecture based on the search is discussed.
For the entire collection see [Zbl 1141.68004].

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI