ISSN 2590-9770
The Art of Discrete and Applied Mathematics 6 (2023) #P2.13
https://doi.org/10.26493/2590-9770.1508.8b5
(Also available at http://adam-journal.eu)
Distance formula for direct-co-direct product in
the case of disconnected factors*
Aleksander Kelenc† , Iztok Peterin‡
University of Maribor, FERI, Koroška cesta 46, 2000 Maribor, Slovenia and
Institute of Mathematics, Physics and Mechanics, Jadranska 19, 1000 Ljubljana, Slovenia
Received 21 November 2021, accepted 25 September 2022, published online 4 January 2023
Abstract
Direct-co-direct product G⊛H of graphs G and H is a graph on the vertex set V (G)×
V (H). Two vertices (g, h) and (g′, h′) are adjacent if gg′ ∈ E(G) and hh′ ∈ E(H)
or gg′ /∈ E(G) and hh′ /∈ E(H). We show that if at most one factor of G ⊛ H is
connected, then the distance between two vertices of G ⊛ H is bounded by three unless
some small number of exceptions. All the exceptions are completely described which
yields the distance formula.
Keywords: Direct-co-direct product, distance, eccentricity, disconnected graphs.
Math. Subj. Class.: 05C12, 05C76
*The authors would like to thanks our mentor, colleague and dear friend Wilfried Imrich, who is also our
academical father, grandfather and grand grandfather at the same time. In particular we would like to thank for
all the shared enthusiasm on the world of graph products that are also the topic of this work.
†Corresponding author. Partially supported by the Slovenian Research Agency ARRS via grant J1–2452.
‡Partially supported by the Slovenian Research Agency ARRS via program P1–0297.
E-mail addresses: aleksander.kelenc@um.si (Aleksander Kelenc), iztok.peterin@um.si (Iztok Peterin)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
ISSN 2590-9770
The Art of Discrete and Applied Mathematics 6 (2023) #P2.13
https://doi.org/10.26493/2590-9770.1508.8b5
(Dostopno tudi na http://adam-journal.eu)
Formula za razdaljo med dvema vozliščema v
direktnem-ko-direktnem produktu, kadar so
faktorji nepovezani*
Aleksander Kelenc† , Iztok Peterin‡
Univerza v Mariboru, FERI, Koroška cesta 46, 2000 Maribor, Slovenija and
Inštitut za matematiko, fiziko in mehaniko, Jadranska 19, 1000 Ljubljana, Slovenija
Prejeto 21. novembra 2021, sprejeto 25. septembra 2022, objavljeno na spletu 4. januarja 2023
Povzetek
Direktni-ko-direktni produkt G⊛H grafov G in H je graf na množici vozlišč V (G)×
V (H). Dve vozlišči (g, h) in (g′, h′) tega produkta sta sosedni, če je gg′ ∈ E(G) in
hh′ ∈ E(H) ali gg′ /∈ E(G) in hh′ /∈ E(H). Pokažemo, da velja: če je največ en faktor
produkta G ⊛ H povezan, potem je razdalja med dvema vozliščema v njem omejena s
tri, razen za nekaj malega izjem. Vse izjeme natančno opišemo, na podlagi česar lahko
izpeljemo formulo za razdaljo.
Ključne besede: Direktni-ko-direktni produkt, razdalja, ekscentričnost, nepovezani grafi.
Math. Subj. Class.: 05C12, 05C76
*Avtorja bi se rada zahvalila najinemu mentorju, sodelavcu in dragemu prijatelju Wilfriedu Imrichu, ki je tudi
najin akademski oče, ded in praded, vse hkrati. Posebej bi se mu rada zahvalila, da si je z nama delil navdušenje
za produkte grafov, ki so tudi tema tega dela.
†Kontaktni avtor. Delno podprt s strani Javne agencije za raziskovalno dejavnost Republike Slovenije ARRS
v okviru dotacije J1–2452.
‡Delno podprt s strani Javne agencije za raziskovalno dejavnost Republike Slovenije ARRS v okviru programa
P1–0297.
E-poštni naslovi: aleksander.kelenc@um.si (Aleksander Kelenc), iztok.peterin@um.si (Iztok Peterin)
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/4.0/