Orderly Algorithm to Enumerate Central Groupoids and Their Graphs
查看参考文献28篇
|
文摘
|
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 32 and 42. 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 32, which runs fast enough. We hope to be able to determine the UPP2 graphs of order 42 in the near future. |
|
来源
|
Acta Mathematica Sinica. English Series
,2007,23(2):249-264 【核心库】
|
|
DOI
|
10.1007/s10114-005-0775-2
|
|
关键词
|
orderly algorithms
;
paths in directed graphs
;
enumeration
|
|
地址
|
Time's Up Research Department and Department of Mathematics, Johannes–Kepler University, Linz
|
|
语种
|
英文 |
|
ISSN
|
1439-8516 |
|
学科
|
数学 |
|
基金
|
奥地利科学基金会（FWF）资助
;
the national science finding bodyas well as by several ongoing grants from Stadt Linz, Land Ober¨osterreich
|
|
文献收藏号
|
CSCD:3144350
|
参考文献 共
28
共2页
|
|
1.
The GAP Group.
Algorithms, and Programming, Version 4. 3,2002
|
CSCD被引
1
次
|
|
|
|
|
2.
Soicher L H. GRAPE:a system for computing with graphs and groups.
Groups and Computation, volume 11 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science,1993:287-291
|
CSCD被引
1
次
|
|
|
|
|
3.
McKay B D.
Nauty user’s guide, Technical report,1990
|
CSCD被引
1
次
|
|
|
|
|
4.
Read R C. Every one a winner.
Annals of Discrete Mathematics,1978,2:107-120
|
CSCD被引
1
次
|
|
|
|
|
5.
McKay B D. Isomorph-free exhaustive generation.
J. on Algorithms,1998,26:306-324
|
CSCD被引
4
次
|
|
|
|
|
6.
Royle. Gordon, F. An orderly algorithm and some applications in finite geometry.
Discrete Mathematics,1998,185:105-115
|
CSCD被引
1
次
|
|
|
|
|
7.
Evans T. Products of points-some simple algebras and their identities.
Am. Math. Monthly,1967:362-372
|
CSCD被引
1
次
|
|
|
|
|
8.
McLean D. Idempotent semigroups.
American Math Monthly,1954,64:110-113
|
CSCD被引
1
次
|
|
|
|
|
9.
Donald E. Knuth:Notes on central groupoids.
Journal of Combinatorial Theory,1970,8:376-390
|
CSCD被引
1
次
|
|
|
|
|
10.
Hoffman A J. Research problem 2-11.
J. Combinatorial Theory,1967,2:393
|
CSCD被引
3
次
|
|
|
|
|
11.
Leslie E. Shader:On the existence of finite central groupoids of all possible ranks.
J. Combinat. Theory, Ser. A,1974,16:221-229
|
CSCD被引
1
次
|
|
|
|
|
12.
Fiol M A. Digraphs with walks of equal lengths between vertices.
Graph Theory with Applications to Algorithms and Computer Science,1985:313-322
|
CSCD被引
1
次
|
|
|
|
|
13.
Mendelsohn N S. Directed graphs with the unique path property.
Combinatorial Theory and its Applications, volume 4,1970:783-799
|
CSCD被引
1
次
|
|
|
|
|
14.
Lam C W H. On rational circulants satisfying A m=dI+λJ. Lin.
Alg. App.,1975,12:139-150
|
CSCD被引
1
次
|
|
|
|
|
15.
Lam C W H. On some solutions of A m=dI+λJ.
J. Comb. Theory Ser. A,1977,29:140-147
|
CSCD被引
1
次
|
|
|
|
|
16.
Lam C W H. Directed graphs with unique paths of fixed lengths.
Journal of Comb. Theory B,1978,24:331-337
|
CSCD被引
2
次
|
|
|
|
|
17.
Ma S L. On rational circulants satisfying A m=dI+λJ.
Lin. Alg. App.,1984,62:155-161
|
CSCD被引
1
次
|
|
|
|
|
18.
Ryser H J. A generalisation of the matrix equation A 2=J.
Lin. Alg. App.,1970,3:451-460
|
CSCD被引
2
次
|
|
|
|
|
19.
Wang K. On the matrix equation A m=λJ.
J. Comb. Theory, Ser. A,1980,29:134-141
|
CSCD被引
1
次
|
|
|
|
|
20.
Wang K. On the g-circulant solutions to the matrix equation A m=λJ.
J. Comb. Theory, Ser. A,1982,33:287-296
|
CSCD被引
2
次
|
|
|
|
|
了解气象卫星更多信息，请访问