Predavatelj: Iztok Peterin
Abstract
A graph $H$ is, following the book of Hammack, Imrich and Klavžar, a graph product of graphs $G_1$ and $G_2$ if $V(H)=V(G_1)\times V(G_2)$ and edges of $H$ are yield from some rules on edges and non-edges in $G_1$ and $G_2$. This gives all together 256 different products. Only 10 of them are asociative and comutative at the same time. They can be paired together into five pairs of a product and his complementary product. Beside well known Cartesian product, strong product and direct product and their complementary products we have also (not interesting) complete product (with empty product as its complementary product) and modular product $G_1\Diamond G_2$ with its complementary product. Edges of modular product can be express with edges of strong product and edges of direct product of complements $\overline{G_1}$ and $\overline{G_2}$, that is
$$E(G_1\Diamond G_2)=E(G_1\boxtimes G_2)\cup E(\overline{G_1}\times \overline{G_2}).$$
If we replace edges of strong product with edges of direct product, then we obtain a direct-co-direct product $G_1\circledast G_2$, or shortly DcD product, which is not associative. More detailed
$$E(G_1\circledast G_2)=E(G_1\times G_2)\cup E(\overline{G_1}\times \overline{G_2}).$$
We present history of both products, their basic properties and give a motivation why study them in more detail. Some ot their metric properties will also be revealed.
Joint work with A. Kelenc.
