Geodesic
On Gallai's path decomposition conjecture
Filomat, Tome 37 (2023) no. 17, p. 5829

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

DOI

Gallai conjectured that every connected graph on n vertices can be decomposed into at most n+1 2 paths. Let G be a connected graph on n vertices. The E-subgraph of G, denoted by F, is the subgraph induced by the vertices of even degree in G. The maximum degree of G is denoted by △(G). In 2020, Botler and Sambinelli verified Gallai's Conjecture for graphs whose E-subgraphs F satisfy △(F) ≤ 3. If the E-subgraph of G has at most one vertex with degree greater than 3, Fan, Hou and Zhou verified Gallai's Conjecture for G. In this paper, it is proved that if there are two adjacent vertices x, y ∈ V(F) such that d F (v) ≤ 3 for every vertex v ∈ V(F)\{x, y}, then G has a path-decomposition D 1 such that |D 1 | ≤ n+1 2 and D 1 (x) ≥ 2, and a path-decomposition D 2 such that |D 2 | ≤ n+1 2 and D 2 (y) ≥ 2.
DOI : 10.2298/FIL2317829X
Classification : 05C38, 05C51
Keywords: Decomposition, Path, Gallai’s conjecture 
Mengmeng Xie. On Gallai's path decomposition conjecture. Filomat, Tome 37 (2023) no. 17, p. 5829 . doi: 10.2298/FIL2317829X
@article{10_2298_FIL2317829X,
     author = {Mengmeng Xie},
     title = {On {Gallai's} path decomposition conjecture},
     journal = {Filomat},
     pages = {5829 },
     year = {2023},
     volume = {37},
     number = {17},
     doi = {10.2298/FIL2317829X},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.2298/FIL2317829X/}
}
TY  - JOUR
AU  - Mengmeng Xie
TI  - On Gallai's path decomposition conjecture
JO  - Filomat
PY  - 2023
SP  - 5829 
VL  - 37
IS  - 17
UR  - http://geodesic.mathdoc.fr/articles/10.2298/FIL2317829X/
DO  - 10.2298/FIL2317829X
LA  - en
ID  - 10_2298_FIL2317829X
ER  - 
%0 Journal Article
%A Mengmeng Xie
%T On Gallai's path decomposition conjecture
%J Filomat
%D 2023
%P 5829 
%V 37
%N 17
%U http://geodesic.mathdoc.fr/articles/10.2298/FIL2317829X/
%R 10.2298/FIL2317829X
%G en
%F 10_2298_FIL2317829X

Cité par Sources :