- Tytuł:
- Pm-saturated graphs with minimum size
- Autorzy:
-
Dudek, A.
Wojda, A.P. - Powiązania:
- https://bibliotekanauki.pl/articles/2050147.pdf
- Data publikacji:
- 2004
- Wydawca:
- Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
- Tematy:
-
graph
saturated graph
extremal graph - Opis:
- By Pm we denote a path of order m. A graph G is saidto be P$\text{}_{m}$ - saturated if G has no subgraph isomorphic to P$\text{}_{m}$ and adding any new edge to G creates a Pm in G. In 1986 L. Kaszonyi and Zs. Tuza considered the following problem: for given m and n find the minimum size $sat(n; P\text{}_{m}$) of P$\text{}_{m}$-saturated graph and characterize the graphs of $Sat(n; P\text{}_{m}$) - the set of P$\text{}_{m}$-saturated graphs of minimum size. They have solved this problem for $n \geq a_{m}$ where $$ a_{m} = \begin{cases} 3 \cdot 2^{k-1} - 2~~\text{if}~m = 2k,k~~~~~~~\\ 2^{k+1} - 2~~~~~~\text{if}~m = 2k + 1, k \geq 2 \end{cases} $$ We define $$ b_{m} = \begin{cases} 3 \cdot 2^{k-2}~~~~~~~\text{if}~m = 2k,k \geq 3 \\ 3 \cdot 2 ^{k-1} - 1~~\text{if}~m = 2k + 1,k \geq 3 \end{cases} $$ and give $sat(n; P\text{}_{m}$) and $Sat(n; P\text{}_{m})$ for $m \geq 6$ and $b_{m} \leq n < a_{m}$
- Źródło:
-
Opuscula Mathematica; 2004, 24, 1; 43-55
1232-9274
2300-6919 - Pojawia się w:
- Opuscula Mathematica
- Dostawca treści:
- Biblioteka Nauki
Artykuł