A Nordhaus-Gaddum-type result is a (tight) lower or upper bound on the sum (or product) of a parameter of a graph and its complement. The path covering number c(G) of a graph is the smallest number of vertex-disjoint paths needed to cover the vertices of the graph. 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 Nordhaus-Gaddum-type results for path covering and L(2, 1)-labeling numbers.
展开▼
