PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2006 | 26 | 1 | 41-48
Tytuł artykułu

A characterization of planar median graphs

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
Wydawca
Rocznik
Tom
26
Numer
1
Strony
41-48
Opis fizyczny
Daty
wydano
2006
otrzymano
2004-10-07
poprawiono
2005-04-21
Twórcy
  • Faculty of Electrical Engineering and Computer Science, University of Maribor, Smetanova ulica 17, 2000 Maribor, Slovenia
Bibliografia
  • [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.
  • [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.
  • [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.
  • [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.
  • [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.
  • [10] H.M. Mulder, The Interval Function of a Graph (Mathematical Centre Tracts 132, Mathematisch Centrum, Amsterdam, 1980).
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1299
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.