ArticleOriginal scientific text

Title

Pₘ-saturated bipartite graphs with minimum size

Authors 1, 1

Affiliations

  1. Faculty of Applied Mathematics, AGH University of Science and Technology, Kraków, Poland

Abstract

A graph G is said to be H-saturated if G is H-free i.e., (G has no subgraph isomorphic to H) and adding any new edge to G creates a copy of H 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ₘ) of Pₘ-saturated graph of order n. They gave the number sat(n;Pₘ) for n big enough. We deal with similar problem for bipartite graphs.

Keywords

graph, saturated graph, extremal graph, bipartite graph

Bibliography

  1. N. Alon, An extremal problem for sets with application to graph theory, J. Combin. Theory Ser. A 40 (1985) 82-89, doi: 10.1016/0097-3165(85)90048-2.
  2. B. Bollobás, Extremal Graph Theory (Academic Press, New York, 1978).
  3. P. Erdös, A. Hajnal, and J.W. Moon, A problem in graph theory, Amer. Math. Monthly 71 (1964) 1107-111, doi: 10.2307/2311408.
  4. A. Gyárfás, C.C. Rousseau, and R.H. Schelp, An extremal problem for path in bipartite graphs, J. Graph Theory 8 (1984) 83-95, doi: 10.1002/jgt.3190080109.
  5. L. Kászonyi and Zs. Tuza, Saturated graphs with minimal number of edges, J. Graph Theory 10 (1986) 203-210, doi: 10.1002/jgt.3190100209.
  6. P. Turán, Eine Extremalaufgabe aus der Graphentheorie, Math. Fiz. Lapok 48 (1941) 436-452.
Pages:
197-211
Main language of publication
English
Published
2004
Exact and natural sciences