V okviru raziskovalnega programa smo obravnavali grafovske produkte, njihove invariante in sorodne probleme. Študirali smo medianske grafe s poudarkom na problemu prepoznavanja. V povezavi z medianskimi grafi smo obravnavali tudi različne druge razrede grafov, ki se naravno pojavijo pri tej teoriji: izometrične podgrafe hiperkock, semi-medianske grafe, kvazi-medianske grafe in izometrične podgrafe Hammingovih grafov. Metrično teorijo grafov smo med drugim uporabili v kemijski teoriji grafov za izračun različnih topoloških invariant. Obravnavali smo tudi grafe z zastraženimi klikami in problem določitve najmanjšega števila linearnih gozdov. Na področju računalniške matematike smo se posebej posvetili razvoju hitrih algoritmov za prepoznavanje pomembnih razredov grafov in problemom v zvezi s posplošitvami klasičnega problema Hanojskih stolpov. Eden najvažnejših ciljev raziskovalnega programa je bila monografija v angleščini, ki pokriva grafovske produkte in sorodne teme. Kumulativno smo objavili 56 znanstvenih člankov, od tega 44 v revijah, ki jih pokriva JCR. Z referati smo sodelovali na številnih mednarodnih konferencah ter imeli tudi več vabljenih predavanj na konferencah in tujih univerzah. Objavili smo znanstveno W. Imrich, S. Klavžar, Product Graphs: Structure and Recognition, ki je leta 2000 izšla pri enem najuglednejših svetovnih založnikov znanstvene literature Wiley v New Yorku. Sodelovali smo s številnimi uveljavljenimi znanstveniki iz tujine, med drugim z W. Imrichom iz Leobna, Avstrija, H.M. Mulderjem z Erasmus Universiteit Rotterdam, I. Gutmanom z Univerze v Kragujevcu, I. Ivanšićem z Univerze v Zagrebu, Hrvaška, M. Mollardom in S. Gravierjem z inštituta IMAG v Grenoblu, Francija.