On the path partition of graphs

Szczegóły
Opis

Tytuł:: On the path partition of graphs
Autorzy:: Kouider, Mekkia
Zamime, Mohamed
Powiązania:: https://bibliotekanauki.pl/articles/29519476.pdf
Data publikacji:: 2023
Wydawca:: Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:: path
partition
graphs
Źródło:: Opuscula Mathematica; 2023, 43, 6; 829-839
1232-9274
2300-6919
Język:: angielski
Prawa:: CC BY: Creative Commons Uznanie autorstwa 4.0
Dostawca treści:: Biblioteka Nauki
: Artykuł

Przejdź do źródła

Let $ G $ be a graph of order $ n $. The maximum and minimum degree of $ G $ are denoted by $ Δ $ and $ δ $, respectively. The path partition number $ μ(G) $ of a graph $ G $ is the minimum number of paths needed to partition the vertices of $ G $. Magnant, Wang and Yuan conjectured that $ μ(G) ≤ max { \frac{n}{δ+1} , \frac{(Δ-δ)n}{(Δ+δ)} } $. In this work, we give a positive answer to this conjecture, for $ Δ ≥ 2δ $.

Informacja

Powiązane pozycje