Advanced search
Start date
Betweenand
Related content
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Decomposing regular graphs with prescribed girth into paths of given length

Full text
Author(s):
Botler, F. [1] ; Mota, G. O. [1] ; Oshiro, M. T. I. [1] ; Wakabayashi, Y. [1]
Total Authors: 4
Affiliation:
[1] Univ Sao Paulo, Inst Matemat & Estat, Sao Paulo - Brazil
Total Affiliations: 1
Document type: Journal article
Source: EUROPEAN JOURNAL OF COMBINATORICS; v. 66, p. 28-36, DEC 2017.
Web of Science Citations: 0
Abstract

A P-l-decomposition of a graph G is a set of pairwise edge-disjoint paths with l edges that cover the edge set of G. In 1957, Kotzig proved that a 3-regular graph admits a P-3-decomposition if and only if it contains a perfect matching, and also asked what are the necessary and sufficient conditions for an l-regular graph to admit a P-l-decomposition, for odd l. Let g, l and m be positive integers with g >= 3. We prove that, (i) if l is odd and m > 2 left perpendicular (l - 2)/(g - 2) right perpendicular, then every ml-regular graph with girth at least g that contains an m-factor admits a P-l -decomposition; (ii) if m > left perpendicular (l - 2)/(g - 2) right perpendicular , then every 2ml-regular graph with girth at least g admits a P-l-decomposition. Furthermore, we prove that, for graphs with girth at least l - 1, statement (i) holds for every m >= 1; and observe that, statement (ii) also holds for every m >= 1. (C) 2017 Elsevier Ltd. All rights reserved. (AU)

FAPESP's process: 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science
Grantee:Carlos Eduardo Ferreira
Support Opportunities: Research Projects - Thematic Grants
FAPESP's process: 13/11431-2 - Extremal and probabilistic combinatorics
Grantee:Guilherme Oliveira Mota
Support Opportunities: Scholarships in Brazil - Post-Doctoral
FAPESP's process: 11/08033-0 - Decomposition of a graph into paths: structural and algorithmic aspects
Grantee:Fábio Happ Botler
Support Opportunities: Scholarships in Brazil - Doctorate
FAPESP's process: 14/01460-8 - Graph decompositions
Grantee:Fábio Happ Botler
Support Opportunities: Scholarships abroad - Research Internship - Doctorate
FAPESP's process: 13/20733-2 - Extremal and probabilistic combinatorics
Grantee:Guilherme Oliveira Mota
Support Opportunities: Scholarships abroad - Research Internship - Post-doctor