A family of symmetric graphs with complete quotients

Teng Fang¹ ; Xin Gui Fang¹ ; Binzhou Xia¹ ; Sanming Zhou²

¹Peking University
²The University of Melbourne

The electronic journal of combinatorics, Tome 23 (2016) no. 2

Résumé

A finite graph $\Gamma$ is $G$-symmetric if it admits $G$ as a group of automorphisms acting transitively on $V(\Gamma)$ and transitively on the set of ordered pairs of adjacent vertices of $\Gamma$. If $V(\Gamma)$ admits a nontrivial $G$-invariant partition ${\cal B}$ such that for blocks $B, C \in {\cal B}$ adjacent in the quotient graph $\Gamma_{{\cal B}}$ relative to ${\cal B}$, exactly one vertex of $B$ has no neighbour in $C$, then we say that $\Gamma$ is an almost multicover of $\Gamma_{{\cal B}}$. In this case there arises a natural incidence structure ${\cal D}(\Gamma, {\cal B})$ with point set ${\cal B}$. If in addition $\Gamma_{{\cal B}}$ is a complete graph, then ${\cal D}(\Gamma, {\cal B})$ is a $(G, 2)$-point-transitive and $G$-block-transitive $2$-$(|{\cal B}|, m+1, \lambda)$ design for some $m \geq 1$, and moreover either $\lambda=1$ or $\lambda=m+1$. In this paper we classify such graphs in the case when $\lambda = m+1$; this together with earlier classifications when $\lambda = 1$ gives a complete classification of almost multicovers of complete graphs.

Détail

DOI : 10.37236/5701

Classification : 05C25, 20B25, 05E05
Mots-clés : symmetric graph, arc-transitive graph, almost multicover