Convexidade em Grafo Linha de Bipartido
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.
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.