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.