Premium
Path‐isomorphic networks
Author(s) -
Hartvigsen David
Publication year - 1990
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190140611
Subject(s) - mathematics , combinatorics , bijection , arc (geometry) , path (computing) , isomorphism (crystallography) , discrete mathematics , block (permutation group theory) , directed acyclic graph , class (philosophy) , computer science , chemistry , geometry , artificial intelligence , crystal structure , crystallography , programming language
Abstract Two source‐sink (directed) networks are called path‐isomorphic if there exists a bijection π between their arc sets that preserves (simple) source‐sink directed paths. Although path‐isomorphic networks need not be isomorphic (they need not even have the same number of nodes), we show that several properties are preserved. For example, suppose N and N′ are path‐isomorphic. Then, N is acyclic if and only if N′ is acyclic. B is the arc set of block of N if and only if π( B ) is the arc set of a block of N′ . Also, D is the arc set of a dicomponent of N if and only if π( D ) is the arc set of a dicomponent of N′. In addition, we prove a dipath version of Whitney's well‐known 2‐isomorphism theorem for a special class of networks, which includes the acyclic networks.