Discussiones Mathematicae Graph Theory (May 2018)
Irreducible No-Hole L(2, 1)-Coloring of Edge-Multiplicity-Paths-Replacement Graph
Abstract
An L(2, 1)-coloring (or labeling) of a simple connected graph G is a mapping f : V (G) → Z+ ∪ {0} such that |f(u)−f(v)| ≥ 2 for all edges uv of G, and |f(u) − f(v)| ≥ 1 if u and v are at distance two in G. The span of an L(2, 1)-coloring f, denoted by span(f), of G is max{f(v) : v ∈ V (G)}. The span of G, denoted by λ(G), is the minimum span of all possible L(2, 1)-colorings of G. For an L(2, 1)-coloring f of a graph G with span k, an integer l is a hole in f if l ∈ (0, k) and there is no vertex v in G such that f(v) = l. An L(2, 1)-coloring is a no-hole coloring if there is no hole in it, and is an irreducible coloring if color of none of the vertices in the graph can be decreased and yield another L(2, 1)-coloring of the same graph. An irreducible no-hole coloring, in short inh-coloring, of G is an L(2, 1)-coloring of G which is both irreducible and no-hole. For an inh-colorable graph G, the inh-span of G, denoted by λinh(G), is defined as λinh(G) = min{span(f) : f is an inh-coloring of G. Given a function h : E(G) → ℕ − {1}, and a positive integer r ≥ 2, the edge-multiplicity-paths-replacement graph G(rPh) of G is the graph obtained by replacing every edge uv of G with r paths of length h(uv) each. In this paper we show that G(rPh) is inh-colorable except possibly the cases h(e) ≥ 2 with equality for at least one but not for all edges e and (i) Δ(G) = 2, r = 2 or (ii) Δ (G) ≥ 3, 2 ≤ r ≤ 4. We find the exact value of λinh(G(rPh)) in several cases and give upper bounds of the same in the remaining. Moreover, we find the value of λ(G(rPh)) in most of the cases which were left by Lü and Sun in [L(2, 1)-labelings of the edge-multiplicity-paths-replacement of a graph, J. Comb. Optim. 31 (2016) 396–404].
Keywords
