L(j,k)- and circular L(j,k)-labellings for the products of complete graphs
Tóm tắt
Let j and k be two positive integers with j≥k. An L(j,k)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between labels of any two adjacent vertices is at least j, and the difference between labels of any two vertices that are at distance two apart is at least k. The minimum range of labels over all L(j,k)-labellings of a graph G is called the λ
j,k
-number of G, denoted by λ
j,k
(G). A σ(j,k)-circular labelling with span m of a graph G is a function f:V(G)→{0,1,…,m−1} such that |f(u)−f(v)|
m
≥j if u and v are adjacent; and |f(u)−f(v)|
m
≥k if u and v are at distance two apart, where |x|
m
=min {|x|,m−|x|}. The minimum m such that there exists a σ(j,k)-circular labelling with span m for G is called the σ
j,k
-number of G and denoted by σ
j,k
(G). The λ
j,k
-numbers of Cartesian products of two complete graphs were determined by Georges, Mauro and Stein ((2000) SIAM J Discret Math 14:28–35). This paper determines the λ
j,k
-numbers of direct products of two complete graphs and the σ
j,k
-numbers of direct products and Cartesian products of two complete graphs.
Tài liệu tham khảo
Chang GJ, Kuo D (1996) The L(2,1)-labelling problem on graphs. SIAM J Discret Math 9:309–316
Georges JP, Mauro DW (1995) Generalized vertex labelings with a condition at distance two. Congr Numer 109:141–159
Georges JP, Mauro DW (1999) Some results on λ j k -numbers of the products of complete graphs. Congr Numer 140:141–160
Georges JP, Mauro DW (2003) Labeling trees with a condition at distance two. Discret Math 269:127–148
Georges JP, Mauro DW, Whittlesey MA (1994) Relating path coverings to vertex labellings with a condition at distance two. Discret Math 135:103–111
Georges JP, Mauro DW, Stein MI (2000) Labeling products of complete graphs with a condition at distance two. SIAM J Discret Math 14:28–35
Griggs JR, Yeh RK (1992) Labelling graphs with a condition at distance 2. SIAM J Discret Math 5:586–595
Hale WK (1980) Frequency assignment: theory and applications. Proc IEEE 68:1497–1514
Heuvel J, Leese RA, Shepherd MA (1998) Graph labeling and radio channel assignment. J Graph Theory 29:263–283
Jha PK (2000) Optimal L(2,1)-labeling of Cartesian products of cycles, with an application to independent domination. IEEE Trans Circuits Syst Fundam Theory Appl 47:1531–1534
Jha PK (2001) Optimal L(2,1)-labeling of strong products of cycles. IEEE Trans Circuits Syst Fundam Theory Appl 48:498–500
Jha PK, Narayanan A, Sood P, Sundaram K, Sunder V (2000) On L(2,1)-labelling of the Cartesian product of a cycle and a path. Ars Comb 55:81–89
Klavžar S, Vesel A (2003) Computing invariants on rotagraphs using dynamic algorithm approach: the case of (2,1)-colorings and independence numbers. Discret Appl Math 129:449–460
Liu DDF (2001) Hamiltonicity and circular distance two labellings. Discret Math 232:163–169
Liu DDF, Zhu X (2003) Circulant distance two labeling and circular chromatic number. Ars Comb 69:177–183
Sakai D (1994) Labelling chordal graphs: distance two condition. SIAM J Discret Math 7:133–140
Whittlesey MA, Georges JP, Mauro DW (1995) On the λ-number of Q n and related graphs. SIAM J Discret Math 8:499–506
Wu K, Yeh RK (2000) Labelling graphs with the circular difference. Taiwan J Math 4:397–405