Path covering number and L(2,1)-labeling number of graphs

Details Path covering number and L(2,1)-labeling number of graphs Path covering number and L(2,1)-labeling number of graphs

2012-04-10

arxiv.org/abs/1204.2306v1

Mathematics

Combinatorics

Scientific paper

A {\it path covering} of a graph $G$ is a set of vertex disjoint paths of $G$ containing all the vertices of $G$. The {\it path covering number} of $G$, denoted by $P(G)$, is the minimum number of paths in a path covering of $G$. An {\sl $k$-L(2,1)-labeling} of a graph $G$ is a mapping $f$ from $V(G)$ to the set ${0,1,...,k}$ such that $|f(u)-f(v)|\ge 2$ if $d_G(u,v)=1$ and $|f(u)-f(v)|\ge 1$ if $d_G(u,v)=2$. The {\sl L(2,1)-labeling number $\lambda (G)$} of $G$ is the smallest number $k$ such that $G$ has a $k$-L(2,1)-labeling. The purpose of this paper is to study path covering number and L(2,1)-labeling number of graphs. Our main work extends most of results in [On island sequences of labelings with a condition at distance two, Discrete Applied Maths 158 (2010), 1-7] and can answer an open problem in [On the structure of graphs with non-surjective L(2,1)-labelings, SIAM J. Discrete Math. 19 (2005), 208-223].

Affiliated with

Also associated with

No associations

Rating

Path covering number and L(2,1)-labeling number of graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Path covering number and L(2,1)-labeling number of graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Path covering number and L(2,1)-labeling number of graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-716737