Browsing by Author "Perera, A.A.I."

Filter results by typing the first few letters
Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Prime labeling of scorpion graphs
    (Faculty of Science, University of Kelaniya, Sri Lanka, 2020) Thennakoon, T.R.D.S.M.; Weerarathna, M.D.M.C.P.; Perera, A.A.I.
    The concept of prime labeling was introduced by Roger Entringer. Around 1980, he conjectured that all trees have prime labeling which has not been proved yet. In 2011, The Entringer’s conjecture for trees of sufficiently large order was proved by Haxell, Pikhurko, and Taraz. A graph 𝐺 = (𝑉(𝐺), 𝐸(𝐺)) with |𝑉(𝐺)| vertices is said to have prime labeling, if there exists a bijection mapping 𝑓: 𝑉(𝐺) → {1,2,3, … , |𝑉(𝐺)|} such that for each edge 𝑒 = 𝑢𝑣 in 𝐸(𝐺), 𝑓(𝑢) and 𝑓(𝑣) are relatively prime, where 𝑉(𝐺) and 𝐸(𝐺) are the vertex set and the edge set of 𝐺 respectively. Two integers are said to be relatively prime, if their greatest common divisor is 1. Graph 𝐺 which admits prime labeling is called a prime graph. Much work has been done on various types of prime labeling problems including the shape of some insects and small animals, such as caterpillar, spider, cockroach, snake, etc. In the present work, we focus on prime labeling of a special type of a simple undirected finite graph called scorpion graph, denoted by 𝑆(2𝑝,2𝑞,𝑟) . Scorpion graph gets its name from its shape, which resembles a scorpion, having 2𝑝 + 2𝑞 + 𝑟 vertices (𝑝 ≥ 1, 𝑞 ≥ 2, 𝑟 ≥ 2) which are placed in head, body, and tail respectively. If 𝑃𝑛 denotes the path on 𝑛 vertices, then the Cartesian product 𝑃𝑛 × 𝑃𝑚, where 𝑛 ≥ 𝑚, is called a grid graph. If 𝑚 = 2, then the graph is called a ladder graph. To prove that the scorpion graphs have prime labeling, we used two results that have already been proved for ladder graphs. Those results are: if 𝑛 + 1 is prime, then 𝑃𝑛 × 𝑃2 has a prime labeling and if 2𝑛 + 1 is prime, then 𝑃𝑛 × 𝑃2 has a consecutive cyclic prime labeling with the value 1 assigned to the vertex 𝑣1. In our work, we prove Scorpion graph is prime when 𝑛 + 1 and 2𝑛 + 1 are prime. As a future work, we are planning to generalize results for scorpion graphs with walking legs.