On θ-graphs of partial cubes

Sandi Klavžar; Matjaz Kovse

Discussiones Mathematicae Graph Theory (2007)

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

Abstract

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

How to cite

top

Sandi 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. [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. [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. [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. [4] B. Bresar and T. Kraner Sumenjak, Θ-graphs of partial cubes and strong edge colorings, Ars Combin., to appear. Zbl1224.05160
  5. [5] V.D. Chepoi, d-Convexity and isometric subgraphs of Hamming graphs, Cybernetics 1 (1988) 6-9, doi: 10.1007/BF01069520. 
  6. [6] M.M. Deza and M. Laurent, Geometry of cuts and metrics, Algorithms and Combinatorics, 15 (Springer-Verlag, Berlin, 1997). Zbl0885.52001
  7. [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. [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. [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. [10] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (Wiley, New York, 2000). 
  11. [11] S. Klavžar and M. Kovse, Partial cubes and their τ-graphs, European J. Combin. 28 (2007) 1037-1042. Zbl1120.05027
  12. [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. [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. [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. [15] H.M. Mulder, The Interval Function of a Graph (Math. Centre Tracts 132, Mathematisch Centrum, Amsterdam, 1980). Zbl0446.05039
  16. [16] M. van de Vel, Theory of Convex Structures (North-Holland, Amsterdam, 1993). 
  17. [17] A. Vesel, Characterization of resonance graphs of catacondensed hexagonal graphs, MATCH Commun. Math. Comput. Chem. 53 (2005) 195-208. Zbl1077.05088
  18. [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 ?

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.