| Autor: |
Lü, Damei, Du, Juan, Lin, Nianfeng, Zhang, Ke, Yi, Dan |
| Zdroj: |
Journal of Combinatorial Optimization; Feb2015, Vol. 29 Issue 2, p502-510, 9p |
| Abstrakt: |
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. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
Full text from SpringerLink