Return to Question

I am doing a research on networks which consists of polygons with different number of sides. I am trying to find all simple cycles in a network which are chordless. As an example, consider the following graph:

graph = Graph[
  {
    1 <-> 2,   2 <-> 3,   3 <-> 4,  4 <-> 5,   5 <-> 6,   1 <-> 6,  
    3 <-> 7,   7 <-> 8,   8 <-> 9,  9 <-> 10, 10 <-> 11, 11 <-> 3,
    4 <-> 12, 12 <-> 13, 13 <-> 11
  }, 
    VertexLabels -> "Name"
]

{1,2,3,4,5,6}, {3,4,11,12,13},{3,7,8,9,10,11} are rings and we can extract them by using:

cycles = FindFundamentalCycles[graph];
rings = Sort @* VertexList @* Graph /@ cycles  

But the above solution doesn't always work as it might give non-chordless cycles. Consider the following example:

grapht = Graph[
{
  1 <-> 2, 1 <-> 3, 2 <-> 4, 4 <-> 5, 5 <-> 6, 4 <-> 6, 
  6 <-> 7, 3 <-> 5, 3 <-> 9, 5 <-> 8, 8 <-> 9
},
VertexLabels -> "Name"];

Rings (cycles) are:

cyclest = FindFundamentalCycles[grapht]; 
HighlightGraph[grapht, #] & /@ cyclest

But I need to get {4,5,6} as a ring not {1,2,3,4,5,6} since there is an edge in the latter. Is there any way to filter out only chordless cycles?

W Community crosspost

I am doing a research on networks which consists of polygons with different number of sides. I am trying to find all simple cycles in a network which are chordless. As an example, consider the following graph:

graph = Graph[
  {
    1 <-> 2,   2 <-> 3,   3 <-> 4,  4 <-> 5,   5 <-> 6,   1 <-> 6,  
    3 <-> 7,   7 <-> 8,   8 <-> 9,  9 <-> 10, 10 <-> 11, 11 <-> 3,
    4 <-> 12, 12 <-> 13, 13 <-> 11
  }, 
    VertexLabels -> "Name"
]

{1,2,3,4,5,6}, {3,4,11,12,13},{3,7,8,9,10,11} are rings and we can extract them:

cycles = FindFundamentalCycles[graph];
rings = Sort @* VertexList @* Graph /@ cycles  

But the above solution doesn't always work as it might give non-chordless cycles. Consider the following example:

grapht = Graph[
{
  1 <-> 2, 1 <-> 3, 2 <-> 4, 4 <-> 5, 5 <-> 6, 4 <-> 6, 
  6 <-> 7, 3 <-> 5, 3 <-> 9, 5 <-> 8, 8 <-> 9
},
VertexLabels -> "Name"];

Rings (cycles) are:

cyclest = FindFundamentalCycles[grapht]; 
HighlightGraph[grapht, #] & /@ cyclest

But I need to get {4,5,6} as a ring not {1,2,3,4,5,6} since there is an edge in the latter. Is there any way to filter out only chordless cycles?

W Community crosspost

I am doing a research on networks which consists of polygons with different number of sides. I am trying to find all simple cycles in a network which are chordless. As an example, consider the following graph:

graph = Graph[
  {
    1 <-> 2,   2 <-> 3,   3 <-> 4,  4 <-> 5,   5 <-> 6,   1 <-> 6,  
    3 <-> 7,   7 <-> 8,   8 <-> 9,  9 <-> 10, 10 <-> 11, 11 <-> 3,
    4 <-> 12, 12 <-> 13, 13 <-> 11
  }, 
    VertexLabels -> "Name"
]

{1,2,3,4,5,6}, {3,4,11,12,13},{3,7,8,9,10,11} are rings and we can extract them by using Teake's answer:

cycles = FindFundamentalCycles[graph];
rings = Sort @* VertexList @* Graph /@ cycles  

Edit 1

But the above solution doesn't always work as it might give non-chordless cycles. Consider the following example:

grapht = Graph[
{
  1 <-> 2, 1 <-> 3, 2 <-> 4, 4 <-> 5, 5 <-> 6, 4 <-> 6, 
  6 <-> 7, 3 <-> 5, 3 <-> 9, 5 <-> 8, 8 <-> 9
},
VertexLabels -> "Name"];

Rings (cycles) are:

cyclest = FindFundamentalCycles[grapht]; 
HighlightGraph[grapht, #] & /@ cyclest

But I need to get {4,5,6} as a ring not {1,2,3,4,5,6} since there is an edge in the latter. Is there any way to customize FindFundamentalCycles function to break the cycle into chordless cycles?

W Community crosspost

I am doing a research on networks which consists of polygons with different number of sides. I am trying to find all simple cycles in a network which are chordless. As an example, consider the following graph:

graph = Graph[
  {
    1 <-> 2,   2 <-> 3,   3 <-> 4,  4 <-> 5,   5 <-> 6,   1 <-> 6,  
    3 <-> 7,   7 <-> 8,   8 <-> 9,  9 <-> 10, 10 <-> 11, 11 <-> 3,
    4 <-> 12, 12 <-> 13, 13 <-> 11
  }, 
    VertexLabels -> "Name"
]

{1,2,3,4,5,6}, {3,4,11,12,13},{3,7,8,9,10,11} are rings and we can extract them by using:

cycles = FindFundamentalCycles[graph];
rings = Sort @* VertexList @* Graph /@ cycles  

But the above solution doesn't always work as it might give non-chordless cycles. Consider the following example:

grapht = Graph[
{
  1 <-> 2, 1 <-> 3, 2 <-> 4, 4 <-> 5, 5 <-> 6, 4 <-> 6, 
  6 <-> 7, 3 <-> 5, 3 <-> 9, 5 <-> 8, 8 <-> 9
},
VertexLabels -> "Name"];

Rings (cycles) are:

cyclest = FindFundamentalCycles[grapht]; 
HighlightGraph[grapht, #] & /@ cyclest

But I need to get {4,5,6} as a ring not {1,2,3,4,5,6} since there is an edge in the latter. Is there any way to filter out only chordless cycles?

W Community crosspost

Edit 2

It seems whenever I accept an answer, I come up with a counterexample.

Let's take this new graph:

g = Graph[{1 <-> 2, 1 <-> 3, 2 <-> 4, 4 <-> 5, 5 <-> 6, 4 <-> 6, 
 6 <-> 7, 3 <-> 5, 3 <-> 9, 5 <-> 8, 8 <-> 9, 6 <-> 8}, 
VertexLabels -> "Name"]

Using mrm's answer:

  cy = VertexList[Graph[#]] & /@ FindCycle[g, Infinity, All];
  Select[cy, IsomorphicGraphQ[CycleGraph[Length[#]], Subgraph[g, #]] &]

results in:

where the last one is not chordless.