Computer search for graceful labeling: a survey

Ljiljana Brankovic, Michael J. Reynolds

Abstract


This paper surveys the main computer search results for finding graceful labeling of trees. The paper is devoted to the memory of Mirka Miller, who made an outstanding contribution to the area of graph labeling.


Keywords


graph labeling, graceful labeling, graceful tree conjecture, computer search

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2022.10.1.23

References

J. Abrham and A. Kotzig, Exponential lower bounds for the number of graceful valuations of snakes, Congr. Numer. 72 (1990), 163–174.

M. Adamaszek, Efficient enumeration of graceful permutations, to appear in J. Combin. Math. Combin. Comput..

R.E. Aldred and B.D. McKay, Graceful and harmonious labellings of trees, Bull. Inst. Combin. Appl., 23, (1998), 69–72.

R.E. Aldred, J. Širáň, and M. Širáň, A Note on the number of graceful labelings of paths, Discrete Math., 261, (2003), 27–30.

M. Alfalayleh, L. Brankovic, H. Giggins, and Md. Z. Islam, Towards the graceful tree conjecture: a survey, AWOCA2004, 7-9 July, Ballina, Australia, (2004).

I. Arkut, R. Arkut, and N. Ghani, Graceful label numbering in optical MPLS networks, Proc. SPIE, 4233, (2000), 1–8, OptiComm 2000: Optical Networking and Communications, Imrich Chlamtac; Ed.

M. Baca and C. Barrientos, Graceful and edge-antimagic labelings, Ars Combin., to appear.

P. Bahl, S. Lake, and A. Wertheim, Gracefulness of families of spiders, Involve, 3(3), (2010) pp.241–247.

J.C. Bermond, Graceful graphs, radio antennae and french windmills, Graph Theory and Combinatorics, Pitman, London, (1979), 13–37.

J.C. Bermond, C. Huang, A. Rosa, and D. Sotteau, Decompositions of Complete Graphs into Isomorphic Subgraphs with Five Vertices, Ars Combinatoria 10, (1980), pp.211–254.

J.C. Bermond and D. Sotteau, Graph decompositions and G-designs, Cong. Numer., 15, (1976), 53–72.

G.S. Bloom and S.W. Golomb, Applications of numbered undirected graphs, Proc. IEEE, 65, (1977) 562–570.

G.S. Bloom and S.W. Golomb, Numbered complete graphs, unusual rulers, and assorted applications, in Theory and Applications of Graphs, Lecture Notes in Math., 642, Springer-Verlag, New York, (1978), 53–65.

G.S. Bloom and D.F. Hsu, On graceful digraphs and a problem in network addressing, Congr. Numer., 35, (1982), 91–103.

G.S. Bloom and D.F. Hsu, On graceful directed graphs that are computational models of some algebraic systems, Graph Theory with Applications to Algorithms and Computers, Ed. Y. Alavi, Wiley, New York (1985).

C.P. Bonnington and J. Širáň, Bipartite labeling of trees with maximum degree three, J. Graph Th., 31, (1999), 37–56.

L. Brankovic, C. Murch, J. Pond, and A. Rosa. Alpha-size of trees with maximum degree three and perfect matching, Proceedings of AWOCA2005, 18–21 September, Ballarat, Australia, (2005), 47–56.

L. Brankovic, A. Rosa, and J. Širáň, Labeling of trees with maximum degree three - an improved bound, J. Combin. Math. Combin. Comput., 55, (2005), 159–169.

L. Brankovic and I.M. Wanless, Graceful Labelling: State of the Art, Applications and Future Directions, Mathematics in Computer Science, 5(1), (2011), pp. 11–20.

G. Brinkmann, S. Crevals, H. M$grave{e}$lot, L.J. Rylands, and E. Steffan, α-labelings and the structure of trees with nonzero α-deficit. Discrete Math. Theor. Comput. Sci., 14(1), (2012), 159–174.

D. Bryant, Cycle Decomposition of Complete Graphs, Surveys in Combinatorics 2007, London Mathematical Society Lecture Note Series 34, (2007), pp. 67–97.

N.J. Cavenagh and I.M. Wanless, On the number of transversals in Cayley tables of cyclic groups, Disc. Appl. Math., 158, (2010), 136–146.

