We consider classes of graphs that enjoy the following properties: they are closed for gated subgraphs, gated amalgamation and Cartesian products, and for any gated subgraph the inverse of the gate function maps vertices to gated subsets. We prove that any graph of such a class contains a peripheral subgraph which is a Cartesian product of two graphs: a gated subgraph of the graph and a prime graph minus a vertex. Therefore, these graphs admit a peripheral elimination procedure which is a generalization of analogous procedure in median graphs. We characterize regular graphs of these classes whenever they enjoy an additional property. As a corollary we derive that regular weakly median graphs are precisely Cartesian products in which each factor is a complete graph or a hyperoctahedron.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1198,
author = {Bostjan Bre\v sar},
title = {Arboreal structure and regular graphs of median-like classes},
journal = {Discussiones Mathematicae Graph Theory},
volume = {23},
year = {2003},
pages = {215-225},
zbl = {1055.05040},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1198}
}
Bostjan Brešar. Arboreal structure and regular graphs of median-like classes. Discussiones Mathematicae Graph Theory, Tome 23 (2003) pp. 215-225. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1198/
[000] [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. | Zbl 0654.05049
[001] [2] H.-J. Bandelt and V. Chepoi, Decomposition and l₁-embedding of weakly median graphs, European J. Combin. 21 (2000) 701-714, doi: 10.1006/eujc.1999.0377. | Zbl 0965.05081
[002] [3] H.-J. Bandelt and H.M. Mulder, Regular pseudo-median graphs, J. Graph Theory 4 (1988) 533-549, doi: 10.1002/jgt.3190120410. | Zbl 0672.05046
[003] [4] H.-J. Bandelt and H.M. Mulder, Pseudo-median graphs: decomposition via amalgamation and Cartesian multiplication, Discrete Math. 94 (1991) 161-180, doi: 10.1016/0012-365X(91)90022-T. | Zbl 0743.05055
[004] [5] H.-J. Bandelt, H.M. Mulder and E. Wilkeit, Quasi-median graphs and algebras, J. Graph Theory 18 (1994) 681-703, doi: 10.1002/jgt.3190180705. | Zbl 0810.05057
[005] [6] A. Brandstaet, V.B. Le and J.P. Spinrad, Graphs classes: A survey (SIAM, Philadelphia, 1999), doi: 10.1137/1.9780898719796.
[006] [7] B. Brešar, On the natural imprint function of a graph, European J. Combin. 23 (2002) 149-161, doi: 10.1006/eujc.2001.0555. | Zbl 1002.05061
[007] [8] M. Chastand, Fiber-complemented graphs, I. Structure and invariant subgraphs, Discrete Math. 226 (2001) 107-141, doi: 10.1016/S0012-365X(00)00183-7. | Zbl 0961.05019
[008] [9] W. Imrich and S. Klavžar, Product graphs: Structure and recognition (Wiley, New York, 2000). | Zbl 0963.05002
[009] [10] S. Klavžar and H.M. Mulder, Median graphs: characterizations, location theory and related structures, J. Combin. Math. Combin. Comp. 30 (1999) 103-127. | Zbl 0931.05072
[010] [11] H.M. Mulder, The structure of median graphs, Discrete Math. 24 (1978) 197-204, doi: 10.1016/0012-365X(78)90199-1. | Zbl 0394.05038
[011] [12] H.M. Mulder, The Interval Function of a Graph, Mathematical Centre Tracts 132 (Mathematisch Centrum, Amsterdam, 1980). | Zbl 0446.05039
[012] [13] H.M. Mulder, The expansion procedure for graphs, in: R. Bodendiek ed., Contemporary Methods in Graph Theory (B.I.-Wissenschaftsverlag, Manhaim/Wien/Zürich, 1990) 459-477.
[013] [14] C. Tardif, Prefibers and the Cartesian product of metric spaces, Discrete Math. 109 (1992) 283-288, doi: 10.1016/0012-365X(92)90298-T. | Zbl 0777.05097
[014] [15] M.L.J. van de Vel, Theory of convex structures (North Holland, Amsterdam, 1993). | Zbl 0785.52001