词条 | Graceful labeling |
释义 |
In graph theory, a graceful labeling of a graph with m edges is a labeling of its vertices with some subset of the integers between 0 and m inclusive, such that no two vertices share a label, and each edge is uniquely identified by the absolute difference between its endpoints, such that this magnitude lies between 1 and m inclusive.[1] A graph which admits a graceful labeling is called a graceful graph. The name "graceful labeling" is due to Solomon W. Golomb; this class of labelings was originally given the name β-labelings by Alexander Rosa in a 1967 paper on graph labelings.[2] A major unproven conjecture in graph theory is the Graceful Tree conjecture or Ringel–Kotzig conjecture, named after Gerhard Ringel and Anton Kotzig, which hypothesizes that all trees are graceful. The Ringel–Kotzig conjecture is also known as the "graceful labeling conjecture". Kotzig once called the effort to prove the conjecture a "disease".[3] Another weaker version of graceful labelling is the near graceful labeling, in which the vertices can be labeled using some subset of the integers between 0 and m+1 inclusive, such that no two vertices share a label, and each edge is uniquely identified by the absolute difference between its endpoints, such that this magnitude lies between 1 and m+1 inclusive. Another conjecture in graph theory is the Rosa's Conjecture, named after Alexander Rosa, which says that all triangular cacti are graceful or nearly-graceful.[4] Selected results
See also
External links
References1. ^Virginia Vassilevska, "Coding and Graceful Labeling of trees." SURF 2001. PostScript 2. ^1 {{citation | last = Rosa | first = A. | contribution = On certain valuations of the vertices of a graph | location = New York | mr = 0223271 | pages = 349–355 | publisher = Gordon and Breach | title = Theory of Graphs (Internat. Sympos., Rome, 1966) | year = 1967}}. 3. ^{{citation | last1 = Huang | first1 = C. | last2 = Kotzig | first2 = A. | author2-link = Anton Kotzig | last3 = Rosa | first3 = A. | journal = Utilitas Mathematica | mr = 668845 | pages = 31–48 | title = Further results on tree labellings | volume = 21 | year = 1982}}. 4. ^{{citation|last=Rosa|first=A.|title=Cyclic Steiner Triple Systems and Labelings of Triangular Cacti|journal=Scientia|volume=1|pages=87--95|year=1988}}. 5. ^{{citation | last = Morgan | first = David | journal = Bulletin of the Institute of Combinatorics and its Applications | pages = 82–85 | title = All lobsters with perfect matchings are graceful | url = http://hdl.handle.net/10402/era.26923 | volume = 53 | year = 2008}}. 6. ^1 {{citation | last = Gallian | first = Joseph A. | author-link = Joseph Gallian | journal = Electronic Journal of Combinatorics | mr = 1668059 | page = Dynamic Survey 6, 43 pp. (389 pp. in 18th ed.) (electronic) | title = A dynamic survey of graph labeling | url = http://www.combinatorics.org/ojs/index.php/eljc/article/viewFile/DS6/pdf | volume = 5 | year = 1998}}. 7. ^{{citation | last1 = Aldred | first1 = R. E. L. | last2 = McKay | first2 = Brendan D. | author2-link = Brendan McKay | journal = Bulletin of the Institute of Combinatorics and its Applications | mr = 1621760 | pages = 69–72 | title = Graceful and harmonious labellings of trees | volume = 23 | year = 1998}}. 8. ^{{citation | last = Horton | first = Michael P. | author-link = Michael P. Horton | title = Graceful Trees: Statistics and Algorithms | url = http://eprints.utas.edu.au/19/ | year = 2003}}. 9. ^{{citation | last = Fang | first = Wenjie | arxiv = 1003.3045| title = A Computational Approach to the Graceful Tree Conjecture | year = 2010| bibcode = 2010arXiv1003.3045F}}. See also [https://web.archive.org/web/20120729224449/http://www.eleves.ens.fr/home/wfang/gtv/index_en.html Graceful Tree Verification Project] 10. ^{{citation | last = Kotzig | first = Anton | author-link = Anton Kotzig | doi = 10.1016/0095-8956(81)90031-9 | issue = 3 | journal = Journal of Combinatorial Theory, Series B | mr = 638285 | pages = 292–296 | title = Decompositions of complete graphs into isomorphic cubes | volume = 31 | year = 1981}}. 11. ^{{mathworld|title=Graceful graph|urlname=GracefulGraph}} Further reading
2 : Graph theory objects|Conjectures |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。