Cobrindo as arestas de cactos com caminhos

• Carlos V. G. C. Lima UFCA
• Ana Karolinna Maia UFC
• Samuel S. Morais UFC

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

Resumo

Um problema de cobertura de arestas em grafos procura por uma família de subconjuntos de arestas do grafo com uma determinada propriedade tal que sua união seja exatamente o conjunto de arestas do grafo. [Harary and Schwenk 1972] definiu π∗(G) como o tamanho de uma menor cobertura de arestas de G de forma que todos os subconjuntos na cobertura são caminhos simples em G. Neste trabalho, determinamos π∗(G) para um cacto G.

Referências

Arumugam, S. and Suseela, J. S. (1998). Acyclic graphoidal covers and path partitions in a graph. Discrete Mathematics, 190(1):67–77.

Fan, G. (2002). Subgraph coverings and edge switchings. Journal of Combinatorial Theory, Series B, 84(1):54–83.

Harary, F. and Schwenk, A. J. (1972). Evolution of the path number of a graph: Covering and packing in graphs. In READ, R. C., editor, Graph Theory and Computing, pages 39–45. Academic Press.

Jin, Z. and Li, X. (2006). On the k-path cover problem for cacti. Theoretical Computer Science, 355(3):354–363.

Lovász, L. (1968). On covering of graphs. In Theory of Graphs (Proc. Colloq., Tihany, 1966), pages 231–236. Akadémiai Kiadó, Budapest.

Moran, S. and Wolfstahl, Y. (1991). Optimal covering of cacti by vertex-disjoint paths. Theoretical Computer Science, 84(2):179–197.

Péroche, B. (1984). NP-completeness of some problems of partitioning and covering in graphs. Discrete Applied Mathematics, 8(2):195–208.