IJPAM: Volume 69, No. 4 (2011)

PATH SATURATED GRAPHS

Yehuda Ashkenazi
Ariel Academic Center
Department of Computer Science and Mathematics
Ariel, ISRAEL
e-mail: [email protected]


Abstract. This paper deals with characterization for a graph to be saturated according to a path of order $m$. In this paper we have a full characterization for a connected graph to be $P_m$-saturated for $m \leq 6$ and we have some general results, closing with a conjecture for the related Turán type problem.

Received: November 25, 2010

AMS Subject Classification: 05Cxx

Key Words and Phrases: graph theory, saturated graphs, paths, longest paths, diameter, Turán type problems

Download paper from here.



Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2011
Volume: 69
Issue: 4