Proper gap-labellings: on the edge and vertex variants

• Celso A. Weffort-Santos UNICAMP
• Christiane N. Campos UNICAMP
• Rafael C. S. Schouery UNICAMP

DOI: https://doi.org/10.5753/ctd.2019.6343

Resumo

Given a simple graph G, an ordered pair (π, cπ) is said to be a gap- [k]-edge-labelling (resp. gap-[k]-vertex-labelling) ofG ifπ is an edge-labelling (vertex-labelling) on the set {1, . . . , k}, and cπ is a proper vertex-colouring such that every vertex of degree at least two has its colour induced by the largest difference among the labels of its incident edges (neighbours). The decision problems associated with these labellings are NP-complete for k ≥ 3, and even when k = 2 for some classes of graphs. This thesis presents a study of the computational complexity of these problems, structural properties for certain families of graphs and several labelling algorithms and techniques. First, we present an NP-completeness result for the family of subcubic bipartite graphs. Second, we present polynomial-time algorithms for families ofgraphs. Third, we introduce a new parameter associated with gap-[k]-vertex-labellings ofgraphs.

Palavras-chave: Rotulações por gap, rotulações próprias, colorações de grafos

Referências

Brandt, A., Moran, B., Nepal, K., Pfender, F., and Sigler, D. (2016). Local gap colorings from edge labelings. Australasian Journal ofCombinatorics, 65(3):200 – 211. Dehghan, A., Sadeghi, M., and Ahadi, A. (2013). Algorithmic complexity of proper labeling problems. Theoretical Computer Science, 495:25 – 36.

Dehghan, A., Sadeghi, M., and Ahadi, A. (2013). Algorithmic complexity of proper labeling problems. Theoretical Computer Science, 495:25 – 36.

Tahraoui, M. A., Duchˆene, E., and Kheddouci, H. (2012). Gap vertex-distinguishing edge colorings of graphs. Discrete Mathematics, 312(20):3011 – 3025.

Weffort-Santos, C. A. (2018). Proper gap-labellings: on the edge and vertex variants. Master’s thesis, University of Campinas.

Weffort-Santos, C. A., Campos, C. N., and Schouery, R. C. S. (2017). Tight bounds for gap-labellings. In Anais do XXXVII Congresso da Sociedade Brasileira de Computac¸ ˜ao, pages 119–122.

Weffort-Santos, C. A., Campos, C. N., and Schouery, R. C. S. (2018). Proper gap- labellings of unicyclic graphs. In Anais do VIII Latin American Workshop on Cliques in Graphs, page 34.

Weffort-Santos, C. A., Campos, C. N., and Schouery, R. C. S. (2019a). On the complexity of gap-[2]-vertex-labellings of subcubic bipartite graphs. Accepted in X LAGOS’2019.

Weffort-Santos, C. A., Campos, C. N., and Schouery, R. C. S. (2019b). Proper gap- labellings of unicyclic graphs. Accepted in the Special Issue of Matem´atica Contem- porˆanea for the LAWCG’2018 conference.