DocumentCode
2663746
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
fYear
1990
fDate
1-3 May 1990
Firstpage
2841
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Circuits and Systems, 1990., IEEE International Symposium on
Conference_Location
New Orleans, LA
Type
conf
DOI
10.1109/ISCAS.1990.112602
Filename
112602
Link To Document