Title :
A necessary and sufficient condition for any tree of a connected graph to be a DFS-tree of one of its 2-isomorphic graphs
Author :
Shinoda, Shoji ; Chen, Wai-Kai ; Yasuda, Tomoshige ; Kajitani, Yoji ; Mayda, W.
Author_Institution :
Dept. of Electr. Eng., Chuo Univ., Tokyo, Japan
Abstract :
It is shown that any tree of a connected graph G is a depth-first-search (DFS)-tree of one of its 2-isomorphic graphs if, and only if, G is a series-parallel graph, where two graphs are said to be 2-isomorphic if they have the same set of edges as well as the same set of circuits. Only nonseparable graphs are considered. A basic theorem on series-parallel graphs is given, and the main theorems are discussed
Keywords :
graph theory; trees (mathematics); 2-isomorphic graphs; DFS-tree; connected graph; depth first search tree; nonseparable graphs; series-parallel graph; Circuits; Graph theory; Sufficient conditions; Tree graphs;
Conference_Titel :
Circuits and Systems, 1990., IEEE International Symposium on
Conference_Location :
New Orleans, LA
DOI :
10.1109/ISCAS.1990.112602
