Construction of some countable 1-arc-transitive bipartite graphs

Robert Gray, John K. Truss

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

We generalize earlier work which gave a method of construction for bipartite graphs which are obtained as the set of maximal or minimal elements of a certain cycle-free partial order. The method is extended here to produce a 1-arc-transitive bipartite graph in a ‘free’ way, starting with any partial order with greatest and least element and with instructions on its points about how they will ramify in the extension. A key feature of our work is the interplay between properties of the initial partial order, the extended partial order, and the bipartite graph which results. We also extend the earlier work by giving a complete characterization of all 2-CS-transitive cycle-free partial orders. In addition, we discuss the completeness of the constructed partial orders, in the sense of Dedekind and MacNeille, and remark that the bipartite graph constructed can only be 2-arc-transitive in the cycle-free case.
Original languageEnglish
Pages (from-to)6392-6405
Number of pages14
JournalDiscrete Mathematics
Volume308
Issue number24
DOIs
Publication statusPublished - 2008

Cite this