Pm-saturated graphs with minimum size

• Autorzy: Dudek A. , Wojda A.P.
• Języki publikacji: EN

Abstrakty

EN

By Pm we denote a path of order m. A graph G is said to be Pm - saturated if G has no subgraph isomorphic to Pm 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; Pm) of Pm-saturated graph and characterize the graphs of Sat(n; Pm) - the set of Pm-saturated graphs of minimum size. They have solved this problem for [formula].

Słowa kluczowe

EN

graph; saturated graph; extremal graph

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2004
• Tom: Vol. 24, no. 1
• Strony: 43--55
• Opis fizyczny: Bibliogr. 9 poz., rys.

Twórcy

autor

Dudek A.

• AGH University of Science and Technology, Faculty of Applied Mathematics, al. Mickiewicza 30, 30-059 Cracow, Poland

autor

Wojda A.P.

• AGH University of Science and Technology, Faculty of Applied Mathematics, al. Mickiewicza 30, 30-059 Cracow, Poland

Bibliografia

• [1] Bollobas B.: Extremal Graph Theory. New York, Academic Press 1978.
• [2] Bondy J. A.: Variations on the hamiltonian theme. Canad. Math. Bull. 15 (1972), 57-62.
• [3] Dudek A., Wojda A. P.: Hamiltonian path saturated graphs with small size (submitted).
• [4] Erdos P.: Remarks on a paper of Pósa. Publ. Math. Inst. Hung. Acad. Sci. A7 (1962), 227-229.
• [5] Erdos P., Gallai T.: On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hung. 10 (1959), 337-356.
• [6] Erdos P., Hajnal A., Moon J.W.: A problem in graph theory. Amer. Math. Monthly 71 (1964), 1107-1110.
• [7] Kaszonyi L., Tuza Zs.: Saturated graphs with minimal number of edges. J. Graph Theory 10 (1986), 203-210.
• [8] Skupień Z.: Hamiltonian circuits and path coverings of vertices in graphs. Colloq. Math. 30 (1974), 295-316.
• [9] Skupień Z.: Hamiltonian shortage, path partitions of vertices, and matchings in a graph. Colloq. Math. 36 (1976), 305-318.