F.R.K. Chung and R.L. Graham, Recent results in graph decompositions, Combinatorics (Swansea, 1981), London Math. Soc. Lecture Note Ser. 52, Cambridge Univ. Press, Cambridge-New York, (1981), pp. 103–123.

W.C. Chen, H.I. Lu, and Y.N. Yeh, Operations of interlaced trees and graceful trees, Southeast Asian Bulletin of Mathematics, 21, (1997), 337–348.

D. Dor and M. Tarsi, Graph decomposition is NP-complete: A comlete proof of Holyer’s conjecture, Siam J. Comput. 26, (1997), pp. 1166–1187.

P. Erdos, P. Hell, and P. Winkler, Bandwidth versus bandsize, Ann. Discrete Math., 41, (1989), 117–130.

K. Eshghi and P. Azimi, Applications of mathematical programming in graceful labeling of graphs, J. Appl. Math., 2004:1, (2004), 1–8.

W. Fang, A computational approach to the graceful tree conjecture, arXiv:1003.3045v1 [cs.DM]

J.A. Gallian, A dynamic survey of graph labeling, 20th edition, Electron. J. Combin., DS6, (2017).

L. Goddyn, R.B. Richter, and J. Širáň, Triangular embeddings of complete graphs from graceful labellings of paths, J. Combin. Theory Ser. B, 97, (2007), 964–970.

S.W. Golomb, How to number a graph, Graph Theory and Computing, R.C. Read, Academic Press, New York, (1972), 23–37.

P. Gvozdjak, On the Oberwolfach problem for cycles with multiple lengths, PhD Thesis, Simon Fraser University, (1993).

M. Horton, Graceful trees: Statistics and Algorithms, Honours thesis, University of Tasmania, (2003).

D.F. Hsu and A.D. Keedwell, Generalized complete mappings, neofields, sequenceable groups and block designs I, Pacific J. Math., 111, (1984), 317–332.

D.F. Hsu and A.D. Keedwell, Generalized complete mappings, neofields, sequenceable groups and block designs II, Pacific J. Math., 117, 1985, 291–312.

C. Huang, A. Kotzig, and A. Rosa, Further results on tree labellings, Util. Math., 21C, (1982), 31–48.

B.D. McKay, J.C. McLeod and I.M. Wanless, The number of transversals in a latin square, Des. Codes Cryptogr., 40, (2006), 269–284.

D. Morgan and R. Rees, Using Skolem and hooked-Skolem sequences to generate graceful trees, J. Combin. Math. Combin. Comput., 44, (2003), 47–63.

H.K. Ng, Gracefulness of a class of lobsters, Notices AMS, 7, (1986), 825–294.

Z. Nikoloski, N. Deo, and F. Suraweera, Generation of graceful trees, Congr. Numer., 157, (2002), 191–201.

A.M. Pastel and H. Raynaud. Les oliviers sont gracieux, Colloq. Grenoble, Publications Université de Grenoble, (1978).

G. Ringel, Problem 25, Theory of Graphs and its Application (Proc. Sympos. Smolenice 1963, Nakl. CSAV, Praha, 1964), 162, (1963).

G. Ringel, Map Color Theorem, Springer, 1974.

A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs, (Proc. Internat. Symposium, Rome, 1966), Gordon and Breach, N.Y. and Dunod Paris, (1967) 349–355.

A. Rosa, Labelling snakes, Ars Comb., 3, (1977), pp.67–74.

A. Rosa and J. Širáň, Bipartite labelings of trees and the gracesize, J. Graph Th., 19, (1995), pp.201–215.

G. Sethuraman and J. Jesintha, All banana trees are graceful, Advances and Applications Disc. Math., 4, (2009) pp.53–64.

F. Van Bussel, Relaxed graceful labellings of trees, Electron. J Combin., 9(1), (2002), R4.

J.G. Wang, D.J. Jin, X.G. Lu, and D. Zhang, The gracefulness of a class of lobster trees, Mathematical Computer Modelling, 20, (1994), 105–110.

I.M. Wanless, Transversals in latin squares, Quasigroups Related Systems, 15, (2007), 169–190.

T.M. Wang, C.C. Yang, L.H. Hsu, and E. Cheng, Infinitely many equivalent versions of the graceful tree conjecture, Appl. Anal. Discrete Math., 9(1), (2015), 1–12.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats