Nordhaus–Gaddum-type results for path covering and $$L(2,1)$$ -labeling numbers

Damei Lü (), Juan Du, Nianfeng Lin, Ke Zhang and Dan Yi
Additional contact information
Damei Lü: Nantong University
Juan Du: Nantong University
Nianfeng Lin: Nantong University
Ke Zhang: Nantong University
Dan Yi: Nantong University

Journal of Combinatorial Optimization, 2015, vol. 29, issue 2, No 11, 502-510

Abstract: Abstract 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\ge 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.

Keywords: Nordhaus–Gaddum-type result; $$L(2; 1)$$ -Labeling number; Path covering number (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9610-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:29:y:2015:i:2:d:10.1007_s10878-013-9610-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9610-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().