How do I get a 2-3 subgraph or 3-4 subgraph? (Research question)

Revision en2, by YahiaSherif, 2022-06-24 16:20:49

Hi, I am writing my bachelor thesis and I came across a study which mentions finding a 2-3 subgraph and a 3-4 subgraph as one of its subtask but it doesn't mention an algorithm to do it but it just says that it is done using DFS.

I couldn't really find anything useful online solving these problems.

A 2-3 subgraph is a subgraph where each node has degree 2 or 3 in this subgraph (we remove edges which go to nodes outside the subgraph) and our task is to find a maximal 2-3 subgraph (it doesn't have to be maxmimum in terms of size just that we can't add another node to it). A 3-4 subgraph is just the same but with 3 and 4.

Can anyone help by describing an algorithm or linking an article/paper?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English YahiaSherif 2022-06-24 17:34:10 2 Tiny change: 'aph and a 3-4 subgrap' -> 'aph and a 2-4 subgrap'
en5 English YahiaSherif 2022-06-24 17:32:05 5
en4 English YahiaSherif 2022-06-24 16:32:40 0 (published)
en3 English YahiaSherif 2022-06-24 16:21:21 23 Tiny change: ' subgraph as o' -> ' subgraph of an undirected graph as o'
en2 English YahiaSherif 2022-06-24 16:20:49 1 Tiny change: 'se problem.\n\nA 2-3' -> 'se problems.\n\nA 2-3' (saved to drafts)
en1 English YahiaSherif 2022-06-24 16:20:18 772 Initial revision (published)