Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: graphy theory problem
Replies: 0

 dmallenby Posts: 1 Registered: 10/25/07
graphy theory problem
Posted: Oct 25, 2007 12:50 PM

Hi,

I'm sure this is stupidly simple and someone will be able to tell me the answer straight away. I'm trying to find the name of a type of subgraph, and a way of representing this formulaically if possible.

The graphs I am using are simple undirected graphs, whereby each node is of degree 1,2 or 3. For my work I break the graph into subgraphs, whereby each subgraph is a path such that the start/end nodes are of degree 1 or 3, and the rest are of degree 2.

For example, suppose we had the following graph:

1 - 2 - 3
|
4
|
5 - 6 - 7
Splitting this into the subgraphs mentioned would yield: [1-2-3],[1-4-5],[5-6-7]

So is there a term for such subgraphs, or at least a formula to show how they are derived? I have been unable to find one so far, but as I've said this seems a straightforward thing to do so would expect there is a term for it already!

Thanks