Neighbour-distinguishing labellings of powers of paths and powers of cycles

Atílio G. Luiz (), C. N. Campos (), Simone Dantas () and Diana Sasaki ()
Additional contact information
Atílio G. Luiz: Federal University of Ceará
C. N. Campos: University of Campinas
Simone Dantas: Fluminense Federal University
Diana Sasaki: Rio de Janeiro State University

Journal of Combinatorial Optimization, 2020, vol. 39, issue 4, No 5, 1038-1059

Abstract: Abstract A labelling of a graph G is a mapping $$\pi :S \rightarrow {\mathcal {L}}$$π:S→L, where $${\mathcal {L}}\subset {\mathbb {R}}$$L⊂R and $$S \subseteq V(G)\cup E(G)$$S⊆V(G)∪E(G). If $$S=E(G)$$S=E(G), $$\pi $$π is an $${\mathcal {L}}$$L-edge-labelling and, if $$S=V(G)\cup E(G)$$S=V(G)∪E(G), $$\pi $$π is an $${\mathcal {L}}$$L-total-labelling. For each $$v\in V(G)$$v∈V(G), the colour of v under $$\pi $$π is defined as $$C_{\pi }(v) = \sum _{uv \in E(G)}{\pi (uv)}$$Cπ(v)=∑uv∈E(G)π(uv) if $$\pi $$π is an $${\mathcal {L}}$$L-edge-labelling; and $$C_{\pi }(v) = \pi (v)+\sum _{uv \in E(G)}{\pi (uv)}$$Cπ(v)=π(v)+∑uv∈E(G)π(uv) if $$\pi $$π is an $${\mathcal {L}}$$L-total-labelling. Labelling $$\pi $$π is a neighbour-distinguishing $${\mathcal {L}}$$L-edge-labelling (neighbour-distinguishing $${\mathcal {L}}$$L-total-labelling) if $$\pi $$π is an $${\mathcal {L}}$$L-edge-labelling ($${\mathcal {L}}$$L-total-labelling) and $$C_{\pi }(u)\ne C_{\pi }(v)$$Cπ(u)≠Cπ(v), for every edge $$uv \in E(G)$$uv∈E(G). In 2004, Karónski, Łuczac and Thomasson posed the 1,2,3-Conjecture, which states that every simple graph with no isolated edge has a neighbour-distinguishing $$\{1,2,3\}$${1,2,3}-edge-labelling. In 2010, Przybyło and Woźniak posed the 1,2-Conjecture, which states that every simple graph has a neighbour-distinguishing $$\{1,2\}$${1,2}-total-labelling. In this work, we contribute to the study of these conjectures by verifying the 1,2,3-Conjecture and 1,2-Conjecture for powers of paths and powers of cycles. We also obtain generalizations of these results: we prove that all powers of paths have neighbour-distinguishing $$\{t,2t\}$${t,2t}-total-labellings and neighbour-distinguishing $$\{t,2t,3t\}$${t,2t,3t}-edge-labellings, for $$t\in {\mathbb {R}}\backslash \{0\}$$t∈R\{0}; and we prove that all powers of cycles have neighbour-distinguishing $$\{a,b\}$${a,b}-total-labellings, and neighbour-distinguishing $$\{t,2t,3t\}$${t,2t,3t}-edge-labellings, for $$a,b,t\in {\mathbb {R}}$$a,b,t∈R, $$a\ne b$$a≠b and $$t\ne 0$$t≠0

Keywords: Neighbour-distinguishing labelling; 1; 2; 3 Conjecture; 1; 2 Conjecture; Powers of paths; Powers of cycles; 05C15; 05C38; 05C22 (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00540-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:39:y:2020:i:4:d:10.1007_s10878-020-00540-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00540-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().