On Computing the Path Number of a Graph

Autor(es)

Botler, F. ; Cano, R. ; Sambinelli, M.

• Tipo de documento: Artigo Científico
• Fonte: ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE; v. 346, p. 13-pg., 2019-08-30.

Resumo

Gallai (1966) conjectured that the edge set of every graph G on n vertices can be covered by at most [n/2] edge-disjoint paths. Such a covering by edge-disjoint paths is called a path decomposition, and the size of a path decomposition with a minimum number of elements is called the path number of G. Peroche (1984) proved that the problem of computing the path number is NP-Complete; and Constantinou and Ellinas (2018) proved that it is polynomial for a family of complete bipartite graphs. In this paper we present an integer Linear Programming model for computing the path number of a graph. This allowed us to verify Gallai's Conjecture for a large collection of graphs. As a result, following a work of Heinrich, Natale and Streicher on cycle decompositions (2017), we verify Gallai's Conjecture for graphs with at most 11 vertices; for bipartite graphs with at most 16 vertices; and for regular graphs with at most 14 vertices. (AU)

• Processo FAPESP: 17/23623-4 - Problemas de partição em grafos e dígrafos
• Beneficiário: Maycon Sambinelli
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado