# Tree-Like Partial Hamming Graphs

Discussiones Mathematicae Graph Theory (2014)

- Volume: 34, Issue: 1, page 137-150
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topTanja Gologranc. "Tree-Like Partial Hamming Graphs." Discussiones Mathematicae Graph Theory 34.1 (2014): 137-150. <http://eudml.org/doc/267822>.

@article{TanjaGologranc2014,

abstract = {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.},

author = {Tanja Gologranc},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {partial Hamming graph; expansion procedure; dismantlable graph; gated subgraph; intersection graph},

language = {eng},

number = {1},

pages = {137-150},

title = {Tree-Like Partial Hamming Graphs},

url = {http://eudml.org/doc/267822},

volume = {34},

year = {2014},

}

TY - JOUR

AU - Tanja Gologranc

TI - Tree-Like Partial Hamming Graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2014

VL - 34

IS - 1

SP - 137

EP - 150

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

LA - eng

KW - partial Hamming graph; expansion procedure; dismantlable graph; gated subgraph; intersection graph

UR - http://eudml.org/doc/267822

ER -

## References

top- [1] H.-J. Bandelt, Retracts of hypercubes, J. Graph Theory 8 (1984) 501-510. doi:10.1002/jgt.3190080407[Crossref] Zbl0551.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] Zbl0697.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] Zbl0810.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] Zbl0628.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] Zbl0756.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] Zbl1055.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] Zbl1055.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] Zbl0873.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] Zbl0228.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] Zbl0576.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] Zbl0918.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. Zbl0931.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). Zbl0446.05039
- [20] H.M. Mulder, The expansion procedure for graphs, in: R. Bodendiek (Ed.), Contemporary Methods in Graph Theory (Wissenschaftsverlag, Mannheim, 1990) 459-477. Zbl0744.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] Zbl0508.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] Zbl0657.05023
- [24] E. Wilkeit, The retracts of Hamming graphs, Discrete Math. 102 (1992) 197-218. doi:10.1016/0012-365X(92)90054-J[Crossref] Zbl0759.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]