Opuscula Math. 24, no. 1 (2004), 43-55

Opuscula Mathematica

# Pm-saturated graphs with minimum size

Aneta Dudek
A. Paweł Wojda

Abstract. 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$$.

Keywords: graph, saturated graph, extremal graph.

Mathematics Subject Classification: 05C35.

Full text (pdf)

• Aneta Dudek
• AGH University of Science and Technology, Faculty of Applied Mathematics, al. Mickiewicza 30, 30-059 Cracow, Poland
• A. Paweł Wojda
• AGH University of Science and Technology, Faculty of Applied Mathematics, al. Mickiewicza 30, 30-059 Cracow, Poland
• Received: 2003-12-02.

Cite this article as:
Aneta Dudek, A. Paweł Wojda, Pm-saturated graphs with minimum size, Opuscula Math. 24, no. 1 (2004), 43-55

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

In accordance with EU legislation we advise you this website uses cookies to allow us to see how the site is used. All data is anonymized.
All recent versions of popular browsers give users a level of control over cookies. Users can set their browsers to accept or reject all, or certain, cookies.