| Full text | |
| Author(s): |
Botler, F.
;
Cano, R.
;
Sambinelli, M.
Total Authors: 3
|
| Document type: | Journal article |
| Source: | ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE; v. 346, p. 13-pg., 2019-08-30. |
| Abstract | |
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) | |
| FAPESP's process: | 17/23623-4 - Partition problems in graphs and digraphs |
| Grantee: | Maycon Sambinelli |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |