On Lee's conjecture and some results
Lixia Fan ; Zhihe Liang
Discussiones Mathematicae Graph Theory, Tome 29 (2009), p. 481-498 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

S.M. Lee proposed the conjecture: for any n > 1 and any permutation f in S(n), the permutation graph P(Pₙ,f) is graceful. For any integer n > 1 and permutation f in S(n), we discuss the gracefulness of the permutation graph P(Pₙ,f) if f=∏k=0l-1(m+2k,m+2k+1), and ∏k=0l-1(m+4k,m+4k+2)(m+4k+1,m+4k+3) for any positive integers m and l.

Publié le : 2009-01-01
EUDML-ID : urn:eudml:doc:270816 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1459,
     author = {Lixia Fan and Zhihe Liang},
     title = {On Lee's conjecture and some results},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {29},
     year = {2009},
     pages = {481-498},
     zbl = {1193.05143},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1459}
}

Lixia Fan; Zhihe Liang. On Lee's conjecture and some results. Discussiones Mathematicae Graph Theory, Tome 29 (2009) pp. 481-498. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1459/

[000] [1] A. Rosa, On certain valuations of the vertices of a graph, in: Theory of Graphs, Proc. of Intemational Symposium, Rome 1966 (Gordon Breach, New York 1967), 349-355.

[001] [2] S.W. Golomb, How to number a graph? in: R.C. Read, ed., Graph Theory and Computing (Academic Press, New York, 1972) 23-27. | Zbl 0293.05150

[002] [3] Z. Liang, On the graceful conjecture of permutation graphs of paths, Ars Combin. 91 (2009) 65-82. | Zbl 1224.05449

[003] [4] J.A. Gallian, A dynamic survey of graph labeling, Electronic J. Combin. 14 (2007) DS#6, 1-180.

[004] [5] J.C. Bermond, Graceful graphs, radio antennae and Fench windmills, in: R.J. Wilson, ed., Graph Theory and Combinatorics (Pitman, London, 1979), 13-37. | Zbl 0447.05032

[005] [6] A.K. Dewdney, The search for an invisible ruler that will help radio astronomers to measure the earth, Scientific American, Dec. (1986) 16-19, doi: 10.1038/scientificamerican0186-16.

[006] [7] S.M. Lee, K.Y. Lai, Y.S. Wang and M.K. Kiang, On the graceful permutation graphs conjecture, Congr. Numer. 103 (1994) 193-201. | Zbl 0837.05105

[007] [8] M. Maheo, Strongly graceful graphs, Discrete Math. 29 (1980) 39-46, doi: 10.1016/0012-365X(90)90285-P.

[008] [9] C. Delorme, Two sets of graceful graphs, J. Graph Theory 4 (1980) 247-250, doi: 10.1002/jgt.3190040214. | Zbl 0437.05048

[009] [10] R.W. Frucht and J.A. Gallian, Labelling prisms, Ars Combin. 26 (1988) 69-82. | Zbl 0678.05053

[010] [11] J.A. Gallian, Labelling prisms and prism related graphs, Congress. Numer. 59 (1987) 89-100. | Zbl 0642.05050

[011] [12] Z. Liang, H. Zhang, N. Xu, S. Ye, Y. Fan and H. Ge, Gracefulness of five permutation graphs of paths, Utilitas Mathematica 72 (2007) 241-249. | Zbl 1121.05104

[012] [13] N. Han and Z. Liang, On the graceful permutation graphs conjecture, J. Discrete Math. Sci. & Cryptography 11 (2008) 501-526. | Zbl 1176.05073