Path covering number and(2, 1)L(2, 1)-labeling number of graphs
Lists
Only you see this
Abstract
A path covering of a graph G<math><mi is="true">G</mi></math> is a set of vertex disjoint paths of G<math><mi is="true">G</mi></math> containing all the vertices of G<math><mi is="true">G</mi></math>. The path covering number of G<math><mi is="true">G</mi></math>, denoted by P(G)<math><mi is="true">P</mi><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow></math>, is the minimum number of paths in a path covering of G<math><mi is="true">G</mi></math>. A k<math><mi is="true">k</mi></math>-L(2,1)<math><mi is="true">L</mi><mrow is="true"><mo is="true">(</mo><mn is="true">2</mn><mo is="true">,</mo><mn is="true">1</mn><mo is="true">)</mo></mrow></math>-labeling of a graph G<math><mi is="true">G</mi></math> is a mapping f<math><mi is="true">f</mi></math> from V(G)<math><mi is="true">V</mi><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow></math> to the set {0,1,…,k}<math><mrow is="true"><mo is="true">{</mo><mn is="true">0</mn><mo is="true">,</mo><mn is="true">1</mn><mo is="true">,</mo><mo is="true">…</mo><mo is="true">,</mo><mi is="true">k</mi><mo is="true">}</mo></mrow></math> such that |f(u)−f(v)|≥2<math><mrow is="true"><mo is="true">|</mo><mi is="true">f</mi><mrow is="true"><mo is="true">(</mo><mi is="true">u</mi><mo is="true">)</mo></mrow><mo is="true">−</mo><mi is="true">f</mi><mrow is="true"><mo is="true">(</mo><mi is="true">v</mi><mo is="true">)</mo></mrow><mo is="true">|</mo></mrow><mo is="true">≥</mo><mn is="true">2</mn></math> if dG(u,v)=1<math><msub is="true"><mrow is="true"><mi is="true">d</mi></mrow><mrow is="true"><mi is="true">G</mi></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">u</mi><mo is="true">,</mo><mi is="true">v</mi><mo is="true">)</mo></mrow><mo is="true">=</mo><mn is="true">1</mn></math> and |f(u)−f(v)|≥1<math><mrow is="true"><mo is="true">|</mo><mi is="true">f</mi><mrow is="true"><mo is="true">(</mo><mi is="true">u</mi><mo is="true">)</mo></mrow><mo is="true">−</mo><mi is="true">f</mi><mrow is="true"><mo is="true">(</mo><mi is="true">v</mi><mo is="true">)</mo></mrow><mo is="true">|</mo></mrow><mo is="true">≥</mo><mn is="true">1</mn></math> if dG(u,v)=2<math><msub is="true"><mrow is="true"><mi is="true">d</mi></mrow><mrow is="true"><mi is="true">G</mi></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">u</mi><mo is="true">,</mo><mi is="true">v</mi><mo is="true">)</mo></mrow><mo is="true">=</mo><mn is="true">2</mn></math>. The L(2,1)<math><mi is="true">L</mi><mrow is="true"><mo is="true">(</mo><mn is="true">2</mn><mo is="true">,</mo><mn is="true">1</mn><mo is="true">)</mo></mrow></math>-labeling numberλ(G)<math><mi is="true">λ</mi><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow></math> of G<math><mi is="true">G</mi></math> is the smallest number k<math><mi is="true">k</mi></math> such that G<math><mi is="true">G</mi></math> has a k<math><mi is="true">k</mi></math>-L(2,1)<math><mi is="true">L</mi><mrow is="true"><mo is="true">(</mo><mn is="true">2</mn><mo is="true">,</mo><mn is="true">1</mn><mo is="true">)</mo></mrow></math>-labeling. The purpose of this paper is to study path covering numbers and L(2,1)<math><mi is="true">L</mi><mrow is="true"><mo is="true">(</mo><mn is="true">2</mn><mo is="true">,</mo><mn is="true">1</mn><mo is="true">)</mo></mrow></math>-labeling numbers of graphs. Our main work extends most of the results in [S.S. Adams, A. Trazkovich, D.S. Troxell, B. Westgate, On island sequences of labelings with a condition at distance two, Discrete Appl. Math. 158 (2010) 1–7] and can answer an open problem in [J. Georges, D.W. Mauro, On the structure of graphs with non-surjective L<math><mi is="true">L</mi></math>(2, 1)-labelings, SIAM J. Discrete Math. 19 (2005) 208–223].
BibTeX
@inproceedings{lu2013path,
author = {Changhong Lu and Qing Zhou},
title = {{Path covering number and(2, 1)L(2, 1)-labeling number of graphs}},
booktitle = {Discret. Appl. Math},
year = {2013},
url = {https://openreview.net/forum?id=6DGz1jBCfJ},
}Loading related content...