On The Total Irregularity Strength of Regular Graphs

Abstract

Let 𝐺 = (𝑉, 𝐸) be a graph. A total labeling 𝑓: 𝑉 ∪ 𝐸 → {1, 2, ⋯ , 𝑘} is called a totally irregular total 𝑘-labeling of 𝐺 if every two distinct vertices 𝑥 and 𝑦 in 𝑉 satisfy 𝑤𝑓(𝑥) ≠ 𝑤𝑓(𝑦) and every two distinct edges 𝑥1𝑥2 and 𝑦1𝑦2 in 𝐸 satisfy 𝑤𝑓(𝑥1𝑥2) ≠ 𝑤𝑓(𝑦1𝑦2), where 𝑤𝑓(𝑥) = 𝑓(𝑥) + Σ𝑥𝑧∈𝐸(𝐺) 𝑓(𝑥𝑧) and 𝑤𝑓(𝑥1𝑥2) = 𝑓(𝑥1) + 𝑓(𝑥1𝑥2) + 𝑓(𝑥2). The minimum 𝑘 for which a graph 𝐺 has a totally irregular total 𝑘-labeling is called the total irregularity strength of 𝐺, denoted by 𝑡𝑠(𝐺). In this paper, we consider an upper bound on the total irregularity strength of 𝑚 copies of a regular graph. Besides that, we give a dual labeling of a totally irregular total 𝑘-labeling of a regular graph and we consider the total irregularity strength of 𝑚 copies of a path on two vertices, 𝑚 copies of a cycle, and 𝑚 copies of a prism 𝐶𝑛 □ 𝑃2.

Keywords

• cycle
• dual labeling
• path
• prism
• regular graph
• the total irregularity strength
• totally irregular total k-labeling