Scholarship 11/08033-0 - Algoritmos de aproximação, Grafos - BV FAPESP
Advanced search
Start date
Betweenand

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.

News published in Agência FAPESP Newsletter about the scholarship:
More itemsLess items
Articles published in other media outlets ( ):
More itemsLess items
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

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, . (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, . (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, . (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, . (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, . (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, . (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., . (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.