On $$(s,t)$$ ( s , t ) -relaxed $$L(2,1)$$ L ( 2 , 1 ) -labeling of graphs

We initiate the study of relaxed $$L(2,1)$$ L ( 2 , 1 ) -labelings of graphs. Suppose $$G$$ G is a graph. Let $$u$$ u be a vertex of $$G$$ G . A vertex $$v$$ v is called an $$i$$ i -neighbor of $$u$$ u if $$d_G(u,v)=i$$ d G ( u , v ) = i . A $$1$$ 1 -neighbor of $$u$$ u is simply called a neighbor of $$u$$ u . Let $$s$$ s and $$t$$ t be two nonnegative integers. Suppose $$f$$ f is an assignment of nonnegative integers to the vertices of $$G$$ G . If the following three conditions are satisfied, then $$f$$ f is called an $$(s,t)$$ ( s , t ) -relaxed $$L(2,1)$$ L ( 2 , 1 ) -labeling of $$G$$ G : (1) for any two adjacent vertices $$u$$ u and $$v$$ v of $$G, f(u)\not =f(v)$$ G , f ( u ) ≠ f ( v ) ; (2) for any vertex $$u$$ u of $$G$$ G , there are at most $$s$$ s neighbors of $$u$$ u receiving labels from $$\{f(u)-1,f(u)+1\}$$ { f ( u ) - 1 , f ( u ) + 1 } ; (3) for any vertex $$u$$ u of $$G$$ G , the number of $$2$$ 2 -neighbors of $$u$$ u assigned the label $$f(u)$$ f ( u ) is at most $$t$$ t . The minimum span of $$(s,t)$$ ( s , t ) -relaxed $$L(2,1)$$ L ( 2 , 1 ) -labelings of $$G$$ G is called the $$(s,t)$$ ( s , t ) -relaxed $$L(2,1)$$ L ( 2 , 1 ) -labeling number of $$G$$ G , denoted by $$\lambda ^{s,t}_{2,1}(G)$$ λ 2 , 1 s , t ( G ) . It is clear that $$\lambda ^{0,0}_{2,1}(G)$$ λ 2 , 1 0 , 0 ( G ) is the so called $$L(2,1)$$ L ( 2 , 1 ) -labeling number of $$G$$ G . $$\lambda ^{1,0}_{2,1}(G)$$ λ 2 , 1 1 , 0 ( G ) is simply written as $$\widetilde{\lambda }(G)$$ λ ~ ( G ) . This paper discusses basic properties of $$(s,t)$$ ( s , t ) -relaxed $$L(2,1)$$ L ( 2 , 1 ) -labeling numbers of graphs. For any two nonnegative integers $$s$$ s and $$t$$ t , the exact values of $$(s,t)$$ ( s , t ) -relaxed $$L(2,1)$$ L ( 2 , 1 ) -labeling numbers of paths, cycles and complete graphs are determined. Tight upper and lower bounds for $$(s,t)$$ ( s , t ) -relaxed $$L(2,1)$$ L ( 2 , 1 ) -labeling numbers of complete multipartite graphs and trees are given. The upper bounds for $$(s,1)$$ ( s , 1 ) -relaxed $$L(2,1)$$ L ( 2 , 1 ) -labeling number of general graphs are also investigated. We introduce a new graph parameter called the breaking path covering number of a graph. A breaking path $$P$$ P is a vertex sequence $$v_1,v_2,\ldots ,v_k$$ v 1 , v 2 , … , v k in which each $$v_i$$ v i is adjacent to at least one vertex of $$v_{i-1}$$ v i - 1 and $$v_{i+1}$$ v i + 1 for $$i=2,3,\ldots ,k-1$$ i = 2 , 3 , … , k - 1 . A breaking path covering of $$G$$ G is a set of disjoint such vertex sequences that cover all vertices of $$G$$ G . The breaking path covering number of $$G$$ G , denoted by $$bpc(G)$$ b p c ( G ) , is the minimum number of breaking paths in a breaking path covering of $$G$$ G . In this paper, it is proved that $$\widetilde{\lambda }(G)= n+bpc(G^{c})-2$$ λ ~ ( G ) = n + b p c ( G c ) - 2 if $$bpc(G^{c})\ge 2$$ b p c ( G c ) ≥ 2 and $$\widetilde{\lambda }(G)\le n-1$$ λ ~ ( G ) ≤ n - 1 if and only if $$bpc(G^{c})=1$$ b p c ( G c ) = 1 . The breaking path covering number of a graph is proved to be computable in polynomial time. Thus, if a graph $$G$$ G is of diameter two, then $$\widetilde{\lambda }(G)$$ λ ~ ( G ) can be determined in polynomial time. Several conjectures and problems on relaxed $$L(2,1)$$ L ( 2 , 1 ) -labelings are also proposed.