摘要
A graph has the unique path property UPPn if there is a unique path of length n between any ordered pair of nodes. This paper reiterates Royle and MacKay＇s technique for constructing orderly algorithms. We wish to use this technique to enumerate all UPP2 graphs of small orders 3^2 and 4^2. We attempt to use the direct graph formalism and find that the algorithm is inefficient. We introduce a generalised problem and derive algebraic and combinatoric structures with appropriate structure. Then we are able to design an orderly algorithm to determine all UPP2 graphs of order 3^2, which runs fast enough. We hope to be able to determine the UPP2 graphs of order 4^2 in the near future.
A graph has the unique path property UPPn if there is a unique path of length n between any ordered pair of nodes. This paper reiterates Royle and MacKay＇s technique for constructing orderly algorithms. We wish to use this technique to enumerate all UPP2 graphs of small orders 3^2 and 4^2. We attempt to use the direct graph formalism and find that the algorithm is inefficient. We introduce a generalised problem and derive algebraic and combinatoric structures with appropriate structure. Then we are able to design an orderly algorithm to determine all UPP2 graphs of order 3^2, which runs fast enough. We hope to be able to determine the UPP2 graphs of order 4^2 in the near future.
基金
supported in part by Project P15691 from the Austrian Federal FWF,the national science finding body,as well as by several ongoing grants from Stadt Linz,Land Obersterreich and the Austrian Federal BKA.Kunst
