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.
@article{bwmeta1.element.doi-10_7151_dmgt_1723,
author = {Tanja Gologranc},
title = {Tree-Like Partial Hamming Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {34},
year = {2014},
pages = {137-150},
zbl = {1292.05099},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1723}
}
Tanja Gologranc. Tree-Like Partial Hamming Graphs. Discussiones Mathematicae Graph Theory, Tome 34 (2014) pp. 137-150. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1723/
[1] H.-J. Bandelt, Retracts of hypercubes, J. Graph Theory 8 (1984) 501-510. doi:10.1002/jgt.3190080407[Crossref] | Zbl 0551.05060
[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] | Zbl 0697.05034
[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] | Zbl 0810.05057
[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] | Zbl 0628.05053
[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] | Zbl 0756.05091
[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] | Zbl 1055.05040
[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] | Zbl 1055.05129
[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] | Zbl 0873.05060
[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] | Zbl 0228.94020
[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] | Zbl 0576.05017
[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] | Zbl 0918.05085
[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. | Zbl 0931.05072
[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). | Zbl 0446.05039
[20] H.M. Mulder, The expansion procedure for graphs, in: R. Bodendiek (Ed.), Contemporary Methods in Graph Theory (Wissenschaftsverlag, Mannheim, 1990) 459-477. | Zbl 0744.05064
[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] | Zbl 0508.05058
[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] | Zbl 0657.05023
[24] E. Wilkeit, The retracts of Hamming graphs, Discrete Math. 102 (1992) 197-218. doi:10.1016/0012-365X(92)90054-J[Crossref] | Zbl 0759.05085
[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]