Tree-Like Partial Hamming Graphs

Tanja Gologranc

Discussiones Mathematicae Graph Theory (2014)

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

Abstract

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

How to cite

top

Tanja 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. [1] H.-J. Bandelt, Retracts of hypercubes, J. Graph Theory 8 (1984) 501-510. doi:10.1002/jgt.3190080407[Crossref] Zbl0551.05060
  2. [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. [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. [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. [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. [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. [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. [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. [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. [10] V. Chepoi, Isometric subgraphs of Hamming graphs and d-convexity, Cybernetics 1 (1988) 6-9. doi:10.1007/BF01069520[Crossref] 
  11. [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. [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. [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. [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. [15] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (John Wiley & Sons, New York, 2000). 
  16. [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. [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. [18] H.M. Mulder, n-cubes and median graphs, J. Graph Theory 4 (1980) 107-110. doi:10.1002/jgt.3190040112[Crossref] 
  19. [19] H.M. Mulder, The Interval Function of a Graph (Mathematical Centre Tracts 132, Mathematisch Centrum, Amsterdam, 1980). Zbl0446.05039
  20. [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. [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. [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. [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. [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. [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] 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.