***** To join INSNA, visit http://www.insna.org ***** Tad, do you imply that a solution is known for k = 1? Isn't this NP? --Moses 2011/2/23 <[log in to unmask]>: > ***** 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. > _____________________________________________________________________ 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.