Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2003 | 23 | 2 | 227-240
Tytuł artykułu

Tree-like isometric subgraphs of hypercubes

Treść / Zawartość
Warianty tytułu
Języki publikacji
Tree-like isometric subgraphs of hypercubes, or tree-like partial cubes as we shall call them, are a generalization of median graphs. Just as median graphs they capture numerous properties of trees, but may contain larger classes of graphs that may be easier to recognize than the class of median graphs. We investigate the structure of tree-like partial cubes, characterize them, and provide examples of similarities with trees and median graphs. For instance, we show that the cube graph of a tree-like partial cube is dismantlable. This in particular implies that every tree-like partial cube G contains a cube that is invariant under every automorphism of G. We also show that weak retractions preserve tree-like partial cubes, which in turn implies that every contraction of a tree-like partial cube fixes a cube. The paper ends with several Frucht-type results and a list of open problems.
Opis fizyczny
  • University of Maribor, FERI, Smetanova 17, 2000 Maribor, Slovenia
  • Montanuniversität Leoben, A-8700 Leoben, Austria
  • Department of Mathematics, PEF, University of Maribor, Koroska cesta 160, 2000 Maribor, Slovenia
  • [1] F. Aurenhammer and J. Hagauer, Recognizing binary Hamming graphs in O(n²log n) time, Math. Systems Theory 28 (1995) 387-396, doi: 10.1007/BF01185863.
  • [2] H.-J. Bandelt, Retracts of hypercubes, J. Graph Theory 8 (1984) 501-510, doi: 10.1002/jgt.3190080407.
  • [3] H.-J. Bandelt and E. Prisner, Clique graphs and Helly graphs, J. Combin. Theory (B) 51 (1991) 34-45, doi: 10.1016/0095-8956(91)90004-4.
  • [4] H.-J. Bandelt, M. van de Vel, A fixed cube theorem for median graphs, Discrete Math. 62 (1987) 129-137, doi: 10.1016/0012-365X(87)90022-7.
  • [5] H.-J. Bandelt and M. van de Vel, Superextensions and the depth of median graphs, J. Combin. Theory (A) 57 (1991) 187-202, doi: 10.1016/0097-3165(91)90044-H.
  • [6] B. Brešar, W. Imrich and S. Klavžar, Fast recognition algorithms for classes of partial cubes, Discrete Appl. Math., in press.
  • [7] B. Brešar, 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.
  • [8] B. Brešar, S. Klavžar, R. Skrekovski, Cubes polynomial and its derivatives, Electron. J. Combin. 10 (2003) #R3, pp. 11.
  • [9] V. Chepoi, d-Convexity and isometric subgraphs of Hamming graphs, Cybernetics 1 (1988) 6-10, doi: 10.1007/BF01069520.
  • [10] V. Chepoi, Bridged graphs are cop-win graphs: an algorithmic proof, J. Combin. Theory (B) 69 (1997) 97-100, doi: 10.1006/jctb.1996.1726.
  • [11] D. Djoković, Distance preserving subgraphs of hypercubes, J. Combin. Theory (B) 14 (1973) 263-267, doi: 10.1016/0095-8956(73)90010-5.
  • [12] R. Frucht, Herstellung von Graphen mit vorgegebener abstrakter Gruppe, Compositio Math. 6 (1938) 239-250.
  • [13] J. Hagauer, W. Imrich and S. Klavžar, Recognizing median graphs in subquadratic time, Theoret. Comput. Sci. 215 (1999) 123-136, doi: 10.1016/S0304-3975(97)00136-9.
  • [14] W. Imrich and S. Klavžar, A convexity lemma and expansion procedures for bipartite graphs, European J. Combin. 19 (1998) 677-685, doi: 10.1006/eujc.1998.0229.
  • [15] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (John Wiley & Sons, New York, 2000).
  • [16] 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.
  • [17] S. Klavžar and A. Lipovec, Partial cubes as subdivision graphs and as generalized Petersen graphs, Discrete Math. 263 (2003) 157-165, doi: 10.1016/S0012-365X(02)00575-7.
  • [18] S. Klavžar and H.M. Mulder, Median graphs: characterizations, location theory and related structures, J. Combin. Math. Combin. Comp. 30 (1999) 103-127.
  • [19] H.M. Mulder, The structure of median graphs, Discrete Math. 24 (1978) 197-204, doi: 10.1016/0012-365X(78)90199-1.
  • [20] H.M. Mulder, n-Cubes and median graphs, J. Graph Theory 4 (1980) 107-110, doi: 10.1002/jgt.3190040112.
  • [21] H.M. Mulder, The Interval Function of a Graph, (Mathematical Centre Tracts 132, Mathematisch Centrum, Amsterdam, 1980).
  • [22] H.M. Mulder, The expansion procedure for graphs, in: R. Bodendiek (ed.), Contemporary Methods in Graph Theory (Wissenschaftsverlag, Mannheim, 1990) 459-477.
  • [23] R. Nowakowski and I. Rival, Fixed-edge theorem for graphs with loops, J. Graph Theory 3 (1979) 339-350, doi: 10.1002/jgt.3190030404.
  • [24] R. Nowakowski and P. Winkler, Vertex-to-vertex pursuit in a graph, Discrete Math. 43 (1983) 235-239, doi: 10.1016/0012-365X(83)90160-7.
  • [25] G. Sabidussi, Graphs with given group and given graph-theoretical properties, Canad. J. Math. 9 (1957) 515-525, doi: 10.4153/CJM-1957-060-7.
  • [26] R. Skrekovski, Two relations for median graphs, Discrete Math. 226 (2001) 351-353, doi: 10.1016/S0012-365X(00)00120-5.
  • [27] P.S. Soltan and V. Chepoi, Solution of the Weber problem for discrete median metric spaces, (Russian) Trudy Tbiliss. Mat. Inst. Razmadze Akad. Nauk Gruzin. SSR 85 (1987) 52-76.
  • [28] C. Tardif, Prefibers and the Cartesian product of metric spaces, Discrete Math. 109 (1992) 283-288, doi: 10.1016/0012-365X(92)90298-T.
  • [29] P. Winkler, Isometric embeddings in products of complete graphs, Discrete Appl. Math. 7 (1984) 221-225, doi: 10.1016/0166-218X(84)90069-6.
Typ dokumentu
Identyfikator YADDA
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ć.