Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



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: [123],[145],[567]
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



