Connected Tropical Subgraphs in Vertex-Colored Graphs
Résumé
A subgraph of a vertex-colored graph is said to be tropical whenever it contains each color of the original graph at least once. In this work we study the problem of finding a minimal connected tropical subgraph. We show that this problem is NP-Hard for trees, interval graphs and split graphs, but polynomial when the number of colors is logarithmic on the number of vertices of the graph.
We give results that provide upper bounds for the order of the minimal connected tropical subgraph under various sufficient conditions, for example, minimal degree or number of edges. We finaly study sufficient and necessary conditions for a random graph to have a tropical subgraph such that each color is present precisely once.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...