×

On the total vertex-irregular strength of a disjoint union of \(t\) copies of a path. (English) Zbl 1197.05130

Summary: For a simple graph \(G\) with the vertex set \(V\) and the edge set \(E\), a labelling \(\lambda:V\cup E\to\{1,2,3,\dots,k\}\) is called a vertex-irregular total \(k\)-labelling of \(G\) if for any two different vertices \(x\) and \(y\) in \(V\) we have \(wt(x)\neq wt(y)\) where \(wt(x)= \lambda(x)+ \sum_{xy\in E}\lambda(xy)\). The total vertex-irregular strength, denoted by \(tvs(G)\), is the small est positive integer \(k\) for which \(G\) has a vertex-irregular total \(k\)-labelling. In this paper, we determine the total vertex-irregular strength of a disjoint union of t copies of a path, denoted by \(tP_n\). We prove that for any \(t\geq 2\),
\[ tvs(tP_n)=\begin{cases} t &\text{for }n=1,\\ t+1 &\text{for }2\leq n\leq3,\\ \big\lceil\frac{nt+1}{3}\big\rceil &\text{for }n\geq 4. \end{cases} \]

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
PDF BibTeX XML Cite