COVERS AND PSEUDOCOVERS OF SYMMETRIC GRAPHS CAI HENG LI AND YAN ZHOU ZHU Abstract. We introduce the concept of pseudocover which is a counterpart of cover for

2025-04-27 0 0 424.87KB 15 页 10玖币

侵权投诉

COVERS AND PSEUDOCOVERS OF SYMMETRIC GRAPHS

CAI HENG LI AND YAN ZHOU ZHU

Abstract. We introduce the concept of pseudocover, which is a counterpart of cover, for

symmetric graphs. The only known example of pseudocovers of symmetric graphs so far

was given by Praeger, Zhou and the ﬁrst-named author a decade ago, which seems technical

and hard to extend to obtain more examples. In this paper, we present a criterion for a

symmetric extender of a symmetric graph to be a pseudocover, and then apply it to produce

various examples of pseudocovers, including (1) with a single exception, each Praeger-Xu’s

graph is a pseudocover of a wreath graph; (2) each connected tetravalent symmetric graph

with vertex stabilizer of size divisible by 32 has connected pseudocovers.

1. Introduction

Denote by Γ= (V, E) a ﬁnite undirected simple graph with vertex set Vand edge set E.

The vertex set Vis sometime written as VΓ. An arc of Γis an ordered pair of adjacent

vertices, and an edge corresponds to two arcs. A graph Γis called symmetric if its arcs are

equivalent under the automorphism group AutΓ. In particular, we say Γis G-symmetric for

if G⩽Aut(Γ) is transitive on the arc set. A symmetric graph is also called an arc-transitive

graph. The study of symmetric graphs is one of the main topics in algebraic graph theory,

refer to [1, 5] for references.

For a graph Γ= (V, E), a group of automorphisms G⩽AutΓis a permutation group on

the vertex set V. If Gis further transitive on arcs of Γ, then Gis a transitive permutation

group on V. Studying symmetric graphs is thus naturally associated with studying permu-

tation groups G. In the case where Gis primitive on V, namely, Γis G-vertex-primitive,

the well-known O’Nan-Scott Theorem [8] of permutation group theory and the theory of

ﬁnite simple groups provide powerful tools for the study of symmetric graphs which are

vertex-primitive, see [6, 12].

On the other hand, assume that a G-symmetric graph Γ= (V, E) is not G-vertex-

primitive, namely, Gis imprimitive on V. Let Bbe a non-trivial block system for Gacting

on V, that is, 1 <|B| <|V|. Then Ginduces a transitive permutation group GB, and

G/G(B)∼

=GB, which is called a quotient permutation group of Gon V, where G(B)is the

kernel of Gacting on B. If G(B)= 1, then G∼

=GBis faithful on B. In the quotient action,

the point in Bcorresponding to the block Bcontaining βis denoted by β, so that β∈B=β.

Clearly, one block βcorresponds to |B|choices for β. Corresponding to a quotient group, a

G-symmetric graph Γhas a quotient graph ΓB(with respect to G), which has vertex set B

Key words and phrases. Symmetric graph, Cover, Pseudocover, Praeger-Xu’s graph, Tetravalent graph.

arXiv:2210.02679v2 [math.CO] 7 Dec 2024

2 CAI HENG LI AND YAN ZHOU ZHU

such that for any two vertices α, β ∈ B,

(α, β) is an arc of ΓBif and only if (α, β) is an arc of Γfor some α∈αand β∈β.

We usually call the original graph Γan extender of the quotient graph ΓB, and call the block

αthe image of α.

The quotient graph ΓBis a smaller symmetric graph than the original graph Γin the sense

that |VΓB|<|VΓ|. Naturally, one may wish to understand Γthrough characterizing the

smaller graph ΓBand the relation between Γand ΓB. For two blocks αand βin Bwhich are

adjacent vertices in ΓB, let Γ[α, β] be the subgraph of Γinduced on the subset of vertices

α∪βof VΓ. If Γis G-symmetric, then the induced subgraph Γ[α, β] is independent of the

choice of (α, β). The structure of Γ[α, β] and the valencies val(Γ) and val(ΓB) are obviously

important parameters for understanding the relation between Γand ΓB, which leads to the

following concepts.

Deﬁnition 1.1. Let Γbe a G-symmetric graph, and ΓBa quotient graph of Γ, where Bis

a block system of Gacting on VΓ. Pick an arc (α, β) of Γ.

(A) If the induced subgraph Γ[α, β] is a regular graph, then Γis called a multicover of ΓB;

so that val(Γ) is divisible by val(ΓB).

(B) If the induced subgraph Γ[α, β] is a perfect matching, then Γis called a cover of ΓB; so

that val(Γ) = val(ΓB).

Constructing and characterizing symmetric covers of given symmetric graphs is an im-

portant approach for studying symmetric graphs, refer to [2, 3, 4]. As noticed above, if a

symmetric graph Γis a cover of ΓB, then Γand ΓBhave the same valency. Whether the

converse statement is true or not had been an open problem until the ﬁrst example of pseu-

