Distance Two Surjective Labelling of Paths and Interval Graphs

Abstract

Graph labelling problem has been broadly studied for a long period for its applications, especially in frequency assignment in (mobile) communication system, <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" id="M1"> <a:mi>X</a:mi> </a:math> -ray crystallography, circuit design, etc. Nowadays, surjective <c:math xmlns:c="http://www.w3.org/1998/Math/MathML" id="M2"> <c:mi>L</c:mi> <c:mfenced open="(" close=")" separators="|"> <c:mrow> <c:mn>2,1</c:mn> </c:mrow> </c:mfenced> </c:math> -labelling is a well-studied problem. Motivated from the <h:math xmlns:h="http://www.w3.org/1998/Math/MathML" id="M3"> <h:mi>L</h:mi> <h:mfenced open="(" close=")" separators="|"> <h:mrow> <h:mn>2,1</h:mn> </h:mrow> </h:mfenced> </h:math> -labelling problem and the importance of surjective <m:math xmlns:m="http://www.w3.org/1998/Math/MathML" id="M4"> <m:mi>L</m:mi> <m:mfenced open="(" close=")" separators="|"> <m:mrow> <m:mn>2,1</m:mn> </m:mrow> </m:mfenced> </m:math> -labelling problem, we consider surjective <r:math xmlns:r="http://www.w3.org/1998/Math/MathML" id="M5"> <r:mi>L</r:mi> <r:mfenced open="(" close=")" separators="|"> <r:mrow> <r:mn>2,1</r:mn> </r:mrow> </r:mfenced> </r:math> -labelling ( <w:math xmlns:w="http://www.w3.org/1998/Math/MathML" id="M6"> <w:mtext>SL</w:mtext> <w:mn>21</w:mn> </w:math> -labelling) problems for paths and interval graphs. For any graph <y:math xmlns:y="http://www.w3.org/1998/Math/MathML" id="M7"> <y:mi>G</y:mi> <y:mo>=</y:mo> <y:mfenced open="(" close=")" separators="|"> <y:mrow> <y:mi>V</y:mi> <y:mo>,</y:mo> <y:mi>E</y:mi> </y:mrow> </y:mfenced> </y:math> , an <db:math xmlns:db="http://www.w3.org/1998/Math/MathML" id="M8"> <db:mtext>SL</db:mtext> <db:mn>21</db:mn> </db:math> -labelling is a mapping <fb:math xmlns:fb="http://www.w3.org/1998/Math/MathML" id="M9"> <fb:mi>φ</fb:mi> <fb:mo>:</fb:mo> <fb:mi>V</fb:mi> <fb:mo>⟶</fb:mo> <fb:mfenced open="{" close="}" separators="|"> <fb:mrow> <fb:mn>1,2</fb:mn> <fb:mo>,</fb:mo> <fb:mo>…</fb:mo> <fb:mo>,</fb:mo> <fb:mi>n</fb:mi> </fb:mrow> </fb:mfenced> </fb:math> so that, for every pair of nodes <kb:math xmlns:kb="http://www.w3.org/1998/Math/MathML" id="M10"> <kb:mi>u</kb:mi> </kb:math> and <mb:math xmlns:mb="http://www.w3.org/1998/Math/MathML" id="M11"> <mb:mi>v</mb:mi> </mb:math> , if <ob:math xmlns:ob="http://www.w3.org/1998/Math/MathML" id="M12"> <ob:mi>d</ob:mi> <ob:mfenced open="(" close=")" separators="|"> <ob:mrow> <ob:mi>u</ob:mi> <ob:mo>,</ob:mo> <ob:mi>v</ob:mi> </ob:mrow> </ob:mfenced> <ob:mo>=</ob:mo> <ob:mn>1</ob:mn> </ob:math> , then <tb:math xmlns:tb="http://www.w3.org/1998/Math/MathML" id="M13"> <tb:mfenced open="|" close="|" separators="|"> <tb:mrow> <tb:mi>φ</tb:mi> <tb:mfenced open="(" close=")" separators="|"> <tb:mrow> <tb:mi>u</tb:mi> </tb:mrow> </tb:mfenced> <tb:mo>−</tb:mo> <tb:mi>φ</tb:mi> <tb:mfenced open="(" close=")" separators="|"> <tb:mrow> <tb:mi>v</tb:mi> </tb:mrow> </tb:mfenced> </tb:mrow> </tb:mfenced> <tb:mo>≥</tb:mo> <tb:mn>2</tb:mn> </tb:math> ; and if <ec:math xmlns:ec="http://www.w3.org/1998/Math/MathML" id="M14"> <ec:mi>d</ec:mi> <ec:mfenced open="(" close=")" separators="|"> <ec:mrow> <ec:mi>u</ec:mi> <ec:mo>,</ec:mo> <ec:mi>v</ec:mi> </ec:mrow> </ec:mfenced> <ec:mo>=</ec:mo> <ec:mn>2</ec:mn> </ec:math> , then <jc:math xmlns:jc="http://www.w3.org/1998/Math/MathML" id="M15"> <jc:mfenced open="|" close="|" separators="|"> <jc:mrow> <jc:mi>φ</jc:mi> <jc:mfenced open="(" close=")" separators="|"> <jc:mrow> <jc:mi>u</jc:mi> </jc:mrow> </jc:mfenced> <jc:mo>−</jc:mo> <jc:mi>φ</jc:mi> <jc:mfenced open="(" close=")" separators="|"> <jc:mrow> <jc:mi>v</jc:mi> </jc:mrow> </jc:mfenced> </jc:mrow> </jc:mfenced> <jc:mo>≥</jc:mo> <jc:mn>1</jc:mn> </jc:math> , and every label <uc:math xmlns:uc="http://www.w3.org/1998/Math/MathML" id="M16"> <uc:mn>1,2</uc:mn> <uc:mo>,</uc:mo> <uc:mo>…</uc:mo> <uc:mo>,</uc:mo> <uc:mi>n</uc:mi> </uc:math> is used exactly once, where <wc:math xmlns:wc="http://www.w3.org/1998/Math/MathML" id="M17"> <wc:mi>d</wc:mi> <wc:mfenced open="(" close=")" separators="|"> <wc:mrow> <wc:mi>u</wc:mi> <wc:mo>,</wc:mo> <wc:mi>v</wc:mi> </wc:mrow> </wc:mfenced> </wc:math> represents the distance between the nodes <bd:math xmlns:bd="http://www.w3.org/1998/Math/MathML" id="M18"> <bd:mi>u</bd:mi> </bd:math> and <dd:math xmlns:dd="http://www.w3.org/1998/Math/MathML" id="M19"> <dd:mi>v</dd:mi> </dd:math> , and <fd:math xmlns:fd="http://www.w3.org/1998/Math/MathML" id="M20"> <fd:mi>n</fd:mi> </fd:math> </jats

Topics & Concepts