Convexidade em Grafo Linha de Bipartido

• Vitor Ponciano UFRJ
• Romulo Oliveira UFRJ

DOI: https://doi.org/10.5753/etc.2019.6403

Resumo

For a nontrivial connected and simple graphs G= (V(G), E(G)), a set S E(G) is called edge geodetic set of G if every edge of G it’s in S or is contained in a geodesic joining some pair of edges in S. The edge geodetic number eds(G) of G is the minimum order of its edge geodetic sets. We prove that it is NP-complete to decide for a given bipartiti graphs G and a given integer k whether G has a edge geodetic set of cardinality at most k. A set M V(G) is called P3 set of G if all vertices of G have two neighbors in M. The P3 number of G is the minimum order of its P3 sets. We prove that it is NP-complete to decide for a given graphs G(diamond,odd-hole) free and a given integer k whether G has a P3 set of cardinality at most k.

Palavras-chave: Grafo bipartido, convexidade

Referências

Bonomo, F., Dur´an, G., and Marenco, J. (2009). Exploring the complexity boundary between coloring and list-coloring. Annals ofOperations Research, 169(1):3.

Erdos, P., Rubin, L., and Taylor, H. (1979). Chosability in graphs. Proceedings West Coast Conference on Combinatorics, 26:125–157.

Fellows, M., Lokshtanov, D., Rosamond, F., Saurabh, S., and Misra, N. (2008). Graph layout problems parameterized by vertex cover. Algorithms and Computation, Proce- edings ofISAAC 2008.

Fellows, M. R., dos Santos Souza, U., Protti, F., and da Silva, M. D. (2015). Tractability and hardness of flood-filling games on trees. Theoretical Computer Science, 576:102– 116.