Decomposition of a graph into paths: structural and algorithmic aspects

• Grant number: 11/08033-0
• Support Opportunities: Scholarships in Brazil - Doctorate
• Start date: August 01, 2011
• End date: February 29, 2016
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Yoshiko Wakabayashi
• Grantee: Fábio Happ Botler
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Associated scholarship(s): 14/01460-8 - Graph decompositions, BE.EP.DR

Abstract

The focus of this project is a classical problem in graph theory on the partition of the edge set of a graph into a minimum number of paths. This problem has its roots in a conjecture of Gallai (1966) on an upper bound for this number that depends only on the number of vertices of the graph. This conjecture states that the edge set of an n-vertex connected graph can be decomposed into at most (n+1)/2 paths. Not so many results have been published on this conjecture. It is known that it has been established for graphs in which all vertices have odd degree, and also for graphs in which the vertices of even degree induce a subgraph with a special structure. We are interested in investigating this conjecture for other classes of graphs and and also explore algorithmic aspects of this problem. Algorithmic results on this problem have not been found in the literature.

Scientific publications

(7)

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

BOTLER, F.; MOTA, G. O.; OSHIRO, M. T. I.; WAKABAYASHI, Y.. Decomposing highly connected graphs into paths of length five. DISCRETE APPLIED MATHEMATICS, v. 245, n. SI, p. 128-138, AUG 20 2018. (13/20733-2, 13/03447-6, 13/11431-2, 11/08033-0, 14/01460-8)

BOTLER, F.; MOTA, G. O.; OSHIRO, M. T. I.; WAKABAYASHI, Y.. Decomposing regular graphs with prescribed girth into paths of given length. EUROPEAN JOURNAL OF COMBINATORICS, v. 66, p. 28-36, DEC 2017. (13/03447-6, 13/11431-2, 11/08033-0, 14/01460-8, 13/20733-2)

BOTLER, FABIO; JIMENEZ, ANDREA. On path decompositions of 2k-regular graphs. DISCRETE MATHEMATICS, v. 340, n. 6, p. 1405-1411, JUN 2017. (13/03447-6, 11/08033-0, 14/01460-8)

BOTLER, F.; TALON, A.. Decomposing 8-regular graphs into paths of length 4. DISCRETE MATHEMATICS, v. 340, n. 9, p. 2275-2285, SEP 2017. (13/03447-6, 11/08033-0, 14/01460-8)

BOTLER, F.; MOTA, G. O.; WAKABAYASHI, Y.. Decompositions of triangle-free 5-regular graphs into paths of length five. DISCRETE MATHEMATICS, v. 338, n. 11, p. 1845-1855, NOV 6 2015. (11/08033-0, 13/11431-2, 14/01460-8, 13/20733-2)

BOTLER, F.; MOTA, G. O.; OSHIRO, M. T. I.; WAKABAYASHI, Y.. Decomposing highly edge-connected graphs into paths of any given length. JOURNAL OF COMBINATORIAL THEORY SERIES B, v. 122, p. 508-542, JAN 2017. (13/20733-2, 13/03447-6, 13/11431-2, 11/08033-0, 14/01460-8)

BOTLER, F.; MOTA, G. O.; OSHIRO, M. T. I.; WAKABAYASHI, Y.. Decomposing highly connected graphs into paths of length five. DISCRETE APPLIED MATHEMATICS, v. 245, p. 11-pg., 2018-08-20. (11/08033-0, 13/11431-2, 13/20733-2, 13/03447-6, 14/01460-8)

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

BOTLER, Fábio Happ. Decomposition of graphs into paths. 2016. Doctoral Thesis - Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) São Paulo.