Abstract
For two positive integers j and k with j≥k, an L(j,k)-labeling of a graph G is an assignment of nonnegative integers to V(G) such that the difference between labels of adjacent vertices is at least j, and the difference between labels of vertices that are distance two apart is at least k. The span of an L(j,k)-labeling of a graph G is the difference between the maximum and minimum integers used by it. The L(j,k)-labelings-number of G is the minimum span over all L(j,k)-labelings of G. This paper focuses on L(d,1)-labelings-number of the edge-path-replacement G(P k ) of a graph G. Note that G(P 3) is the incidence graph of G. L(d,1)-labelings of the edge-path-replacement G(P k ) of a graph, called (d,1)-total labeling of G, was introduced in 2002 by Havet and Yu (Workshop graphs and algorithms, 2003; Discrete Math 308:493–513, 2008). Havet and Yu (Discrete Math 308:498–513, 2008) obtained the bound \(\Delta+ d-1\leq\lambda^{T}_{d}(G)\leq2\Delta+ d-1\) and conjectured \(\lambda^{T}_{d}(G)\leq\Delta+2d-1\). In (Lü in J Comb Optim, to appear; Zhejiang University, submitted), we worked on L(2,1)-labelings-number and L(1,1)-labelings-number of the edge-path-replacement G(P k ) of a graph G, and obtained that λ(G(P k ))≤Δ+2 for k≥5, and conjecture λ(G(P 4))≤Δ+2 for any graph G with maximum degree Δ. In this paper, we will study L(d,1)-labelings-number of the edge-path-replacement G(P k ) of a graph G for d≥3 and k≥4.
Similar content being viewed by others
References
Borodin OV, Kostochka AV, Woodall DR (1996) Total colorings of planar graphs with large maximum degree. J Graph Theory 26:53–59
Borodin OV, Kostochka AV, Woodall DR (1997) List edge and list total colourings of multigraphs. J Comb Theory, Ser B 71:184–204
Borodin OV, Kostochka AV, Woodall DR (1998) Total colorings of planar graphs with large girth. Eur J Comb 19:19–24
Erwin DJ, Georges JP, Mauro DW (2003) On labeling the vertices of products of complete graphs with distance constraints. Nav Res Logist 50
Frobenius G (1992) Über Matrizen aus nicht negativen Elementen[M]. Sitzungsberichte Preuss, Akad Wiss Berlin, pp. 456–477
Georges JP, Mauro DW (1995) Some results on \(\lambda^{j}_{k}\)-numbers of the products of complete graphs. Congr Numer 109:141–159
Georges JP, Mauro DW, Stein MI (2000) Labeling products of complete graphs with a condition at distance two. SIAM J Discrete Math 14:28–35
Griggs JR, Yeh RK (1992) Labeling graphs with a condition at distance two. SIAM J Discrete Math 5:586–595
Havet F (2003) (d,1)-total labeling of graphs. In: Workshop graphs and algorithms, Dijon, France
Havet F, Yu ML (2008) (p,1)-total labeling of graphs. Discrete Math 308:498–513
Isobe S, Zhou X, Nishizeki T (2001) Total colorings of degenerated graphs. In: ICALP 2001. LNCS, vol 207b, pp 506–517
Jha, PK (2000) Optimal L(2,1)-labeling of Cartesian products of cycles, with an application to independent domination. IEEE Trans Circuits Syst I, Fundam Theory 47:1531–1534
Jha, PK (2001) Optimal L(2,1)-labelings of strong Cartesian products of cycles. IEEE Trans Circuits Syst I, Fundam Theory 48:498–500
Jha PK, Klavz̆ar S, Vesel A (2005a) L(2,1)-labeling of direct products of paths and cycles. Discrete Appl Math 145:317–325
Jha PK, Klavz̆ar S, Vesel A (2005b) Optimal L(d,1)-labelings of certain directed products of cycles and Cartesian products of cycles. Discrete Appl Math 152:257–265
Jha PK, Narayanan A, Sood P, Sundaran K, Sunder V (2000) On L(2,1)-labeling of the Cartesian product of a cycle and a path. Ars Comb 55:81–89
Kuo D, Yan J-H (2004) On L(2,1)-labeling of Cartesian products of paths and cycles. Discrete Math 283:137–144
Lü DM (2012a) L(2,1)-labelings of the edge-path-replacement of a graph. J Comb Optim. doi:10.1007/s10878-012-9470-2
Lü DM (2012b) L(1,1)-labelings of the edge-path-replacement of a graph. Zhejiang University (submitted)
Rosenfeld M (1971) On the total coloring of certain graphs. Isr J Math 9:396–402
Schwarz C, Troxell D (2006) L(2,1)-labeling of Cartesian products of two cycles. Discrete Appl Math 154:1522–1540
Vijayadita N (1971) On total chromatic number of a graph. J Lond Math Soc 3(2):405–408
Whittlesey MA, Georges JP, Mauro DW (1995) On the λ-number of Q n and related graphs. SIAM J Discrete Math 8:449–506
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by NSFC under grant 10671033 and the Natural Science Foundation of Nantong University 11Z055 and 11Z056.
Rights and permissions
About this article
Cite this article
Lü, D., Lin, N. L(d,1)-labelings of the edge-path-replacement of a graph. J Comb Optim 26, 819–831 (2013). https://doi.org/10.1007/s10878-012-9487-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-012-9487-6