Median and quasi-median direct products of graphs
Boštjan Brešar ; Pranava K. Jha ; Sandi Klavžar ; Blaž Zmazek
Discussiones Mathematicae Graph Theory, Tome 25 (2005), p. 183-196 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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

Publié le : 2005-01-01
EUDML-ID : urn:eudml:doc:270212 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1271,
     author = {Bo\v stjan Bre\v sar and Pranava K. Jha and Sandi Klav\v zar and Bla\v z Zmazek},
     title = {Median and quasi-median direct products of graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {25},
     year = {2005},
     pages = {183-196},
     zbl = {1079.05082},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1271}
}

Boštjan Brešar; Pranava K. Jha; Sandi Klavžar; Blaž Zmazek. Median and quasi-median direct products of graphs. Discussiones Mathematicae Graph Theory, Tome 25 (2005) pp. 183-196. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1271/

[000] [1] G. Abay-Asmerom and R. Hammack, Centers of tensor products of graphs, Ars Combin., to appear. | Zbl 1081.05090

[001] [2] H.-J. Bandelt, Retracts of hypercubes, J. Graph Theory 8 (1984) 501-510, doi: 10.1002/jgt.3190080407. | Zbl 0551.05060

[002] [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 | Zbl 0857.05079

[003] [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. | Zbl 0810.05057

[004] [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. | Zbl 1055.05129

[005] [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. | Zbl 1022.05070

[006] [7] M. Deza and M. Laurent, Geometry of Cuts and Metrics (Springer-Verlag, Berlin, 1997). | Zbl 0885.52001

[007] [8] D. Djoković, Distance preserving subgraphs of hypercubes, J. Combin. Theory (B) 14 (1973) 263-267, doi: 10.1016/0095-8956(73)90010-5. | Zbl 0245.05113

[008] [9] J. Hagauer and S. Klavžar, Clique-gated graphs, Discrete Math. 161 (1996) 143-149, doi: 10.1016/0012-365X(95)00280-A. | Zbl 0869.05054

[009] [10] W. Imrich, Factoring cardinal product graphs in polynomial time, Discrete Math. 192 (1998) 119-144, doi: 10.1016/S0012-365X(98)00069-7. | Zbl 0955.68089

[010] [11] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (Wiley, New York, 2000).

[011] [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. | Zbl 0906.05050

[012] [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. | Zbl 0765.05093

[013] [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. | Zbl 0931.05072

[014] [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. | Zbl 0953.05065

[015] [16] H.M. Mulder, The structure of median graphs, Discrete Math. 24 (1978) 197-204, doi: 10.1016/0012-365X(78)90199-1. | Zbl 0394.05038

[016] [17] H.M. Mulder, The Interval Function of a Graph (Mathematisch Centrum, Amsterdam, 1980). | Zbl 0446.05039

[017] [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 | Zbl 0863.05068

[018] [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. | Zbl 0102.38801

[019] [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. | Zbl 0529.05055