Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2014 | 34 | 1 | 137-150
Tytuł artykułu

Tree-Like Partial Hamming Graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
Tree-like partial cubes were introduced in [B. Brešar, W. Imrich, S. Klavžar, Tree-like isometric subgraphs of hypercubes, Discuss. Math. Graph Theory, 23 (2003), 227-240] as a generalization of median graphs. We present some incorrectnesses from that article. In particular we point to a gap in the proof of the theorem about the dismantlability of the cube graph of a tree-like partial cube and give a new proof of that result, which holds also for a bigger class of graphs, so called tree-like partial Hamming graphs. We investigate these graphs and show some results which imply previously-known results on tree-like partial cubes. For instance, we characterize tree-like partial Hamming graphs and prove that every tree-like partial Hamming graph G contains a Hamming graph that is invariant under every automorphism of G. The latter result is a direct consequence of the result about the dismantlability of the intersection graph of maximal Hamming graphs of a tree-like partial Hamming graph.
Opis fizyczny
  • Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
  • [1] H.-J. Bandelt, Retracts of hypercubes, J. Graph Theory 8 (1984) 501-510. doi:10.1002/jgt.3190080407[Crossref]
  • [2] H.-J. Bandelt and H.M. Mulder, Helly Theorems for dismantlable graphs and pseudo- modular graphs, in: R. Bodendiek, R. Henn (Eds.), Topics in Combinatorics and Graph Theory, Physica-Verlag (1990) 65-71. doi:10.1007/978-3-642-46908-4 7[Crossref]
  • [3] H.-J. Bandelt, H.M. Mulder and E. Wilkeit, Quasi-median graphs and algebras, J. Graph Theory 18 (1994) 681-703. doi:10.1002/jgt.3190180705[Crossref]
  • [4] H.-J. Bandelt and 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[Crossref]
  • [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[Crossref]
  • [6] B. Brešar, Arboreal structure and regular graphs of median-like classes, Discuss. Math. Graph Theory 23 (2003) 215-225. doi:10.7151/dmgt.1198[Crossref]
  • [7] B. Brešar, Partial Hamming graphs and expansion procedures, Discrete Math. 237 (2001) 13-27. doi:10.1016/S0012-365X(00)00362-9[Crossref]
  • [8] B. Brešar, W. Imrich and S. Klavžar, Tree-like isometric subgraphs of hypercubes, Discuss. Math. Graph Theory 23 (2003) 227-240. doi:10.7151/dmgt.1199[Crossref]
  • [9] 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[Crossref]
  • [10] V. Chepoi, Isometric subgraphs of Hamming graphs and d-convexity, Cybernetics 1 (1988) 6-9. doi:10.1007/BF01069520[Crossref]
  • [11] F.R.K. Chung, R.L. Graham and M.E. Saks, A dynamic location problem for graphs, Combinatorica 9 (1989) 111-131. doi:10.1007/BF02124674[Crossref]
  • [12] R.L. Graham and H.O. Pollak, On addressing problem for loop switching, Bell System Tech. J. 50 (1971) 2495-2519. doi:10.1002/j.1538-7305.1971.tb02618.x[Crossref]
  • [13] R.L. Graham and P. Winkler, On isometric embeddings of graphs, Trans. Amer. Math. Soc. 288 (1985) 527-539. doi:10.1090/S0002-9947-1985-0776391-5[Crossref]
  • [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[Crossref]
  • [15] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (John Wiley & Sons, New York, 2000).
  • [16] S. Klavžar and H.M. Mulder, Median graphs: characterizations, location theory and related structures, J. Combin. Math. Combin. Comput. 30 (1999) 103-127.
  • [17] H.M. Mulder, The structure of median graphs, Discrete Math. 24 (1978) 197-204. doi:10.1016/0012-365X(78)90199-1[Crossref]
  • [18] H.M. Mulder, n-cubes and median graphs, J. Graph Theory 4 (1980) 107-110. doi:10.1002/jgt.3190040112[Crossref]
  • [19] H.M. Mulder, The Interval Function of a Graph (Mathematical Centre Tracts 132, Mathematisch Centrum, Amsterdam, 1980).
  • [20] H.M. Mulder, The expansion procedure for graphs, in: R. Bodendiek (Ed.), Contemporary Methods in Graph Theory (Wissenschaftsverlag, Mannheim, 1990) 459-477.
  • [21] 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[Crossref]
  • [22] C. Tardif, Prefibers and the Cartesian product of metric spaces, Discrete Math. 109 (1992) 283-288. doi:10.1016/0012-365X(92)90298-T[Crossref]
  • [23] E. Wilkeit, Isometric embeddings in Hamming graphs, J. Combin. Theory (B) 50 (1990) 179-197. doi:10.1016/0095-8956(90)90073-9[Crossref]
  • [24] E. Wilkeit, The retracts of Hamming graphs, Discrete Math. 102 (1992) 197-218. doi:10.1016/0012-365X(92)90054-J[Crossref]
  • [25] P. Winkler, Isometric embeddings in products of complete graphs, Discrete Appl. Math. 7 (1984) 221-225. doi:10.1016/0166-218X(84)90069-6 [Crossref]
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ć.