On Lee's conjecture and some results

Lixia Fan; Zhihe Liang

Discussiones Mathematicae Graph Theory (2009)

  • Volume: 29, Issue: 3, page 481-498
  • ISSN: 2083-5892

Abstract

top
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 = 0 l - 1 ( m + 2 k , m + 2 k + 1 ) , and ∏ k = 0 l - 1 ( m + 4 k , m + 4 k + 2 ) ( m + 4 k + 1 , m + 4 k + 3 ) for any positive integers m and l.

How to cite

top

Lixia Fan, and Zhihe Liang. "On Lee's conjecture and some results." Discussiones Mathematicae Graph Theory 29.3 (2009): 481-498. <http://eudml.org/doc/270816>.

@article{LixiaFan2009,
abstract = {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 = 0\}^\{l-1\} (m+2k, m+2k+1)$, and $∏_\{k=0\}^\{l-1\} (m+4k,m+4k+2)(m+4k+1,m+4k+3)$ for any positive integers m and l.},
author = {Lixia Fan, Zhihe Liang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {permutation graph; graceful, Lee's conjecture; graceful Lee's conjecture},
language = {eng},
number = {3},
pages = {481-498},
title = {On Lee's conjecture and some results},
url = {http://eudml.org/doc/270816},
volume = {29},
year = {2009},
}

TY - JOUR
AU - Lixia Fan
AU - Zhihe Liang
TI - On Lee's conjecture and some results
JO - Discussiones Mathematicae Graph Theory
PY - 2009
VL - 29
IS - 3
SP - 481
EP - 498
AB - 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 = 0}^{l-1} (m+2k, m+2k+1)$, and $∏_{k=0}^{l-1} (m+4k,m+4k+2)(m+4k+1,m+4k+3)$ for any positive integers m and l.
LA - eng
KW - permutation graph; graceful, Lee's conjecture; graceful Lee's conjecture
UR - http://eudml.org/doc/270816
ER -

References

top
  1. [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. 
  2. [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. Zbl0293.05150
  3. [3] Z. Liang, On the graceful conjecture of permutation graphs of paths, Ars Combin. 91 (2009) 65-82. Zbl1224.05449
  4. [4] J.A. Gallian, A dynamic survey of graph labeling, Electronic J. Combin. 14 (2007) DS#6, 1-180. 
  5. [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. Zbl0447.05032
  6. [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. 
  7. [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. Zbl0837.05105
  8. [8] M. Maheo, Strongly graceful graphs, Discrete Math. 29 (1980) 39-46, doi: 10.1016/0012-365X(90)90285-P. 
  9. [9] C. Delorme, Two sets of graceful graphs, J. Graph Theory 4 (1980) 247-250, doi: 10.1002/jgt.3190040214. Zbl0437.05048
  10. [10] R.W. Frucht and J.A. Gallian, Labelling prisms, Ars Combin. 26 (1988) 69-82. Zbl0678.05053
  11. [11] J.A. Gallian, Labelling prisms and prism related graphs, Congress. Numer. 59 (1987) 89-100. Zbl0642.05050
  12. [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. Zbl1121.05104
  13. [13] N. Han and Z. Liang, On the graceful permutation graphs conjecture, J. Discrete Math. Sci. & Cryptography 11 (2008) 501-526. Zbl1176.05073

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.