Median and quasi-median direct products of graphs

Boštjan Brešar; Pranava K. Jha; Sandi Klavžar; Blaž Zmazek

Discussiones Mathematicae Graph Theory (2005)

  • Volume: 25, Issue: 1-2, page 183-196
  • ISSN: 2083-5892

Abstract

top
Median graphs are characterized among direct products of graphs on at least three vertices. Beside some trivial cases, it is shown that one component of G×P₃ is median if and only if G is a tree in that the distance between any two vertices of degree at least 3 is even. In addition, some partial results considering median graphs of the form G×K₂ are proved, and it is shown that the only nonbipartite quasi-median direct product is K₃×K₃.

How to cite

top

Boštjan Brešar, et al. "Median and quasi-median direct products of graphs." Discussiones Mathematicae Graph Theory 25.1-2 (2005): 183-196. <http://eudml.org/doc/270212>.

@article{BoštjanBrešar2005,
abstract = {Median graphs are characterized among direct products of graphs on at least three vertices. Beside some trivial cases, it is shown that one component of G×P₃ is median if and only if G is a tree in that the distance between any two vertices of degree at least 3 is even. In addition, some partial results considering median graphs of the form G×K₂ are proved, and it is shown that the only nonbipartite quasi-median direct product is K₃×K₃.},
author = {Boštjan Brešar, Pranava K. Jha, Sandi Klavžar, Blaž Zmazek},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {median graph; direct product; quasi-median graph; isometric embeddings; convexity; tree; distance},
language = {eng},
number = {1-2},
pages = {183-196},
title = {Median and quasi-median direct products of graphs},
url = {http://eudml.org/doc/270212},
volume = {25},
year = {2005},
}

TY - JOUR
AU - Boštjan Brešar
AU - Pranava K. Jha
AU - Sandi Klavžar
AU - Blaž Zmazek
TI - Median and quasi-median direct products of graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2005
VL - 25
IS - 1-2
SP - 183
EP - 196
AB - Median graphs are characterized among direct products of graphs on at least three vertices. Beside some trivial cases, it is shown that one component of G×P₃ is median if and only if G is a tree in that the distance between any two vertices of degree at least 3 is even. In addition, some partial results considering median graphs of the form G×K₂ are proved, and it is shown that the only nonbipartite quasi-median direct product is K₃×K₃.
LA - eng
KW - median graph; direct product; quasi-median graph; isometric embeddings; convexity; tree; distance
UR - http://eudml.org/doc/270212
ER -

References

top
  1. [1] G. Abay-Asmerom and R. Hammack, Centers of tensor products of graphs, Ars Combin., to appear. Zbl1081.05090
  2. [2] H.-J. Bandelt, Retracts of hypercubes, J. Graph Theory 8 (1984) 501-510, doi: 10.1002/jgt.3190080407. Zbl0551.05060
  3. [3] H.-J. Bandelt, G. Burosch and J.-M. Laborde, Cartesian products of trees and paths, J. Graph Theory 22 (1996) 347-356, doi: 10.1002/(SICI)1097-0118(199608)22:4<347::AID-JGT8>3.0.CO;2-L Zbl0857.05079
  4. [4] H.-J. Bandelt, H.M. Mulder and E. Wilkeit, Quasi-median graphs and algebras, J. Graph Theory 18 (1994) 681-703, doi: 10.1002/jgt.3190180705. Zbl0810.05057
  5. [5] B. Brešar, 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
  6. [6] B. Brešar, S. Klavžar and R. Skrekovski, Quasi-median graphs, their generalizations, and tree-like equalities, European J. Combin. 24 (2003) 557-572, doi: 10.1016/S0195-6698(03)00045-3. Zbl1022.05070
  7. [7] M. Deza and M. Laurent, Geometry of Cuts and Metrics (Springer-Verlag, Berlin, 1997). Zbl0885.52001
  8. [8] 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
  9. [9] J. Hagauer and S. Klavžar, Clique-gated graphs, Discrete Math. 161 (1996) 143-149, doi: 10.1016/0012-365X(95)00280-A. Zbl0869.05054
  10. [10] W. Imrich, Factoring cardinal product graphs in polynomial time, Discrete Math. 192 (1998) 119-144, doi: 10.1016/S0012-365X(98)00069-7. Zbl0955.68089
  11. [11] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (Wiley, New York, 2000). 
  12. [12] P.K. Jha, S. Klavžar and B. Zmazek, Isomorphic components of Kronecker products of bipartite graphs, Discuss. Math. Graph Theory 17 (1997) 301-309, doi: 10.7151/dmgt.1057. Zbl0906.05050
  13. [13] S.-R. Kim, Centers of a tensor composite graph, in: Proceedings of the Twenty-second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991), Congr. Numer. 81 (1991) 193-203. Zbl0765.05093
  14. [14] S. Klavžar and H.M. Mulder, Median graphs: characterizations, location theory and related structures, J. Combin. Math. Combin. Comp. 30 (1999) 103-127. Zbl0931.05072
  15. [15] S. Klavžar and R. Skrekovski, On median graphs and median grid graphs, Discrete Math. 219 (2000) 287-293, doi: 10.1016/S0012-365X(00)00085-6. Zbl0953.05065
  16. [16] H.M. Mulder, The structure of median graphs, Discrete Math. 24 (1978) 197-204, doi: 10.1016/0012-365X(78)90199-1. Zbl0394.05038
  17. [17] H.M. Mulder, The Interval Function of a Graph (Mathematisch Centrum, Amsterdam, 1980). Zbl0446.05039
  18. [18] C. Tardif, On compact median graphs, J. Graph Theory 23 (1996) 325-336, doi: 10.1002/(SICI)1097-0118(199612)23:4<325::AID-JGT1>3.0.CO;2-T Zbl0863.05068
  19. [19] P.M. Weichsel, The Kronecker product of graphs, Proc. Amer. Math. Soc. 13 (1962) 47-52, doi: 10.1090/S0002-9939-1962-0133816-6. Zbl0102.38801
  20. [20] P.M. Winkler, Isometric embedding 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.