Advanced search
Start date
Betweenand

Graph decompositions

Grant number: 14/01460-8
Support type:Scholarships abroad - Research Internship - Doctorate
Effective date (Start): April 04, 2014
Effective date (End): 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 abroad: Cun-Quan Zhang
Home Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
Local de pesquisa : 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)

Scientific publications (6)
(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. Web of Science Citations: 1.
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. Web of Science Citations: 0.
BOTLER, F.; TALON, A. Decomposing 8-regular graphs into paths of length 4. DISCRETE MATHEMATICS, v. 340, n. 9, p. 2275-2285, SEP 2017. Web of Science Citations: 1.
BOTLER, FABIO; JIMENEZ, ANDREA. On path decompositions of 2k-regular graphs. DISCRETE MATHEMATICS, v. 340, n. 6, p. 1405-1411, JUN 2017. Web of Science Citations: 5.
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. Web of Science Citations: 7.
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. Web of Science Citations: 4.

Please report errors in scientific publications list by writing to: cdi@fapesp.br.