On dually compact closed classes of graphs and BFS-constructible graphs

Norbert Polat

Discussiones Mathematicae Graph Theory (2003)

  • Volume: 23, Issue: 2, page 365-381
  • ISSN: 2083-5892

Abstract

top
A class C of graphs is said to be dually compact closed if, for every infinite G ∈ C, each finite subgraph of G is contained in a finite induced subgraph of G which belongs to C. The class of trees and more generally the one of chordal graphs are dually compact closed. One of the main part of this paper is to settle a question of Hahn, Sands, Sauer and Woodrow by showing that the class of bridged graphs is dually compact closed. To prove this result we use the concept of constructible graph. A (finite or infinite) graph G is constructible if there exists a well-ordering ≤ (called constructing ordering) of its vertices such that, for every vertex x which is not the smallest element, there is a vertex y < x which is adjacent to x and to every neighbor z of x with z < x. Finite graphs are constructible if and only if they are dismantlable. The case is different, however, with infinite graphs. A graph G for which every breadth-first search of G produces a particular constructing ordering of its vertices is called a BFS-constructible graph. We show that the class of BFS-constructible graphs is a variety (i.e., it is closed under weak retracts and strong products), that it is a subclass of the class of weakly modular graphs, and that it contains the class of bridged graphs and that of Helly graphs (bridged graphs being very special instances of BFS-constructible graphs). Finally we show that the class of interval-finite pseudo-median graphs (and thus the one of median graphs) and the class of Helly graphs are dually compact closed, and that moreover every finite subgraph of an interval-finite pseudo-median graph (resp. a Helly graph) G is contained in a finite isometric pseudo-median (resp. Helly) subgraph of G. We also give two sufficient conditions so that a bridged graph has a similar property.

How to cite

top

Norbert Polat. "On dually compact closed classes of graphs and BFS-constructible graphs." Discussiones Mathematicae Graph Theory 23.2 (2003): 365-381. <http://eudml.org/doc/270651>.

