We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On Small World Semiplanes with Generalised Schubert Cells.
- Authors
Vyacheslav Futorny; Vasyl Ustimenko
- Abstract
Abstract  The well known âreal-life examplesâ of small world graphs, including the graph of binary relation: âtwo persons on the earth know each otherâ contains cliques, so they have cycles of order 3 and 4. Some problems of Computer Science require explicit construction of regular algebraic graphs with small diameter but without small cycles. The well known examples here are generalised polygons, which are small world algebraic graphs i.e. graphs with the diameter dâ¤clogâ kâ1(v), where v is order, k is the degree and c is the independent constant, semiplanes (regular bipartite graphs without cycles of order 4); graphs that can be homomorphically mapped onto the ordinary polygons. The problem of the existence of regular graphs satisfying these conditions with the degree â¥k and the diameter â¥d for each pair kâ¥3 and dâ¥3 is addressed in the paper. This problem is positively solved via the explicit construction. Generalised Schubert cells are defined in the spirit of Gelfand-Macpherson theorem for the Grassmanian. Constructed graph, induced on the generalised largest Schubert cells, is isomorphic to the well-known Wengerâs graph. We prove that the family of edge-transitive q-regular Wenger graphs of order 2q n , where integer nâ¥2 and q is prime power, qâ¥n, q>2 is a family of small world semiplanes. We observe the applications of some classes of small world graphs without small cycles to Cryptography and Coding Theory.
- Subjects
ALGEBRAIC geometry; PATHS &; cycles in graph theory; COMPUTATIONAL mathematics; POLYGONS
- Publication
Acta Applicandae Mathematicae, 2007, Vol 98, Issue 1, p47
- ISSN
0167-8019
- Publication type
Article
- DOI
10.1007/s10440-007-9144-8