The Study on the Upper-bound of Labeling Number for Chordal and Permutation Graphs


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 6, No. 8, pp. 2124-2132, Aug. 1999
10.3745/KIPSTE.1999.6.8.2124,   PDF Download:

Abstract

Given a graph G=(V, E), Ld = (2, 1)-labeling of G is a function f : V(G) -> [0, ∞) such that, if v1,v2%u2208V are adjacent, f(x) - f(y) ≥ 2d, and if the distance between v1 and v2 is two, f(x) - f(y) ≥ d, where dG(v1, v2) is the shortest distance between v1 and v2 in G. The L(2, 1)-labeling number λ(G) is the smallest number m such that G has an L(2, 1)-labeling f with maximum m of f(v) for v∈V. This problem has been studied by Griggs, Yeh and Sakai for the various classes of graphs. In this paper, we discuss the upper-bound of λ(G) for a chordal graph G and that of λ(G') for a permutation graph G'.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
J. T. Eui and H. K. Hee, "The Study on the Upper-bound of Labeling Number for Chordal and Permutation Graphs," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 6, no. 8, pp. 2124-2132, 1999. DOI: 10.3745/KIPSTE.1999.6.8.2124.

[ACM Style]
Jeong Tae Eui and Han Keun Hee. 1999. The Study on the Upper-bound of Labeling Number for Chordal and Permutation Graphs. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 6, 8, (1999), 2124-2132. DOI: 10.3745/KIPSTE.1999.6.8.2124.