On One-Factorizations of Replacement Products


Alireza Abdollahi, Amir Loghman




Let $G$ be an $(n,m)$-graph ($n$ vertices and $m$-regular) and $H$ be an $(m,d)$-graph. Randomly number the edges around each vertex of $G$ by $\{1,\ldots,m\}$ and fix it. Then the replacement product $G\circledR\circledR H$ of graphs $G$ and $H$ (with respect to the numbering) has vertex set $V(G)\circledR H)=V(G)\times V(H)$ and there is an edge between $(v,k)$ and $(w,l)$ if $v=w$ and $kl\in E(G)$ or $vw\in E(G)$ and $k$th edge incident on vertex $v$ in $G$ is connected to the vertex $w$ and this edge is the $l$th edge incident on $w$ in $G$, where the numberings $k$ and $l$ refers to the random numberings of edges adjacent to any vertex of $G$. If the set of edges of a graph can be partitioned to a set of complete matchings, then the graph is called 1-factorizable and any such partition is called a 1-factorization. In this paper, 1-factorizability of the replacement product $G\circledR H$ of graphs $G$ and $H$ is studied. As an application we show that fullerene $C_{60}$ and $C_4C_8$ nanotorus are 1-factorizable.