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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.