On one-factorizations of replacement products

Abstract

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,...,m} and fix it. Then the replacement product GrH of graphs G®H (with respect to the numbering) has vertex set V(G®H) = V(G) × V(H) and there is an edge between (v, k) and (w, l) if v = w and kl ∈ E(H) or vw ∈ E(G) and kth edge incident on vertex v in G is connected to the vertex w and this edge is the lth 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 GrH of graphs G®H is studied. As an application we show that fullerene C60 and C4C8 nanotorus are 1-factorizable.