@article{NorbertPolat2003,
abstract = {A class C of graphs is said to be dually compact closed if, for every infinite G ∈ C, each finite subgraph of G is contained in a finite induced subgraph of G which belongs to C. The class of trees and more generally the one of chordal graphs are dually compact closed. One of the main part of this paper is to settle a question of Hahn, Sands, Sauer and Woodrow by showing that the class of bridged graphs is dually compact closed. To prove this result we use the concept of constructible graph. A (finite or infinite) graph G is constructible if there exists a well-ordering ≤ (called constructing ordering) of its vertices such that, for every vertex x which is not the smallest element, there is a vertex y < x which is adjacent to x and to every neighbor z of x with z < x. Finite graphs are constructible if and only if they are dismantlable. The case is different, however, with infinite graphs. A graph G for which every breadth-first search of G produces a particular constructing ordering of its vertices is called a BFS-constructible graph. We show that the class of BFS-constructible graphs is a variety (i.e., it is closed under weak retracts and strong products), that it is a subclass of the class of weakly modular graphs, and that it contains the class of bridged graphs and that of Helly graphs (bridged graphs being very special instances of BFS-constructible graphs). Finally we show that the class of interval-finite pseudo-median graphs (and thus the one of median graphs) and the class of Helly graphs are dually compact closed, and that moreover every finite subgraph of an interval-finite pseudo-median graph (resp. a Helly graph) G is contained in a finite isometric pseudo-median (resp. Helly) subgraph of G. We also give two sufficient conditions so that a bridged graph has a similar property.},
author = {Norbert Polat},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {infinite graph; dismantlable graph; constructible graph; BFS-cons-tructible graph; variety; weak-retract; strong product; bridged graph; Helly graph; weakly-modular graph; dually compact closed class; dually compact closed; chordal graphs; bridged graphs; infinite graphs; BFS-constructible graph; modular graphs; Helly graphs; pseudo-median graphs},
language = {eng},
number = {2},
pages = {365-381},
title = {On dually compact closed classes of graphs and BFS-constructible graphs},
url = {http://eudml.org/doc/270651},
volume = {23},
year = {2003},
}

TY - JOUR
AU - Norbert Polat
TI - On dually compact closed classes of graphs and BFS-constructible graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2003
VL - 23
IS - 2
SP - 365
EP - 381
AB - A class C of graphs is said to be dually compact closed if, for every infinite G ∈ C, each finite subgraph of G is contained in a finite induced subgraph of G which belongs to C. The class of trees and more generally the one of chordal graphs are dually compact closed. One of the main part of this paper is to settle a question of Hahn, Sands, Sauer and Woodrow by showing that the class of bridged graphs is dually compact closed. To prove this result we use the concept of constructible graph. A (finite or infinite) graph G is constructible if there exists a well-ordering ≤ (called constructing ordering) of its vertices such that, for every vertex x which is not the smallest element, there is a vertex y < x which is adjacent to x and to every neighbor z of x with z < x. Finite graphs are constructible if and only if they are dismantlable. The case is different, however, with infinite graphs. A graph G for which every breadth-first search of G produces a particular constructing ordering of its vertices is called a BFS-constructible graph. We show that the class of BFS-constructible graphs is a variety (i.e., it is closed under weak retracts and strong products), that it is a subclass of the class of weakly modular graphs, and that it contains the class of bridged graphs and that of Helly graphs (bridged graphs being very special instances of BFS-constructible graphs). Finally we show that the class of interval-finite pseudo-median graphs (and thus the one of median graphs) and the class of Helly graphs are dually compact closed, and that moreover every finite subgraph of an interval-finite pseudo-median graph (resp. a Helly graph) G is contained in a finite isometric pseudo-median (resp. Helly) subgraph of G. We also give two sufficient conditions so that a bridged graph has a similar property.
LA - eng
KW - infinite graph; dismantlable graph; constructible graph; BFS-cons-tructible graph; variety; weak-retract; strong product; bridged graph; Helly graph; weakly-modular graph; dually compact closed class; dually compact closed; chordal graphs; bridged graphs; infinite graphs; BFS-constructible graph; modular graphs; Helly graphs; pseudo-median graphs
UR - http://eudml.org/doc/270651
ER -

References

top
  1. [1] R.P. Anstee and M. Farber, On bridged graphs and cop-win graphs, J. Combin. Theory (B) 44 (1988) 22-28, doi: 10.1016/0095-8956(88)90093-7. Zbl0654.05049
  2. [2] M. Chastand, F. Laviolette and N. Polat, On constructible graphs, infinite bridged graphs and weakly cop-win graphs, Discrete Math. 224 (2000) 61-78, doi: 10.1016/S0012-365X(00)00127-8. Zbl0961.05066
  3. [3] G. Hahn, F. Laviolette, N. Sauer and R.E. Woodrow, On cop-win graphs, preprint, 1989. Zbl1009.05085
  4. [4] G. Hahn, N. Sands, N. Sauer and R.E. Woodrow, Problem Session, in: Colloque Franco-Canadien de Combinatoire (Université de Montréal, 1981). 
  5. [5] G. Hahn, N. Sauer and R.E. Woodrow, personal communication. 
  6. [6] J. Isbell, Six theorems about injective metric spaces, Comment. Math. Helv. 39 (1964), 65-76, doi: 10.1007/BF02566944. Zbl0151.30205
  7. [7] W. Imrich and S. Klavžar, Product graphs (Wiley, 2000). 
  8. [8] E. Jawhari, D. Misane and M. Pouzet, Retracts: Graphs and ordered sets from the metric point of view, Contemp. Math. 57 (1986) 175-226, doi: 10.1090/conm/057/856237. Zbl0597.54028
  9. [9] R. Nowakowski and I. Rival, The smallest graph variety containing all paths, Discrete Math. 43 (1983) 223-234, doi: 10.1016/0012-365X(83)90159-0. Zbl0511.05059
  10. [10] E. Pesch, Minimal extensions of graphs to absolute retracts, J. Graph Theory 11 (1987) 585-598, doi: 10.1002/jgt.3190110416. Zbl0649.05050
  11. [11] N. Polat, Invariant subgraph properties in pseudo-modular graphs, Discrete Math. 207 (2000) 199-217, doi: 10.1016/S0012-365X(99)00045-X. Zbl0945.05039
  12. [12] N. Polat, On infinite bridged graphs and strongly dismantlable graphs, Discrete Math. 211 (2000) 153-166, doi: 10.1016/S0012-365X(99)00142-9. Zbl0959.05100
  13. [13] N. Polat, On isometric subgraphs of infinite bridged graphs and geodesic convexity, Discrete Math. 244 (2002) 399-416, doi: 10.1016/S0012-365X(01)00097-8. Zbl0995.05045
  14. [14] M. Pouzet, Une approche métrique de la rétraction dans les ensembles ordonnés et les graphes, Compte-rendu des Journées infinitistes de Lyon (octobre 1984), Pub. Dépt. Math. (Lyon, 1985). 
  15. [15] M. Pouzet, Retracts: recent and old results on graphs, ordered sets and metric spaces, Circulating manuscript, 29 pages, Nov. 1983. 
  16. [16] A. Quilliot, Homomorphismes, points fixes, rétractions et jeux de poursuite dans les graphes, les ensembles ordonnés et les espaces métriques, Thrèse de doctorat d'Etat (Univ. Paris VI, 1983). 
  17. [17] V. Soltan and V. Chepoi, Conditions for invariance of set diameters under d-convexification, Cybernetics 19 (1983) 750-756, doi: 10.1007/BF01068561. Zbl0564.05037
  18. [18] C. Tardif, On compact median graphs, J. Graph Theory 23 (1996) 325-336, doi: 10.1002/(SICI)1097-0118(199612)23:4<325::AID-JGT1>3.0.CO;2-T Zbl0863.05068

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.