An Introduction to Graph Folding

Abstract

Graph folding is a unary operation introduced by Gervacio [6] in 1992 which he later modified in 1999.

This operation induces in a very natural way a partitioning of the vertex set of a graph into pairwise linked and independent sets. In this paper we give results involving the folding of regular graphs. Here, too, we show that the famous Petersen graph folds only into the complete graphs K3, K4, and K5. In addition, among others, we will show that max{ t| Kt ∈ F(G)} <  [1+1+4rn/2] , where G is a connected r-regular graph of order n.

Furthermore, this paper enumerates some relationships of folding graphs to several graph invariants such as chromatic number, span, independence number, domination number, maximum degree, and dimension.