Open AccessConvexidade em Grafo Linha de Bipartido
Author(s) -
Vitor S Ponciano,
R. S. Oliveira
Publication year - 2019
Language(s) - English
Resource type - Conference proceedings
DOI - 10.5753/etc.2019.6403
Subject(s) - combinatorics , cardinality (data modeling) , mathematics , geodetic datum , integer (computer science) , enhanced data rates for gsm evolution , geodesic , set (abstract data type) , discrete mathematics , geometry , computer science , telecommunications , cartography , data mining , programming language , geography
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.