Pₘ-saturated bipartite graphs with minimum size

Aneta Dudek; A. Paweł Wojda

Discussiones Mathematicae Graph Theory (2004)

  • Volume: 24, Issue: 2, page 197-211
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Aneta Dudek, and A. Paweł Wojda. "Pₘ-saturated bipartite graphs with minimum size." Discussiones Mathematicae Graph Theory 24.2 (2004): 197-211. <http://eudml.org/doc/270410>.

@article{AnetaDudek2004,
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.},
author = {Aneta Dudek, A. Paweł Wojda},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph; saturated graph; extremal graph; bipartite graph},
language = {eng},
number = {2},
pages = {197-211},
title = {Pₘ-saturated bipartite graphs with minimum size},
url = {http://eudml.org/doc/270410},
volume = {24},
year = {2004},
}

TY - JOUR
AU - Aneta Dudek
AU - A. Paweł Wojda
TI - Pₘ-saturated bipartite graphs with minimum size
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 2
SP - 197
EP - 211
AB - 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.
LA - eng
KW - graph; saturated graph; extremal graph; bipartite graph
UR - http://eudml.org/doc/270410
ER -

References

top
  1. [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. [2] B. Bollobás, Extremal Graph Theory (Academic Press, New York, 1978). Zbl0419.05031
  3. [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. Zbl0126.39401
  4. [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. Zbl0576.05031
  5. [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. Zbl0593.05041
  6. [6] P. Turán, Eine Extremalaufgabe aus der Graphentheorie, Math. Fiz. Lapok 48 (1941) 436-452. Zbl0026.26903

NotesEmbed ?

top

You must be logged in to post comments.