***** To join INSNA, visit http://www.insna.org *****
Dear Socnet Members
Let me address a question to those of you who have been watching
developments in GRAPH THEORY.
Is the following statement true?
'No nontrivial complete set collection of invariants has yet been found
for directed graphs’
Definitions
A (finite) DIRECTED GRAPH is a mathematical object of the form G=(X,R),
where X is a finite set (of points) and R is a binary relation in X.
Two digraphs G=(X,R) and G’=(X’,R’) are ISOMORPHIC if there exists a 1-1
mapping F of X onto X’ such that xRy if and only if F(x)R’F(y), for any
x,y in X.
A STRUCTURAL PARAMETER of a digraph is any mapping P which assigns a
numerical value to any digraph in such a way that P(G)=P(G’) if G and G’
are isomorphic.
A COMPLETE SET OF INVARIANTS is any finite collection P1,…,Pk of
structural parameters such that, for any two digraphs G and G’, the
equations P1(G)=P1(G’),…,Pk(G)=Pk(G’) imply that G and G’ are isomorphic.
For any n, let gn denote the number of equivalence classes of the
isomorphism relation in the set of digraphs with X={1,…,n}. The numbers
1,…,gn can be used as code symbols of equivalence classes. A 'trivial'
set of invariants is obtained by assigning to any G=(X,R) the number n of
points (n=|X| ) and an appropriate symbol from the range from 1 to gn.
Hence, by saying that a set of invariants is NONTRIVIAL I mean that the
values of P1,…,Pk for two n-point digraphs G and G’ can be computed
without prior knowledge of the list of isomorphism classes.
Tad Sozanski
www.cyf-kr.edu.pl/~ussozans/
_____________________________________________________________________
SOCNET is a service of INSNA, the professional association for social
network researchers (http://www.insna.org). To unsubscribe, send
an email message to [log in to unmask] containing the line
UNSUBSCRIBE SOCNET in the body of the message.
|