DMGT

Discussiones Mathematicae Graph Theory 23(2) (2003) 227-240
DOI: https://doi.org/10.7151/dmgt.1199

TREE-LIKE ISOMETRIC SUBGRAPHS OF HYPERCUBES

Bostjan Bresar^*

University of Maribor
FERI, Smetanova 17, 2000 Maribor, Slovenia
e-mail: bostjan.bresar@uni-mb.si

Wilfried Imrich

Montanuniversität Leoben
A-8700 Leoben, Austria
e-mail: imrich@unileoben.ac.at

Sandi Klavžar¹

Department of Mathematics, PEF, University of Maribor
Koroska cesta 160, 2000 Maribor, Slovenia
e-mail: sandi.klavzar@uni-mb.si

Abstract

Tree-like isometric subgraphs of hypercubes, or tree-like partial cubes as we shall call them, are a generalization of median graphs. Just as median graphs they capture numerous properties of trees, but may contain larger classes of graphs that may be easier to recognize than the class of median graphs. We investigate the structure of tree-like partial cubes, characterize them, and provide examples of similarities with trees and median graphs. For instance, we show that the cube graph of a tree-like partial cube is dismantlable. This in particular implies that every tree-like partial cube G contains a cube that is invariant under every automorphism of G. We also show that weak retractions preserve tree-like partial cubes, which in turn implies that every contraction of a tree-like partial cube fixes a cube. The paper ends with several Frucht-type results and a list of open problems.

Keywords: isometric embeddings, partial cubes, expansion procedures, trees, median graphs, graph automorphisms, automorphism groups, dismantlable graphs.

2000 Mathematics Subject Classification: 05C75, 05C12, 05C05, 05C25.

References

[1]	F. Aurenhammer and J. Hagauer, Recognizing binary Hamming graphs in O(n²logn) time, Math. Systems Theory 28 (1995) 387-396, doi: 10.1007/BF01185863.
[2]	H.-J. Bandelt, Retracts of hypercubes, J. Graph Theory 8 (1984) 501-510, doi: 10.1002/jgt.3190080407.
[3]	H.-J. Bandelt and E. Prisner, Clique graphs and Helly graphs, J. Combin. Theory (B) 51 (1991) 34-45, doi: 10.1016/0095-8956(91)90004-4.
[4]	H.-J. Bandelt, 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. Bresar, W. Imrich and S. Klavžar, Fast recognition algorithms for classes of partial cubes, Discrete Appl. Math., in press.
[7]	B. Bresar, W. Imrich, S. Klavžar, H.M. Mulder and R. Skrekovski, Tiled partial cubes, J. Graph Theory 40 (2002) 91-103, doi: 10.1002/jgt.10031.
[8]	B. Bresar, S. Klavžar, R. Skrekovski, Cubes polynomial and its derivatives, Electron. J. Combin. 10 (2003) #R3, pp. 11.
[9]	V. Chepoi, d-Convexity and isometric subgraphs of Hamming graphs, Cybernetics 1 (1988) 6-10, doi: 10.1007/BF01069520.
[10]	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.
[11]	D. Djoković, Distance preserving subgraphs of hypercubes, J. Combin. Theory (B) 14 (1973) 263-267, doi: 10.1016/0095-8956(73)90010-5.
[12]	R. Frucht, Herstellung von Graphen mit vorgegebener abstrakter Gruppe, Compositio Math. 6 (1938) 239-250.
[13]	J. Hagauer, W. Imrich and S. Klavžar, Recognizing median graphs in subquadratic time, Theoret. Comput. Sci. 215 (1999) 123-136, doi: 10.1016/S0304-3975(97)00136-9.
[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]	W. Imrich, S. Klavžar, and H.M. Mulder, Median graphs and triangle-free graphs, SIAM J. Discrete Math. 12 (1999) 111-118, doi: 10.1137/S0895480197323494.
[17]	S. Klavžar and A. Lipovec, Partial cubes as subdivision graphs and as generalized Petersen graphs, Discrete Math. 263 (2003) 157-165, doi: 10.1016/S0012-365X(02)00575-7.
[18]	S. Klavžar and H.M. Mulder, Median graphs: characterizations, location theory and related structures, J. Combin. Math. Combin. Comp. 30 (1999) 103-127.
[19]	H.M. Mulder, The structure of median graphs, Discrete Math. 24 (1978) 197-204, doi: 10.1016/0012-365X(78)90199-1.
[20]	H.M. Mulder, n-Cubes and median graphs, J. Graph Theory 4 (1980) 107-110, doi: 10.1002/jgt.3190040112.
[21]	H.M. Mulder, The Interval Function of a Graph, (Mathematical Centre Tracts 132, Mathematisch Centrum, Amsterdam, 1980).
[22]	H.M. Mulder, The expansion procedure for graphs, in: R. Bodendiek (ed.), Contemporary Methods in Graph Theory (Wissenschaftsverlag, Mannheim, 1990) 459-477.
[23]	R. Nowakowski and I. Rival, Fixed-edge theorem for graphs with loops, J. Graph Theory 3 (1979) 339-350, doi: 10.1002/jgt.3190030404.
[24]	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.
[25]	G. Sabidussi, Graphs with given group and given graph-theoretical properties, Canad. J. Math. 9 (1957) 515-525, doi: 10.4153/CJM-1957-060-7.
[26]	R. Skrekovski, Two relations for median graphs, Discrete Math. 226 (2001) 351-353, doi: 10.1016/S0012-365X(00)00120-5.
[27]	P.S. Soltan and V. Chepoi, Solution of the Weber problem for discrete median metric spaces, (Russian) Trudy Tbiliss. Mat. Inst. Razmadze Akad. Nauk Gruzin. SSR 85 (1987) 52-76.
[28]	C. Tardif, Prefibers and the Cartesian product of metric spaces, Discrete Math. 109 (1992) 283-288, doi: 10.1016/0012-365X(92)90298-T.
[29]	P. Winkler, Isometric embeddings in products of complete graphs, Discrete Appl. Math. 7 (1984) 221-225, doi: 10.1016/0166-218X(84)90069-6.

Received 9 January 2002
Revised 11 June 2002

Footnotes:

¹Supported by the Ministry of Education, Science and Sport of Slovenia under the grants Z1-3073, and 0101-P-504, respectively.