Geodesic
Median and quasi-median direct products of graphs
Discussiones Mathematicae. Graph Theory, Tome 25 (2005) no. 1-2, pp. 183-196.

Voir la notice de l'article provenant de la source Library of Science

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₃.
Keywords: median graph, direct product, quasi-median graph, isometric embeddings, convexity 
@article{DMGT_2005_25_1-2_a17,
     author = {Bre\v{s}ar, Bo\v{s}tjan and Jha, Pranava and Klav\v{z}ar, Sandi and Zmazek, Bla\v{z}},
     title = {Median and quasi-median direct products of graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {183--196},
     publisher = {mathdoc},
     volume = {25},
     number = {1-2},
     year = {2005},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2005_25_1-2_a17/}
}
TY  - JOUR
AU  - Brešar, Boštjan
AU  - Jha, Pranava
AU  - Klavžar, Sandi
AU  - Zmazek, Blaž
TI  - Median and quasi-median direct products of graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2005
SP  - 183
EP  - 196
VL  - 25
IS  - 1-2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2005_25_1-2_a17/
LA  - en
ID  - DMGT_2005_25_1-2_a17
ER  - 
%0 Journal Article
%A Brešar, Boštjan
%A Jha, Pranava
%A Klavžar, Sandi
%A Zmazek, Blaž
%T Median and quasi-median direct products of graphs
%J Discussiones Mathematicae. Graph Theory
%D 2005
%P 183-196
%V 25
%N 1-2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2005_25_1-2_a17/
%G en
%F DMGT_2005_25_1-2_a17
Brešar, Boštjan; Jha, Pranava; Klavžar, Sandi; Zmazek, Blaž. Median and quasi-median direct products of graphs. Discussiones Mathematicae. Graph Theory, Tome 25 (2005) no. 1-2, pp. 183-196. http://geodesic.mathdoc.fr/item/DMGT_2005_25_1-2_a17/

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

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

[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:4347::AID-JGT8>3.0.CO;2-L

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[18] C. Tardif, On compact median graphs, J. Graph Theory 23 (1996) 325-336, doi: 10.1002/(SICI)1097-0118(199612)23:4325::AID-JGT1>3.0.CO;2-T

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

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