A characterization of planar median graphs

Iztok Peterin

Discussiones Mathematicae Graph Theory (2006)

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

Abstract

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

How to cite

top

Iztok 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. [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. [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. [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. [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. [5] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (John Wiley & Sons, New York, 2000). 
  6. [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. [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. [8] B. Mohar and C. Thomassen, Graphs on Surfaces (Johns Hopkins University Press, Baltimore, MD, 2001). 
  9. [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. [10] H.M. Mulder, The Interval Function of a Graph (Mathematical Centre Tracts 132, Mathematisch Centrum, Amsterdam, 1980). Zbl0446.05039
  11. [11] H.M. Mulder, The expansion procedure for graphs, Contemporary methods in graph theory 459-477 Bibliographisches Inst. Mannheim, 1990. 
  12. [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

NotesEmbed ?

top

You must be logged in to post comments.