Search code examples
algorithmgraphvertex-cover

representive Vertex cycle cover

This problem may be related to this post.

This problem also asked here but with a different taste.

Consider an (undirected) square graph with a periodic boundary condition. Then find a complete cycle graph with length equal to 4. now I want to assign a unique representative to each cycle from its elements. Therefore in a square graph with n_v vertex i will find n_f=n_v 4-cycles and n_v representative for the cycles. For the square graph, everything is simple. just assign the bottom left vertex of each plaque(4-cycles).

enter image description here

(i just show first 4-cycle)

Now, I want to generalize it for other structures. consider (undirected) kagome graph with proper boundary condition,

enter image description here

(here I just show 3 distinct cycles)

In this case for assigning a vertex to cycles cover, you need three different length cycles. which show by similar color with the assigned vertex. However, now I want to generalize this to other complicated graphs. I want to know is this problem has a name and about its possibility or algorithm. For example, we cannot do it in a triangular graph:

enter image description here

Solution

  • This problem solved here.

    • I)Let show all faces and vertices by \alpha_i, where i contain vertices and faces.
    • II) make a graph which relates \alpha_i (from i in face group) to \alpha_j (to j in vertex group), if j(vortex) belong to i(face).
    • III) find the independent edge set of this graph gives for any vortex a face.

    Please see here for additional information.