Local 2-geodesic transitivity and clique graphs

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:120

Article

Devillers, Alice¹  Jin, Wei¹  Li, Cai Heng¹  Praeger, Cheryl E.¹ 

[1] Univ Western Australia, Sch Math & Stat, Crawley, WA 6009, Australia

关键词: Local 2-geodesic transitivity;    Clique graph;    Partial linear space;   

DOI  :  10.1016/j.jcta.2012.10.004

来源: Elsevier

【 摘 要 】

A 2-geodesic in a graph is a vertex triple (u, v, w) such that v is adjacent to both u and w and u, w are not adjacent. We study non-complete graphs Gamma in which, for each vertex u, all 2-geodesics with initial vertex u are equivalent under the subgroup of graph automorphisms fixing u. We call such graphs locally 2-geodesic transitive, and show that the subgraph [Gamma(u)] induced on the set of vertices of Gamma adjacent to u is either (i) a connected graph of diameter 2. or (ii) a union mK(r) of m >= 2 copies of a complete graph K-r with r >= 1. This suggests studying locally 2-geodesic transitive graphs according to the structure of the subgraphs [Gamma(u)]. We investigate the family F(m, r) of connected graphs r such that [Gamma(u)] congruent to mK(r) for each vertex u, and for fixed m >= 2, r >= 1. We show that each Gamma is an element of F(m, r) is the point graph of a partial linear space S of order (m, r + 1) which has no triangles (and 2-geodesic transitivity of Gamma corresponds to natural strong symmetry properties of S). Conversely, each S with these properties has point graph in F(m,r), and a natural duality on partial linear spaces induces a bijection F(m, r) -> F(r + 1, m - 1). (C) 2012 Elsevier Inc. All rights reserved.

【 授权许可】

Free