DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 24(2) (2004) 197-211
DOI: 10.7151/dmgt.1225

Pm-SATURATED BIPARTITE GRAPHS WITH MINIMUM SIZE

Aneta Dudek and A. Paweł Wojda

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;Pm) of Pm-saturated graph of order n. They gave the number sat(n;Pm) for n big enough. We deal with similar problem for bipartite graphs.

Keywords: graph, saturated graph, extremal graph, bipartite graph.

2000 Mathematics Subject Classification: 05C35.

References

[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.

Received 20 June 2002
Revised 9 December 2002