# A characterization of planar median graphs

Discussiones Mathematicae Graph Theory (2006)

- Volume: 26, Issue: 1, page 41-48
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topIztok Peterin. "A characterization of planar median graphs." Discussiones Mathematicae Graph Theory 26.1 (2006): 41-48. <http://eudml.org/doc/270692>.

@article{IztokPeterin2006,

abstract = {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.},

author = {Iztok Peterin},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {median graphs; planar graphs; expansion; planar graph; convex subgraph},

language = {eng},

number = {1},

pages = {41-48},

title = {A characterization of planar median graphs},

url = {http://eudml.org/doc/270692},

volume = {26},

year = {2006},

}

TY - JOUR

AU - Iztok Peterin

TI - A characterization of planar median graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2006

VL - 26

IS - 1

SP - 41

EP - 48

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

LA - eng

KW - median graphs; planar graphs; expansion; planar graph; convex subgraph

UR - http://eudml.org/doc/270692

ER -

## References

top- [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. Zbl0177.52402
- [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.
- [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.
- [4] D. Djoković, Distance preserving subgraphs of hypercubes, J. Combin. Theory (B) 14 (1973) 263-267, doi: 10.1016/0095-8956(73)90010-5. Zbl0245.05113
- [5] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (John Wiley & Sons, New York, 2000).
- [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. Zbl0916.68106
- [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. Zbl0931.05072
- [8] B. Mohar and C. Thomassen, Graphs on Surfaces (Johns Hopkins University Press, Baltimore, MD, 2001).
- [9] H.M. Mulder, The structure of median graphs, Discrete Math. 24 (1978) 197-204, doi: 10.1016/0012-365X(78)90199-1. Zbl0394.05038
- [10] H.M. Mulder, The Interval Function of a Graph (Mathematical Centre Tracts 132, Mathematisch Centrum, Amsterdam, 1980). Zbl0446.05039
- [11] H.M. Mulder, The expansion procedure for graphs, Contemporary methods in graph theory 459-477 Bibliographisches Inst. Mannheim, 1990.
- [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. Zbl0529.05055

## Citations in EuDML Documents

top## NotesEmbed ?

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