Download PDF - On θ-graphs of partial cubesAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

On θ-graphs of partial cubes

Authors 1, 2

Affiliations

  1. Department of Mathematics and Computer Science, FNM, University of Maribor, Gosposvetska 84, 2000 Maribor, Slovenia
  2. Institute of Mathematics, Physics and Mechanics, Gosposvetska 84, 2000 Maribor, Slovenia

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.

Keywords

ENG
intersection graph, partial cube, median graph, expansion theorem, Cartesian product of graphs

Bibliography

  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.
  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.
Discussiones Mathematicae Graph Theory
2007/27/2
Export to PBN, Opens in new tab
Pages:
313-321
Main language of publication
English
Received
2006-04-25
Accepted
2006-12-28
Published
2007

DOI: 10.7151/dmgt.1363

Exact and natural sciences