Generating \(r\)-regular graphs (Q1406030)

The authors study the problem of \(r\)-regular graph generation. The considered graphs can posses multiple edges between each pair \((x,y)\) of vertices, so they can be seen as labeled graphs with an integer accompanying each edge. Therefore, the subjective loopless graphs can be seen as flow networks. Two general approaches to generation are discussed. The first one is the generation by extension, i.e., we add more and more edges one by one getting \(r\)-regular graphs of greater size. The second approach is by reduction of consecutive vertices preserving the general connectivity of the graphs, i.e., the general properties are preserved and the edges accompanying the removed vertex(ices) are replaced with new edges connecting the neighbors, so that the \(r\)-regularity of the obtained graph is preserved and the vertices connected previously through the removed vertex became connected directly. This model represents reduction of flow networks with maximal flow preserving. The authors study several operations that can be used for subclasses of dedicated graphs. The first operation is called splitting the vertex and is denoted with S. The second operation is called doubled splitting and is denoted with DS, in fact this operation removes in one time two vertices instead of one and preserves the general mentioned properties of vertices removal. The next operation, called redoubled splitting and denoted DS+ can be seen as a composition of three S operations. For other general classes of graphs the authors study the reduction problem in terms of existence of operators enabling the reduction. They claim that such operations exist, however they do not specify them explicitly. The results seem to be worth mention for those studying the flow algorithms.