A characterization of planar median graphs
Iztok Peterin
Discussiones Mathematicae Graph Theory, Tome 26 (2006), p. 41-48 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

Median graphs have many interesting properties. One of them is-in connection with triangle free graphs-the recognition complexity. In general the complexity is not very fast, but if we restrict to the planar case the recognition complexity becomes linear. Despite this fact, there is no characterization of planar median graphs in the literature. Here an additional condition is introduced for the convex expansion procedure that characterizes planar median graphs.

Publié le : 2006-01-01
EUDML-ID : urn:eudml:doc:270692 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1299,
     author = {Iztok Peterin},
     title = {A characterization of planar median graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {26},
     year = {2006},
     pages = {41-48},
     zbl = {1105.05017},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1299}
}

Iztok Peterin. A characterization of planar median graphs. Discussiones Mathematicae Graph Theory, Tome 26 (2006) pp. 41-48. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1299/

[000] [1] M. Behzad and E.S. Mahmoodian, On topological invariants of the product of graphs, Canad. Math. Bull. 12 (1969) 157-166, doi: 10.4153/CMB-1969-015-9. | Zbl 0177.52402

[001] [2] B. Bresar, W. Imrich, S. Klavžar, H.M. Mulder and R. Skrekovski, Tiled partial cubes, J. Graph Theory 40 (2002) 91-103, doi: 10.1002/jgt.10031.

[002] [3] V.D. Chepoi, Isometric subgraphs of Hamming graphs and d-convexity, (Russian) Kibernetika (Kiev) (1988) 6-9; translation in Cybernetics 24 (1988) 6-11.

[003] [4] D. Djoković, Distance preserving subgraphs of hypercubes, J. Combin. Theory (B) 14 (1973) 263-267, doi: 10.1016/0095-8956(73)90010-5. | Zbl 0245.05113

[004] [5] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (John Wiley & Sons, New York, 2000).

[005] [6] W. Imrich, S. Klavžar and H.M. Mulder, Median graphs and triangle-free graphs, SIAM J. Discrete Math. 12 (1999) 111-118, doi: 10.1137/S0895480197323494. | Zbl 0916.68106

[006] [7] S. Klavžar and H.M. Mulder, Median graphs: characterization, location theory and related structures, J. Combin. Math. Combin. Comp. 30 (1999) 103-127. | Zbl 0931.05072

[007] [8] B. Mohar and C. Thomassen, Graphs on Surfaces (Johns Hopkins University Press, Baltimore, MD, 2001).

[008] [9] 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

[009] [10] H.M. Mulder, The Interval Function of a Graph (Mathematical Centre Tracts 132, Mathematisch Centrum, Amsterdam, 1980). | Zbl 0446.05039

[010] [11] H.M. Mulder, The expansion procedure for graphs, Contemporary methods in graph theory 459-477 Bibliographisches Inst. Mannheim, 1990.

[011] [12] P.M. Winkler, Isometric embedding in products of complete graphs, Discrete Appl. Math. 7 (1984) 221-225, doi: 10.1016/0166-218X(84)90069-6. | Zbl 0529.05055