docovers was discovered by Praeger, Zhou and the ﬁrst-named author in [7], see Example 5.7.

The presentation given in [7, Construction 3.5] seems technical and hard to extend to obtain

more examples.

Convention: For a G-symmetric graph Γwhere G⩽AutΓ, the group Ginduces an

arc-transitive action on each quotient graph ΓB. However, Gis not necessarily faithful on

the vertex set VΓB. For convenience, we shall also call ΓBaG-symmetric graph, and say Γ

is a G-symmetric extender of ΓBif Bis a block system of G. With this convention, Gαis a

subgroup of Gαand acts on ΓB(α) naturally, where Gαis the subgroup of Gstabilizes the

subset α.

We ﬁrst present a criterion for deciding an extender to be a pseudocover.

Theorem 1.2. Let Γ be a G-symmetric extender of ΓBsuch that val(Γ) = val(ΓB). Let

(α, β)be an arc of Γ , and (α, β)the corresponding image in ΓB. Then the followings are

equivalent:

(a) Γ is a G-symmetric pseudocover of ΓB;

(b) Gαis an intransitive subgroup of Gαon ΓB(α);

COVERS AND PSEUDOCOVERS OF SYMMETRIC GRAPHS 3

(d) Gαβ ,Gαβ and Gαβ are pairwise diﬀerent.

This theorem explores a key property of pseudocovers, and provides us with a tool for

constructing covers and pseudocovers of symmetric graphs, which we will apply to study

several important families of symmetric graphs.

In 1989, Praeger and Xu [13] explicitly characterized the class of G-symmetric graphs of

order rpsand valency 2pwith pprime and r⩾3 such that Ghas an elementary abelian

normal p-subgroup that is non-semiregular on vertices, which we call Praeger-Xu’s graphs.

See Deﬁnition 4.1 for a deﬁnition of these graphs in terms of coset graphs. We remark that

the Praeger-Xu’s graph with s= 1, namely the graph is of order rp, is isomorphic to the

so-called wreath graph W(r, p) = Cr[Kp].

The next result gives a characterization of Praeger-Xu’s graphs in the language of pseu-

docovers.

Corollary 1.3. With a single exception, each Praeger-Xu’s graph is a symmetric pseudocover

of W(r, p), for some integer r⩾3and prime p.

The ﬁnal theorem of this paper shows that ‘most’ tetravalent symmetric graphs have

connected pseudocovers.

Theorem 1.4. Each connected tetravalent G-symmetric graph with vertex stabilizer of order

divisible by 32 has a connected G-symmetric pseudocover.

2. Coset graphs and extenders

A well-known important notion for studying symmetric graphs is the coset graph repre-

sentation, which we describe below.

Let Γ= (V, E) be a G-symmetric graph, and ﬁx an edge {α, β} ∈ E. Then the vertex

set Vmay be identiﬁed with the set of right cosets [G:Gα] = {Gαx|x∈G}, and then

the action of Gon Vis equivalent to the action of Gon [G:Gα] by right multiplication of

elements in G. Further, since Gis symmetric on Γ, there exists an element g∈Gsuch that

(α, β)g= (β, α). Clearly, g2∈Gαand gcan be chosen as a 2-element, namely, an element

of order 2mfor some integer m. Then, in terms of cosets, the right coset Gαxcorresponds

to the vertex αx∈V. In particular, Gαand Gαgcorrespond to the vertices αand β,

respectively. Thus the neighborhood Γ(α) = {Gαgh |h∈Gα}, consisting right cosets of Gα

contained in the double coset GαgGα. It implies that Gαxand Gαyare adjacent if and only

if yx−1∈GαgGα.

Conversely, for an abstract group G, a subgroup H < G and an element g∈Gsuch

that g2∈H, one can deﬁne a graph Γ= (V, E), called a coset graph and denoted by

Cos(G, H, HgH), where

V= [G:H],

E={Hx, Hy} | yx−1∈HgH.

We notice that, with this deﬁnition, Gis not necessarily faithful on the vertex set V= [G:

H]. The quotient permutation group GVis a subgroup of AutΓby the coset action of Gon

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

COVERSANDPSEUDOCOVERSOFSYMMETRICGRAPHSCAIHENGLIANDYANZHOUZHUAbstract.Weintroducetheconceptofpseudocover,whichisacounterpartofcover,forsymmetricgraphs.TheonlyknownexampleofpseudocoversofsymmetricgraphssofarwasgivenbyPraeger,Zhouandthefirst-namedauthoradecadeago,whichseemstechnicalandhardtoextendtoobt...

展开>> 收起<<

COVERS AND PSEUDOCOVERS OF SYMMETRIC GRAPHS CAI HENG LI AND YAN ZHOU ZHU Abstract. We introduce the concept of pseudocover which is a counterpart of cover for.pdf

共15页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

COVERS AND PSEUDOCOVERS OF SYMMETRIC GRAPHS CAI HENG LI AND YAN ZHOU ZHU Abstract. We introduce the concept of pseudocover which is a counterpart of cover for

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: