Neighbour-Distinguishing Labellings of Families of Graphs

Autor(es)

Luiz, Atilio G. ; Campos, C. N.

• Tipo de documento: Artigo Científico
• Fonte: GRAPHS AND COMBINATORICS; v. 38, n. 3, p. 22-pg., 2022-06-01.

Resumo

A labelling of a graph G is a mapping pi : S -> L,where L subset of R and S is an element of{E(G), V(G) boolean OR E (G)} . If S = E(G), pi is an L-edge-labelling and, if S = V(G) boolean OR E(G), pi is an L-total-labelling. For each nu is an element of V(G), the colour of nu under pi is defined as c(pi)(nu) = Sigma(u nu is an element of E(G)) pi(u nu) if pi is an L-edge-labelling; and c(pi)(nu) = pi(nu) + Sigma(u nu is an element of E(G)) pi(u nu) if pi is an L-total-labelling. The pair (pi, c(pi)) is a neighbour-distinguishing L-edge-labelling (neighbour-distinguishing L-total-la-belling) if pi is an L-edge-labelling (G-total-labelling) and c(pi)(u) not equal c(pi)(nu) for every edge u nu is an element of E(G). In this work, we show that split graphs, regular cobipartite graphs, complete multipartite graphs and cubic graphs have neighbour-distinguishing {a, b, c}-edge-labellings, for distinct a, b,c is an element of R (in some cases a, b, c >= 0). For split graphs and regular cobipartite graphs we also prove they admit neighbour-distinguishing {a, b}-total-labellings. Furthermore, we show that flower snarks and some subfamilies of split graphs and regular cobipartite graphs have neighbour-distinguishing {a, b}-edge-labellings and prove that some families of split graphs do not have neighbour-distinguishing L-edge-labellings, for L= {a, 2a} and L= {0, a}, a, b is an element of R\{0}, a not equal b. (AU)

• Processo FAPESP: 14/16861-8 - Problemas de rotulação em grafos
• Beneficiário: Atilio Gomes Luiz
• Modalidade de apoio: Bolsas no Brasil - Doutorado