ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 25(1-2) (2005) 183-196
DOI: 10.7151/dmgt.1271


Bostjan Bresar

University of Maribor, FEECS
Smetanova 17, 2000 Maribor, Slovenia

Pranava K. Jha

Department of Computer Science
St. Cloud State University
720 Fourth Ave. S., St. Cloud, MN 56301, USA

Sandi Klavžar

Department of Mathematics and Computer Science, PEF
University of Maribor
Koroska 160, 2000 Maribor, Slovenia

Blaz Zmazek

University of Maribor, FME
Smetanova 17, 2000 Maribor, Slovenia


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×P3 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×K2 are proved, and it is shown that the only nonbipartite quasi-median direct product is K3×K3.

Keywords: median graph, direct product, quasi-median graph, isometric embeddings, convexity.

2000 Mathematics Subject Classification: 05C75, 05C12.


[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:4<347::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. 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.
[6] B. Bresar, 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:4<325::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.

Received 29 November 2003
Revised 1 September 2004