Prime labeling of scorpion graphs
Date
2020
Journal Title
Journal ISSN
Volume Title
Publisher
Faculty of Science, University of Kelaniya, Sri Lanka
Abstract
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.
Description
Keywords
Ladder graph, Prime labeling, Prime graphs, Scorpion graph
Citation
Thennakoon, T.R.D.S.M., Weerarathna, M.D.M.C.P. and Perera, A.A.I. (2020). Prime labeling of scorpion graphs. In : International Conference on Applied and Pure Sciences, 2020. Faculty of Science, University of Kelaniya, Sri Lanka, p.49.