# On θ-graphs of partial cubes

Discussiones Mathematicae Graph Theory (2007)

- Volume: 27, Issue: 2, page 313-321
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topSandi Klavžar, and Matjaz Kovse. "On θ-graphs of partial cubes." Discussiones Mathematicae Graph Theory 27.2 (2007): 313-321. <http://eudml.org/doc/270620>.

@article{SandiKlavžar2007,

abstract = {The Θ-graph Θ(G) of a partial cube G is the intersection graph of the equivalence classes of the Djoković-Winkler relation. Θ-graphs that are 2-connected, trees, or complete graphs are characterized. In particular, Θ(G) is complete if and only if G can be obtained from K₁ by a sequence of (newly introduced) dense expansions. Θ-graphs are also compared with familiar concepts of crossing graphs and τ-graphs.},

author = {Sandi Klavžar, Matjaz Kovse},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {intersection graph; partial cube; median graph; expansion theorem; Cartesian product of graphs; expansion},

language = {eng},

number = {2},

pages = {313-321},

title = {On θ-graphs of partial cubes},

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

volume = {27},

year = {2007},

}

TY - JOUR

AU - Sandi Klavžar

AU - Matjaz Kovse

TI - On θ-graphs of partial cubes

JO - Discussiones Mathematicae Graph Theory

PY - 2007

VL - 27

IS - 2

SP - 313

EP - 321

AB - The Θ-graph Θ(G) of a partial cube G is the intersection graph of the equivalence classes of the Djoković-Winkler relation. Θ-graphs that are 2-connected, trees, or complete graphs are characterized. In particular, Θ(G) is complete if and only if G can be obtained from K₁ by a sequence of (newly introduced) dense expansions. Θ-graphs are also compared with familiar concepts of crossing graphs and τ-graphs.

LA - eng

KW - intersection graph; partial cube; median graph; expansion theorem; Cartesian product of graphs; expansion

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

ER -

## References

top- [1] B. Bresar, Coloring of the Θ-graph of a median graph, Problem 2005.3, Maribor Graph Theory Problems. http://www-mat.pfmb.uni-mb.si/personal/klavzar/MGTP/index.html.
- [2] B. Bresar, 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. Zbl1055.05129
- [3] B. Bresar and S. Klavžar, Crossing graphs as joins of graphs and Cartesian products of median graphs, SIAM J. Discrete Math. 21 (2007) 26-32, doi: 10.1137/050622997. Zbl1141.05071
- [4] B. Bresar and T. Kraner Sumenjak, Θ-graphs of partial cubes and strong edge colorings, Ars Combin., to appear. Zbl1224.05160
- [5] V.D. Chepoi, d-Convexity and isometric subgraphs of Hamming graphs, Cybernetics 1 (1988) 6-9, doi: 10.1007/BF01069520.
- [6] M.M. Deza and M. Laurent, Geometry of cuts and metrics, Algorithms and Combinatorics, 15 (Springer-Verlag, Berlin, 1997). Zbl0885.52001
- [7] D. Djoković, Distance preserving subgraphs of hypercubes, J. Combin. Theory (B) 14 (1973) 263-267, doi: 10.1016/0095-8956(73)90010-5. Zbl0245.05113
- [8] R.J. Faudree, A. Gyarfas, R.H. Schelp and Z. Tuza, Induced matchings in bipartite graphs, Discrete Math. 78 (1989) 83-87, doi: 10.1016/0012-365X(89)90163-5. Zbl0709.05026
- [9] 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. Zbl0918.05085
- [10] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (Wiley, New York, 2000).
- [11] S. Klavžar and M. Kovse, Partial cubes and their τ-graphs, European J. Combin. 28 (2007) 1037-1042. Zbl1120.05027
- [12] S. Klavžar and H.M. Mulder, Partial cubes and crossing graphs, SIAM J. Discrete Math. 15 (2002) 235-251, doi: 10.1137/S0895480101383202. Zbl1003.05089
- [13] F.R. McMorris, H.M. Mulder and F.R. Roberts, The median procedure on median graphs, Discrete Appl. Math. 84 (1998) 165-181, doi: 10.1016/S0166-218X(98)00003-1. Zbl0906.05023
- [14] H.M. Mulder, The structure of median graphs, Discrete Math. 24 (1978) 197-204, doi: 10.1016/0012-365X(78)90199-1. Zbl0394.05038
- [15] H.M. Mulder, The Interval Function of a Graph (Math. Centre Tracts 132, Mathematisch Centrum, Amsterdam, 1980). Zbl0446.05039
- [16] M. van de Vel, Theory of Convex Structures (North-Holland, Amsterdam, 1993).
- [17] A. Vesel, Characterization of resonance graphs of catacondensed hexagonal graphs, MATCH Commun. Math. Comput. Chem. 53 (2005) 195-208. Zbl1077.05088
- [18] P. Winkler, Isometric embeddings in products of complete graphs, Discrete Appl. Math. 7 (1984) 221-225, doi: 10.1016/0166-218X(84)90069-6. Zbl0529.05055

## NotesEmbed ?

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