# Graphs that cause DFS and BFS to process nodes in the exact same order

For some graphs, DFS and BFS search algorithms process nodes in the exact same order provided that they both start at the same node. Two examples are graphs that are paths and graphs that are star-shaped (trees of depth $1$ with an arbitrary number of children). Is there some way for categorizing graphs that satisfy this property?

-
Note that in both cases this only works if you start at some specific node. If you pick a central node in a long path, for example, you will get back different orderings from DFS and BFS. –  templatetypedef Aug 20 '12 at 4:49
Are there any other interesting possibilities than a star or a path? At first glance it would seem that if you had a vertex with both a sibling and a child then you immediately get different traversals, so either no vertex has children (apart from the root) and you get a star, or no vertex has a sibling and you get a path. I guess a clique also works, but it has both the star and path embedded. –  Luke Mathieson Aug 20 '12 at 8:38
@LukeMathieson I'm thinking of a star with the rightmost child being the root of another star. I guess that would work as well. We can even make a general statement: if $G = (V,E)$ satisfies the property when the search starts at node v∈V, then so does a star whose rightmost child $= v$. Even better, if $G_1$ and $G_2$ satisfy the property and node $v_1$ is the last one processed in $G_1$ and $v_2$ is where the search starts in $G_2$, then adding the bridge edge $(v_1, v_2)$ creates a graph that satisfies the property. Replacing $v_1$ by $v_2$ also works I think. –  saadtaame Aug 20 '12 at 9:51
Good point, so there's some sort of right-recursive composition where you could identify the right leaf of the first graph with the root of the second. –  Luke Mathieson Aug 20 '12 at 11:53
@LukeMathieson It looks like you can fix the case where a node $v$ has a sibling and a child by adding an edge between that child and the parent of $v$. Here is my proposition: Given a graph $G=(V,E)$. $\forall x \in V$, if $\exists y,z,w \in V$ such that $(y,x),(z,y),(x,w) \in E$, then $(x,z) \in E \implies$ the property holds for $G$. The next step is to prove or disprove this proposition. –  saadtaame Aug 20 '12 at 17:48