Scholarship 14/01460-8 - Teoria dos grafos - BV FAPESP
Advanced search
Start date
Betweenand

Graph decompositions

Grant number: 14/01460-8
Support Opportunities:Scholarships abroad - Research Internship - Doctorate
Start date until: April 04, 2014
End date until: 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
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)

Please report errors in scientific publications list using this form.