Busca avançada
Ano de início
Entree


On the Complexity of Gap- [2]-vertex-labellings of Subcubic Bipartite Graphs

Texto completo
Autor(es):
Weffort-Santos, C. A. ; Campos, C. N. ; Schouery, R. C. S.
Número total de Autores: 3
Tipo de documento: Artigo Científico
Fonte: ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE; v. 346, p. 10-pg., 2019-08-30.
Resumo

A gap-[k]-vertex-labelling of a simple graph G = (V, E) is a pair (pi, c(pi)) in which pi : V(G) -> {1, 2, ..., k} is an assignment of labels to the vertices of G and c(pi) : V(G) -> {0, 1, ..., k} is a proper vertex-colouring of G such that, for every v is an element of V(G) of degree at least two, c(pi)(v) is induced by the largest difference, i.e. the largest gap, between the labels of its neighbours (cases where d(v) = 1 and d(v) = 0 are treated separately). Introduced in 2013 by A. Dehghan et al. [3] they show that deciding whether a bipartite graph admits a gap-[2]-vertex-labelling is NP-complete and question the computational complexity of deciding whether cubic bipartite graphs admit such a labelling. In this work, we advance the study of the computational complexity for this class, proving that this problem remains NP-complete even when restricted to subcubic bipartite graphs. (AU)

Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
Beneficiário:Flávio Keidi Miyazawa
Modalidade de apoio: Auxílio à Pesquisa - Temático