Regularity and transitivity in graphs

Shawe-Taylor, John Stewart


Shawe-Taylor, John Stewart (1986) Regularity and transitivity in graphs.

Our Full Text Deposits

Full text access: Open

10096267.pdf - 12.88 MB


Graphs with high regularity and transitivity conditions are studied. The first graphs considered are graphs where each vertex has an intersection array (possibly differing from that of other vertices). These graphs are called distance-regularised and are shown to be distance-regular or bipartite with each bipartition having the same intersection array. The latter graphs are called distance-biregular. This leads to the study of distance-biregular graphs. The derived graphs of a distance-biregular graph are shown to be distance-regular and the notion of feasibility for a distance-regular graph is extended to the biregular case. The study of the intersection arrays of distance-biregular graphs is concluded with a bound on the diameter in terms of the girth and valencies. Special classes of distance-biregular graphs are also studied. Distance-biregular graphs with 2-valent vertices are shown to be the subdivision graphs of cages. Distance-biregular graphs with one derived graph complete and the other strongly-regular are characterised according to the minimum eigenvalue of the strongly-regular graph. Distance-biregular graphs with prescribed derived graph are classified in cases where the derived graph is from some classes of classical distance-regular graphs. A graph theoretic proof of part of the Praeger, Saxl and Yokoyama theorem is given. Finally imprimitivity in distance-biregular graphs is studied and the Praeger, Saxl and Yokoyama theorem is used to show that primitive non-regular distance-bitransitive graphs have almost simple automorphism groups. Many examples of distance-biregular and distance-bitransitive graphs are given.

Information about this Version

This is a Accepted version
This version's date is: 1986
This item is not peer reviewed

Link to this Version

Item TypeThesis (Doctoral)
TitleRegularity and transitivity in graphs
AuthorsShawe-Taylor, John Stewart
Uncontrolled KeywordsMathematics; Pure Sciences; Distance-Biregular Graphs; Distance-Biregular Graphs; Graphs; Regularity; Transitivity



Deposited by David Morgan (UBYL020) on 31-Jan-2017 in Royal Holloway Research Online.Last modified on 31-Jan-2017


Digitised in partnership with ProQuest, 2015-2016. Institution: University of London, Royal Holloway and Bedford New College (United Kingdom).