On L(2,1) and Prime cordial labelings

Document Type : Original Article

Authors

1 Department of Mathematics, Faculty of Science, Ain Shams University, Abbassia, Cairo, Egypt.

2 Department of Mathematics, M.T.C., Kobry ElKobba, Cairo, Egypt.

Abstract

Abstract
An L(2, 1)-labeling of a graph 𝐺 is a function 𝑓 from the vertex set 𝑉(𝐺) into the set of nonnegative integers such that |𝑓(𝑥)−𝑓(𝑦)|≥2 if 𝑑(𝑥,𝑦)=1 and |𝑓(𝑥)−𝑓(𝑦)|≥1 if 𝑑(𝑥,𝑦)=2, where 𝑑(𝑥,𝑦) denotes the distance between 𝑥 and 𝑦 in 𝑉(𝐺). The L(2, 1)-labeling number, 𝜆(𝐺), of 𝐺 is the minimum 𝑘 where 𝐺 has an L(2, 1)-labeling 𝑓 with 𝑘 being the absolute difference between the largest and smallest image points of 𝑓 . A prime cordial labeling of a graph 𝐺 with vertex set 𝑉 is a bijection 𝑓 from 𝑉 to {1,2,...,|𝑉 |} such that if each edge 𝑢𝑣 is assigned the label 1 if gcd(𝑓(𝑢),𝑓(𝑣))=1 and 0 if gcd(𝑓(𝑢),𝑓(𝑣))>1, then the number of edges labeled with 0 and the number of edges labeled with 1 differ by at most 1. In this paper we find the labeling number 𝜆(𝐺)for some families of graphs, and we give an upper bound for the number of edges of any graph on 𝑛 vertices to have a prime cordial labeling, and we compare this upper bound with the number of edges of two families of graphs.

Keywords

Files

Share

How to cite

Statistics