Premium
Gallai's Conjecture For Graphs of Girth at Least Four
Author(s) -
Harding Peter,
McGuinness Sean
Publication year - 2014
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21735
Subject(s) - combinatorics , mathematics , conjecture , girth (graph theory) , simple graph , graph , discrete mathematics
In 1966, Gallai conjectured that for any simple, connected graph G having n vertices, there is a path‐decomposition of G having at most ⌈ n 2 ⌉ paths. In this article, we show that for any simple graph G having girth g ≥ 4 , there is a path‐decomposition of G having at mostp ( G ) 2 + ⌊ ( g + 1 2 g ) q ( G ) ⌋paths, where p ( G ) is the number of vertices of odd degree in G and q ( G ) is the number of nonisolated vertices of even degree in G .