ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 27(2) (2007) 313-321
DOI: 10.7151/dmgt.1363


Sandi Klavžar

Department of Mathematics and Computer Science
FNM, University of Maribor
Gosposvetska 84, 2000 Maribor, Slovenia

Matjaz Kovse

Institute of Mathematics, Physics and Mechanics
Gosposvetska 84, 2000 Maribor, Slovenia


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 K1 by a sequence of (newly introduced) dense expansions. Θ-graphs are also compared with familiar concepts of crossing graphs and τ-graphs.

Keywords: intersection graph, partial cube, median graph, expansion theorem, Cartesian product of graphs.

2000 Mathematics Subject Classification: 05C75, 05C12.


[1] B. Bresar, Coloring of the Θ-graph of a median graph, Problem 2005.3, Maribor Graph Theory Problems.
[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.
[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.
[4] B. Bresar and T. Kraner Sumenjak, Θ-graphs of partial cubes and strong edge colorings, Ars Combin., to appear.
[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).
[7] D. Djoković, Distance preserving subgraphs of hypercubes, J. Combin. Theory (B) 14 (1973) 263-267, doi: 10.1016/0095-8956(73)90010-5.
[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.
[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.
[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.
[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.
[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.
[14] H.M. Mulder, The structure of median graphs, Discrete Math. 24 (1978) 197-204, doi: 10.1016/0012-365X(78)90199-1.
[15] H.M. Mulder, The Interval Function of a Graph (Math. Centre Tracts 132, Mathematisch Centrum, Amsterdam, 1980).
[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.
[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.

Received 25 April 2006
Revised 28 December 2006
Accepted 28 December 2006