Algorithmic and structural aspects of Covering and Packing problems on graphs

Algorithmic and structural aspects of covering and packing problems on graphs

Development of analytical tools in collaboration with the PDS team and the RepMus ...

Send your message by email

Advanced search

Grant number: | 11/08033-0 |

Support Opportunities: | Scholarships in Brazil - Doctorate |

Effective date (Start): | August 01, 2011 |

Effective date (End): | 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 |

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: | |

TITULO | |

Articles published in other media outlets (0 total):
| |

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.; 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, 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.; 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, 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 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)

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.; 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)

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.

Please report errors in scientific publications list using
this form.