α-labeling number of trees

Chin Lin Shiue*, Hung-Lin Fu

*Corresponding author for this work

Research output: Contribution to journalArticle

4 Scopus citations

Abstract

In this paper, we prove that the α-labeling number of trees T, Tα ≤ ⌈ r / 2 ⌉ n where n = | E (T) | and r is the radius of T. This improves the known result Tα ≤ eO (sqrt(n log n)) tremendously and this upper bound is very close to the upper bound Tα ≤ n conjectured by Snevily. Moreover, we prove that a tree with n edges and radius r decomposes Kt for some t ≤ (r + 1) n2 + 1.

Original languageEnglish
Pages (from-to)3290-3296
Number of pages7
JournalDiscrete Mathematics
Volume306
Issue number24
DOIs
StatePublished - 28 Dec 2006

Keywords

  • α-labeling number
  • Tree decomposition

Fingerprint Dive into the research topics of 'α-labeling number of trees'. Together they form a unique fingerprint.

  • Cite this