Geodesic
Tree-Like Partial Hamming Graphs
Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 1, pp. 137-150.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: partial Hamming graph, expansion procedure, dismantlable graph, gated subgraph, intersection graph 
@article{DMGT_2014_34_1_a11,
     author = {Gologranc, Tanja},
     title = {Tree-Like {Partial} {Hamming} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {137--150},
     publisher = {mathdoc},
     volume = {34},
     number = {1},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2014_34_1_a11/}
}
TY  - JOUR
AU  - Gologranc, Tanja
TI  - Tree-Like Partial Hamming Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2014
SP  - 137
EP  - 150
VL  - 34
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2014_34_1_a11/
LA  - en
ID  - DMGT_2014_34_1_a11
ER  - 
%0 Journal Article
%A Gologranc, Tanja
%T Tree-Like Partial Hamming Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2014
%P 137-150
%V 34
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2014_34_1_a11/
%G en
%F DMGT_2014_34_1_a11
Gologranc, Tanja. Tree-Like Partial Hamming Graphs. Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 1, pp. 137-150. http://geodesic.mathdoc.fr/item/DMGT_2014_34_1_a11/

[1] H.-J. Bandelt, Retracts of hypercubes, J. Graph Theory 8 (1984) 501-510. doi:10.1002/jgt.3190080407

[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

[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

[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

[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, Arboreal structure and regular graphs of median-like classes, Discuss. Math. Graph Theory 23 (2003) 215-225. doi:10.7151/dmgt.1198

[7] B. Brešar, Partial Hamming graphs and expansion procedures, Discrete Math. 237 (2001) 13-27. doi:10.1016/S0012-365X(00)00362-9

[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

[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

[10] V. Chepoi, Isometric subgraphs of Hamming graphs and d-convexity, Cybernetics 1 (1988) 6-9. doi:10.1007/BF01069520

[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

[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

[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

[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] 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

[18] H.M. Mulder, n-cubes and median graphs, J. Graph Theory 4 (1980) 107-110. doi:10.1002/jgt.3190040112

[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

[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

[23] E. Wilkeit, Isometric embeddings in Hamming graphs, J. Combin. Theory (B) 50 (1990) 179-197. doi:10.1016/0095-8956(90)90073-9

[24] E. Wilkeit, The retracts of Hamming graphs, Discrete Math. 102 (1992) 197-218. doi:10.1016/0012-365X(92)90054-J

[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