TY  - JOUR
ID  - Dudek2004
LB  - Dudek2004
AU  - Dudek, Aneta
AU  - Wojda, A. Paweł
TI  - P<sub>m</sub>-saturated graphs with minimum size
ST  - P<sub>m</sub>-saturated graphs with minimum size
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2004
VL  - 24
IS  - 1
SP  - 43
EP  - 55
DO  - http://dx.doi.org/10.7494/OpMath.2004.24.1.43
UR  - http://dx.doi.org/10.7494/OpMath.2004.24.1.43
AB  - By \(P_m\) we denote a path of order \(m\). A graph \(G\) is said to be \(P_m\)-saturated if \(G\) has no subgraph isomorphic to \(P_m\) and adding any new edge to \(G\) creates a \(P_m\) in \(G\). In 1986 L. Kászonyi and Zs. Tuza considered the following problem: for given \(m\) and \(n\) find the minimum size \(sat(n;P_m)\) of \(P_m\)-saturated graph and characterize the graphs of \(Sat(n;P_m)\) - the set of \(P_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 &\quad\text{ if }\quad m=2k,\, k\gt 2\\ 2^{k+1}-2 &\quad\text{ if }\quad m=2k+1,\, k\geq 2\end{cases}\). We define \(b_m=\begin{cases}3\cdot 2^{k-2} &\quad\text{ if }\quad m=2k,\, k\geq 3\\ 3\cdot 2^{k-1}-1 &\quad\text{ if }\quad m=2k+1,\, k\geq 3\end{cases}\) and give \(sat(n;P_m)\) and \(Sat(n;P_m)\) for \(m\geq 6\) and \(b_m\leq n\leq a_m\).
KW  - graph
KW  - saturated graph
KW  - extremal graph
SN  - 1232-9274
ER  -