| Grant number: | 14/01460-8 |
| Support Opportunities: | Scholarships abroad - Research Internship - Doctorate |
| Start date: | April 04, 2014 |
| End date: | April 03, 2015 |
| Field of knowledge: | Physical Sciences and Mathematics - Computer Science - Theory of Computation |
| Principal Investigator: | Yoshiko Wakabayashi |
| Grantee: | Fábio Happ Botler |
| Supervisor: | Cun-Quan Zhang |
| Host Institution: | Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil |
| Institution abroad: | West Virginia University (WVU), United States |
| Associated to the scholarship: | 11/08033-0 - Decomposition of a graph into paths: structural and algorithmic aspects, BP.DR |
Abstract A graph G is a pair (V,E), where V is a finite set and E is a set of pairs of distinct elements of V. The elements of V are called vertices, and the elements of E are called edges. Given a graph G=(V,E), a graph decomposition of G is a set of edge-disjoint subgraphs of G that cover E. If D = {H_1,..., H_k} is a decomposition of G such that H_i is a path for every i in {1,...,k}, we say that D is a path decomposition.We say that a path decomposition D of a graph G is minimum if for every path decomposition D' of G we have |D'| >= |D|. The path number of a graph G is the size of a minimum path decomposition of G. We denote it by pn(G). According to Lovász (1968), in 1966, Erdös asked about this parameter, and Gallai stated the following conjecture.Conjecture (Gallai, 1966). If G=(V,E) is a connected graph on n vertices, then pn(G)<=(n+1)/2.This parameter is not known for most of the graph classes. Lovász (1968) found an upper-bound for a similar parameter, the size of a minimum decomposition into paths and cycles.Theorem (Lovász,1968). Every connected graph on n vertices G can be decomposed into at most n/2 paths and cycles.Our plan is to investigate Gallai's conjecture, the path number of special classes of graphs, and related topics. It is known that this conjecture is true for a number of classes of graphs, it has not been settled for classes of graphs such as graphs with maximum degree four, 2k-regular graphs, chordal graphs or planar graphs.We are also interested is the algorithmic aspect of the problem of finding a minimum path decomposition of a graph. We were not able to find results concerning this topic, unlike the case where one seeks vertex-disjoint paths. From this point of view we are interested in approximation algoritms.The study of this problem is justified by its relevance: a classic problem, of great interest in graph theory. Since it is an open conjecture for almost half a century, it would be quite pretentious to establish its veracity or not. Nevertheless, we believe that this study will give the student the oportunity to learn many proof techniques and understand where the difficulty of the problem lies. (AU) | |
| News published in Agência FAPESP Newsletter about the scholarship: | |
| More itemsLess items | |
| TITULO | |
| Articles published in other media outlets ( ): | |
| More itemsLess items | |
| VEICULO: TITULO (DATA) | |
| VEICULO: TITULO (DATA) | |