On k-connected-homogeneous graphs

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:173

Article

Devillers, Alice¹  Fawcett, Joanna B.²  Praeger, Cheryl E.¹  Zhou, Jin-Xin³ 

[1] Univ Western Australia, Ctr Math Symmetry & Computat, Dept Math & Stat, Crawley, WA 6009, Australia

[2] Imperial Coll London, Dept Math, South Kensington Campus, London SW7 2AZ, England

[3] Beijing Jiaotong Univ, Dept Math, Beijing 100044, Peoples R China

关键词: Locally finite graph;    Homogeneous;    k-connected-homogeneous;    s-arc-transitive;   

DOI  :  10.1016/j.jcta.2020.105234

来源: Elsevier

【 摘 要 】

A graph Gis k-connected-homogeneous (k-CH) if kis a positive integer and any isomorphism between connected induced subgraphs of order at most kextends to an automorphism of G, and connected-homogeneous (CH) if this property holds for all k. Locally finite, locally connected graphs often fail to be 4-CH because of a combinatorial obstruction called the unique xproperty; we prove that this property holds for locally strongly regular graphs under various purely combinatorial assumptions. We then classify the locally finite, locally connected 4-CH graphs. We also classify the locally finite, locally disconnected 4-CH graphs containing 3-cycles and induced 4-cycles, and prove that, with the possible exception of locally disconnected graphs containing 3-cycles but no induced 4-cycles, every finite 7-CH graph is CH. (c) 2020 Elsevier Inc. All rights reserved.

【 授权许可】

Free