A construction of an infinite family of 2-arc transitive polygonal graphs of arbitrary even girth

DOI 10.1007/s10801-010-0235-7

A construction of an infinite family of 2-arc transitive polygonal graphs of arbitrary even girth

Eric Swartz

Received: 24 June 2009 / Accepted: 26 April 2010 / Published online: 18 May 2010

© Springer Science+Business Media, LLC 2010

Abstract A near-polygonal graph is a graphΓ which has a setC ofm-cycles for some positive integermsuch that each 2-path ofΓ is contained in exactly one cy- cle inC. If mis the girth of Γ, then the graph is called polygonal. We provide a construction of an infinite family of polygonal graphs of arbitrary even girth with 2-arc transitive automorphism groups, showing that there are infinitely many 2-arc transitive polygonal graphs of every girth.

Keywords Algebraic graph theory·Polygonal graph·2-arc transitive graph

1 Introduction

LetΓ be a graph. For a positive integerl, anl-walk of Γ is a sequence of vertices (α₀, α₁, . . . , α_l)such that α_i is adjacent to α_i+1 for 0≤i≤l−1. If in addition α_i−1=α_i+1for 1≤i≤l−1,then anl-walk is called anl-arc; while if further all the α_i are distinct, then thel-arc is called anl-dipath (directed path). The identification of anl-dipath(α₀, α₁, . . . , α_l)and its reverse(α_l, . . . , α₁, α₀)is called anl-path, and denoted by[α0, α1, . . . , αl].An m-cycle is an (m−1)-path[α1, . . . , αm]such thatαm

is adjacent toα1.

We callΓ a near-polygonal graph if there exists a numbermand a collectionCof m-cycles inΓ such that each 2-path ofΓ is contained in exactly one cycle inC.Ifm is the girthg(Γ )ofΓ, then the graph is called polygonal. The notions of polygonal and near-polygonal graphs were invented by Perkel (see, for example, [2]).

Before [4], the only examples of 2-arc transitive polygonal graphs with arbitrarily large valency had girth no larger than seven, and the 2-arc transitive polygonal graph

E. Swartz (

Department of Mathematics, The Ohio State University, Columbus, OH 43210, USA e-mail:[email protected]

with largest girth had valency five and girth twenty-three (in fact, even with no restric- tions on the automorphism group, there were no examples of polygonal graphs with odd girth greater than twenty-three) [3]. In [4] infinite families of polygonal graphs of arbitrary odd girth were constructed.

The main purpose of this paper is to construct 2-arc transitive polygonal graphs of arbitrarily large valency and girth. We will prove the following results.

Theorem 1.1 There are 2-arc transitive polygonal graphs of arbitrarily large valency and girthmfor all evenm≥4.

Corollary 1.2 There are infinitely many 2-arc transitive polygonal graphs of girth mfor allm≥3,and there are 2-arc transitive polygonal graphs of arbitrarily large valency for eachm.

2 Notation and preliminary results

The construction in this paper is a generalization of that in [1] and so relies heavily upon its notation and results. As in [1], an(l, m)-path-cycle cover of a graphΓ is a setC ofm-cycles such that eachl-path ofΓ is covered by at least one cycle inC;

sometimes an(l, m)-path-cycle cover is simply called an(l, m)-cover. If in addition everyl-path ofΓ lies in a constant numberλof cycles ofC, thenCis called a regular λ-(l, m)-cover, or simply called aλ-(l, m)-cover. Hence near-polygonal graphs are the graphs that have a 1-(2,m)-cover for somem.

For a graphΓ and a groupG≤Aut(Γ ),an(l, m)-coverCis called G-symmetrical ifC= {C1, C2, . . . , Cn}is such that

(i) The restrictionG|Ci ofGto eachC_i contains all rotations ofC_i. (ii) Ginduces a transitive action onC.

There are two possibilities forG|Ci to contain all rotations ofC_i, namelyG|Ci ∼= ZmorG|C_i ∼=D2m.The corresponding symmetrical covers will be calledG-rotary orG-dihedral, respectively. For a positive integer l, a graphΓ is called(G, l)-arc transitive,(G, l)-dipath transitive, or(G, l)-path transitive ifGacts transitively onl- arcs,l-dipaths, orl-paths ofΓ, respectively. In the case of dipath and path transitivity, we also require thatl-dipaths orl-paths exist inΓ ,respectively.

We now present the basis for the construction of near-polygonal graphs in [1].

Lemma 2.1 [1, Lemma 1.1] LetΓ be a regular graph of valency at least three, let G≤Aut(Γ ),and letl≥1 be an integer. Then (a)⇒(b)⇒(c)⇒(d) holds for the following four statements (a)–(d).

(a) Γ has aG-dihedral(l, m)-cover for somem≥3.

(b) Γ is(G, l)-dipath transitive.

(c) Γ has aG-rotary(l, m)-cover for somem≥3.

(d) Γ is(G, l)-path transitive.

Moreover, ifΓ has aG-dihedral(l, m)-coverCandGacts sharply transitively on thel-dipaths inΓ, thenCis a 1-(l, m)-cover.

We will use Lemma2.1in conjunction with the following method for construction.

Construction 2.2 [1, Construction 1.1] Let(α0, . . . , αl)and (α1, . . . , αl, αl+1) be l-dipaths in a graphΓ (allowing thatα0=α_l+1), letG≤Aut(Γ ),and suppose that there existsg∈Gsuch thatα^g_i =α_i+1for 0≤i≤l.LetCbe the cycle generated by the verticesα₀^g,and letC=C^G.

We shall refer to the method described in Construction2.2as spinning anl-dipath.

In order to apply Lemma2.1, we need to ensure that a target groupGoccurs as a group of automorphisms of some graphΓ .That goal can be achieved by definingΓ as a coset graph (also called orbital graph), as described below.

For a group G and a subgroup H < G, denote by [G:H] the set of right cosets ofH inG. For an element g∈G\H withg²∈H, the coset graph Γ :=

Cos(G, H, H gH )is defined as the graph with vertex set[G:H]such that two ver- ticesH x andH y are adjacent if and only ifyx⁻¹∈H gH.Observe that from the conditiong²∈H it follows thatH gH=H g⁻¹H andH x andH y are adjacent if and only ifH yandH xare adjacent, implying thatΓ is undirected. Denote byαthe vertexH of Γ and byβ the vertex α^g=H g.Note thatβ^g=α^g2=α, Gα =H, G_β=H^g,andG_αβ=H∩H^g.The neighbor setN_Γ(α)ofαconsists of the cosets inH gH, and the valency ofαis the index|G_α:G_αβ|.

For constructing near-polygonal graphs as in [1], we want to spin a 2-dipath (γ , α, β).The spinning element can be described easily in terms of the coset graph.

Lemma 2.3 [1, Lemma 2.3] For a coset graphΓ =Cos(G, H, H gH )withg²∈H, letα=Handβ=α^g.Then an elementf ∈Gmapsαtoβif and only iff ∈(Gα)g.

Furthermore, for f ∈G such thatα^f =β, we have thatβ =α^f−1 if and only if f∈(G_α)g\(G_αβ)g.

Finally, we will use the following well-known lemma as stated in [1].

Lemma 2.4 [1, Lemma 2.4] Let Γ be a graph, and let G≤Aut(Γ ) be transitive on the vertex set of Γ . Then Γ is (G,2)-dipath transitive if and only if G_α acts 2-transitively on NΓ(α); furthermore, Γ is sharply (G,2)-dipath transitive if and only ifG_α acts sharply 2-transitively onN_Γ(α).

3 A family of polygonal graphs with cycles of a fixed even length

We will use essentially the same construction as in [4], where a family of polygonal graphs with cycles of a fixed odd length was produced. Letm=2k+2, k∈N.

We define G to be the direct product of k copies of PGL(2, q), where q is a prime power, i.e.,G:=_k

i=1PGL(2, q). The elements of PGL(2, q) can be iden- tified with equivalence classes of 2×2 invertible matrices over the field GF(q), with two matrices equivalent if and only if they are scalar multiples of each other.

With a slight abuse of notation, we shall write that the matrices themselves are ele- ments of PGL(2, q), and that the elements ofGarek-tuples of matrices. We iden- tify H∼=AGL(1, q) with the set of (equivalence classes of) lower triangular ma- trices _a0

b c

:a, b, c∈GF(q), ac=0

and define H:=Diag(_k

i=1AGL(1, q))= {(h, h, . . . , h):h∈H} ≤G.

Fora∈GF(q),letp(a):=_{1 0}

a1

∈H andp(a):=(p(a), p(a), . . . , p(a))∈H . Moreover, ifa=0, then letd(a):=_a0

0 1

∈Handd(a):=(d(a), d(a), . . . , d(a))∈ H .LetP = {p(a):a∈GF(q)}, P = {p(a):a∈GF(q)}, D= {d(a):a∈GF(q)^∗}, andD= {d(a):a∈GF(q)^∗}.ThenH=P D, H=P D, PH,andP H .

Fory ∈GF(q)^∗, letg(y)= _{0 y}

−1 0

. Then, forg=g(y₁, y₂, . . . , y_k):=(g(y₁), g(y₂), . . . , g(y_k))∈G, we haveg²=1∈H ,so we can define the coset graphΓ = Γ (y1, y2, . . . , yk):=Cos(G, H , H gH ).Letαdenote the vertexH, and letβdenote the vertexH g.First we determine the number of vertices, the valency, and bound the number of components ofΓ .The number of vertices is

G:H= |G|/H=q^k−1(q−1)^k−1(q+1)^k.

For anyd∈D, we haved^g=d⁻¹,soGαβ=H∩H^g≥D.SinceDis a maximal subgroup ofH ,we must have equality here, and so the valency ofΓ is

|G_α:G_αβ| =H:D=q.

For a vertex δ of Γ , let W^(r)(δ) denote the set of vertices reachable by an r-long walk from δ. Then we have the following, which has the same proof as [1, Lemma 3.1]:

Lemma 3.1 W^(r)(α)=H gP gP· · ·gP(r iterations ofgP ).

Moreover, we have the following results from [4]:

Lemma 3.2 [4, Lemma 3.2] Lety₁, y₂, . . . , y_kbe distinct elements of GF(q)^∗.Then Γ has at most 2^k−1components.

Lemma 3.3 [4, Lemma 3.3] For ally₁, y₂, . . . , y_k∈GF(q)^∗,the graphΓ is near- polygonal.

Lemma 3.4 [4, Lemma 3.5] Letq ≡ ±1 (modm), and letζ =ζm be a primitive mth root of unity in GF(q²).Then, ify_i:=ζⁱ+ζ^m−i+2∈GF(q)^∗for 1≤i≤k, all they_i are distinct, and the graphΓ =Γ (y1, . . . , y_k)has a 1-(2, m)-cover.

We now proceed to show that the girth of the graphΓ we have just constructed is at leastm. We define

r^(l)(y):=

l i=1

g(y)p(a_i),

wherey∈GF(q)^∗, and for alli, a_i∈GF(q)^∗.Note that we viewr^(l)(y)as a function ofy given arbitrary fixed unitsa₁, . . . , a_l ∈GF(q)^∗. The following is an extension of [4, Lemma 3.6]:

Lemma 3.5 Ifr^(l)(y)=^r11^(l)(y) r^(l)₁₂(y) r₂₁^(l)(y) r^(l)₂₂(y)

,then for alll≥1,

(a) r₁₂^(l)(y)=yr₁₁^(l−1)(y), where we definer⁽⁰⁾(y)=I₂,the 2×2 identity matrix.

(b) deg(r₁₁^(l)(y))=l.

(c) r₁₁^(l)(y)=y^l2sl(y), wheresl(y)is a degree₂^lpolynomial iny with leading coefficienta1a2· · ·al.

(d)

sl(y)= ya_ls_l−1(y)−s_l−2(y), l even, a_ls_l−1(y)−s_l−2(y), l odd, where we defines0(y)=1 ands₋1(y)=0.

(e) For alll≥2, the coefficient ofy^2l−1insl(y), denoted byTl, is the negative of the sum ofl−1 terms, each of which is the product ofl−2 differentai,^l−₂²of which are oddi.

(f) The constant term ofsl(y), denoted byKl,is(−1)^2l forleven and(−1)^l−21(a1+ a3+a5+ · · · +al)forlodd.

(g) The linear term ofsl(y)forleven has coefficientSl, whereSl is the product of (−1)^l2+1and the sum of⁽

l 2)(₂^l+1)

2 terms of the forma_ia_j,whereiis odd andj is even.

(h) r₂₂^(l)=yr₂₁^(l−1)(y).

(i) deg(r₂₁^(l)(y))=l−1.

(j) r₂₁^(l)(y)=y^l−21tl(y),wheretl(y)is a degree^l−₂¹polynomial inywith leading coefficient−a2a3· · ·al.

(k)

t_l(y)= ya_lt_l−1(y)−t_l−2(y), l odd, altl−1(y)−tl−2(y), l even.

(l) The constant term oftl(y), denoted byK_l, is(−1)^l+21 forlodd and(−1)^l2(a2+ a4+a6+ · · ·al)forleven.

Proof Parts (a)–(c) were proved in [4].

We note first thatg(y)p(a)=_{ya y}

−1 0

,and so:

r⁽¹⁾(y)=

ya1 y

−1 0

, (3.1)

r⁽²⁾(y)=

y(ya₁a₂−1) y(ya₁)

−ya₂ −y

, (3.2)

r^(l)(y)=r^(l−1)(y)·

ya_l y

−1 0

=

r₁₁^(l−1) r₁₂^(l−1)

r₂₁^(l−1) r₂₂^(l−1)

·

ya_l y

−1 0

=

yalr₁₁^(l−1)(y)−r₁₂^(l−1)(y) yr₁₁^(l−1)(y)

yalr₂₁^(l−1)(y)−r₂₂^(l−1)(y) yr₂₁^(l−1)(y)

. (3.3)

For (d), we note thats1(y)=a1, s2(y)=ya1a2−1 and proceed by induction. We assume the result holds forn=l−2, l−1.Then using (a), (c), and (3.3), we find that

r₁₁^(l)(y)=y^2ls_l(y)

=yalr₁₁^(l−1)(y)−r₁₂^(l−1)(y)

=ya_l

y^l−21s_l−1(y)

−y

y^l−22s_l−2(y) . Checking the cases forlodd andleven distinctly yields the desired result.

For (e), we proceed by induction. Given that s₂(y)=ya₁a₂−1 and s₃(y)= ya₁a₂a₃−(a₁+a₃), we have our base case. Assume that the result holds for n=l−1.By (d) and (c),

Tl=a_l(Tl−1)−a₁a₂· · ·a_l−2,

so we have(l−2)+1=(l−1)terms, each of which is the negative of the product of(l−2)differenta_i,^l−₂²are oddi.

For (f), we proceed by induction with base casess1(y)=a1, s2(y)=ya1a2−1, s3(y)=ya1a2a3−(a1+a3),and assume that the result is true forn=l−2, l−1.

We note by (d) that forleven,

Kl= −Kl−2, proving the even case, and forlodd,

Kl=a_lKl−1−Kl−2

=al(−1)^l−12 −(−1)^l−32 (a1+a3+ · · · +al−2),

=(−1)^l−21(a₁+a₃+ · · · +a_l) which proves the result.

For (g), we again proceed by induction. We have base cases₂(y)=ya₁a₂−1.We now assume that the result is true forn=l−2 even. By (d),

Sl= −Sl−2+a_lKl−1. Using (f), this gives the desired result.

For (h), we again use induction and refer simply to (3.3).

For (i) and (j), we use induction and refer to (3.1) and (3.2) as our base cases. (3.3) gives us

r₂₁^(l)(y)=yalr₂₁^(l−1)(y)−r₂₂^(l−1)(y)

=yalr₂₁^(l−1)(y)−yr₂₁^(l−2)(y), (3.4)

immediately using the result from (h).

To prove (i), we proceed by induction and assume that it is true for all n < l.

By (3.4),r₂₁^(l)(y)is by inductive hypothesis the difference of a degreel−1 polynomial inyand a degreel−2 polynomial inyand hence is itself a degreelpolynomial iny.

To prove (j), we again proceed by induction onland assume that it holds for all n < l.Applying our inductive hypothesis,

r₂₁^(l)(y)=ya_lr₂₁^(l−1)(y)−yr₂₁^(l−2)(y)

=yal·y^l−22 tl−1(y)−y·y^l−32 tl−2(y)

=y^l−21

y^2l−l−21a_lt_l−1(y)−t_l−2(y) .

Sincetl−1(y)has leading coefficient−a2a3· · ·al−1, we now see thattl(y)has leading coefficient−a2a3· · ·al−1al, and

deg t_l(y)

=deg r₂₁^(l)(y)

− l−1

2

=(l−1)− l−1

2

= l−1

2

,

as desired.

For (k), we again use induction with base casest1(y)= −1, t2(y)= −a2, t3(y)= y(−a2a3)+1.We assume that the result is true for alln < l, and using (h), (i), and (3.3), we find that

r₂₁^(l)(y)=yalr₂₁^(l−1)(y)−r₂₂^(l−1)(y)

=ya_l

y^l−22t_l−1(y)

−y

y^l−23t_l−2(y) . Checking the cases forlodd andleven distinctly yields the desired result.

For (l), we proceed by induction with base casest1(y)= −1, t2(y)= −a2, t3(y)= y(−a2a3)+1, t4(y)=y²(−a2a3a4)+(a2+a4)and assume that the result is true forn < l.We note by (k) that forlodd,

K_l= −K_l−2,

proving the odd case, and forleven, Kl=alKl−1−Kl−2

=a_l(−1)^2l −(−1)^l−22(a₂+a₄+ · · · +a_l−2)

=(−1)^2l(a2+a4+ · · · +a_l),

which proves the result and the lemma.

With the following lemma, we are almost able to show that the graphs are polyg- onal:

Lemma 3.6 Let m=2k+2 for some k∈N, q a prime power such thatq≡ ±1 (modm), and letΓ be a near-polygonal graph with special cycles of lengthmas constructed in Lemma3.4. Then the girth ofΓ is at leastm−1.

Proof The following is analogous to the proof of [4, Theorem 1.1]. It is included for the sake of completeness and to give a flavor for what further work will need to be done.

Ifm=2k+2 for some k∈N, q≡ ±1 (modm),ζ is a primitivemth root of unity in GF(q²), andyi :=ζⁱ+ζ^m−i+2, then, by Lemma3.4,Γ =Γ (y1, . . . , yk) is a near-polygonal graph with cycles of length m. Assume thatΓ has girth n <

m−1. This means thatα∈W⁽ⁿ⁾(α)=H_n

i=1gP by Lemma3.1and that there was no “backtracking” along our n-walk, i.e., we have an (n−1)-dipath (δ₀= α, δ₁, . . . , δ_n−1)withδ_n−1 adjacent toα and no shorter dipaths fromαto itself in Γ .ThusH_n

i=1gP=H, which means that there exista₁, a₂, . . . , a_n∈GF(q)such that_n

i=1gp(a_i)∈H ,which in turn implies that_n

i=1g(y_j)p(a_i)is a lower diago- nal matrix for each 1≤j≤k.Note that for 1≤t≤(n−1),a_t=0,since otherwise

n i=1

gp(a_i)=gp(a₁)· · ·gp(a_t−1)g1gp(at+1)· · ·gp(a_n)

=gp(a1)· · ·gp(a_t−1+a_t+1)· · ·gp(a_n),

which is at most a nontrivial(n−1)-walk fromα,contradicting our assumption of girthn. Note that

n i=1

g(y)p(a_i)=r⁽ⁿ⁻¹⁾(y)·g(y)p(a_n)

=

r₁₁⁽ⁿ⁻¹⁾ r₁₂⁽ⁿ⁻¹⁾

r₂₁⁽ⁿ⁻¹⁾ r₂₂⁽ⁿ⁻¹⁾

·

ya_n y

−1 0

=

yanr₁₁⁽ⁿ⁻¹⁾(y)−r₁₂⁽ⁿ⁻¹⁾(y) yr₁₁⁽ⁿ⁻¹⁾(y)

yanr₂₁⁽ⁿ⁻¹⁾(y)−r₂₂⁽ⁿ⁻¹⁾(y) yr₂₁⁽ⁿ⁻¹⁾(y)

,

and so n i=1

gp(ai)=

y1anr₁₁⁽ⁿ⁻¹⁾(y1)−r₁₂⁽ⁿ⁻¹⁾(y1) y1r₁₁⁽ⁿ⁻¹⁾(y1)

y1anr₂₁⁽ⁿ⁻¹⁾(y1)−r₂₂⁽ⁿ⁻¹⁾(y1) y1r₂₁⁽ⁿ⁻¹⁾(y1)

, . . . , y_ka_nr₁₁⁽ⁿ⁻¹⁾(y_k)−r₁₂⁽ⁿ⁻¹⁾(y_k) y_kr₁₁⁽ⁿ⁻¹⁾(y_k)

y_ka_nr₂₁⁽ⁿ⁻¹⁾(y_k)−r₂₂⁽ⁿ⁻¹⁾(y_k) y_kr₂₁⁽ⁿ⁻¹⁾(y_k)

,

and by Lemma3.5(c)

yr₁₁⁽ⁿ⁻¹⁾(y)=y·yⁿ⁻¹² sn−1(y). (3.5) Hence eachyi is a root of the right-hand side of (3.5) in GF(q)since_n

i=1gp(ai) is lower diagonal. We know from Lemma3.4that for alli,y_i=0.Thus eachy_i for 1≤i≤kmust be a root ofs_n−1(y)in GF(q)if the girth ofΓ isn. They_i are all distinct, and so this implies that deg(sn−1(y))≥k.But, by Lemma3.5(c),

deg

s_n−1(y)

= n−1

2

≤

2k−1 2

=k−1,

sincen < m−1, a contradiction. Therefore the girth ofΓ is at leastm−1.

For the graphs of odd girth constructed in [4], the techniques used in the above lemma were enough to show that the graphs were actually polygonal. Here, however, we need the following additional theorem:

Theorem 3.7 Letm=2k+2 for somek∈N, pa prime, q=pⁿ for somen∈N, q≡ ±1 (modm), and letΓ be a near-polygonal graph with special cycles of length mas constructed in Lemma3.4. IfΓ has girth(m−1), then either

(i) p|(k−1)andp|(2^k−1−1).

(ii) p|(4k+3)andp|(5^k−4·3^k).

Proof We must look precisely at the case where we have a cycle of lengthm−1.

Since we have a 2-arc transitive automorphism group andΓ is(G,2)-dipath transi- tive, we may assume that our cycle of lengthm−1 includes[γ=H f⁻¹, α=H , β= H g],i.e., we may assume thatγ∈W^(2k−1)(β).Now,W^(2k−1)(β)=H g·P g· · ·P g (2k−1 copies ofP g). ThusH g·P g· · ·P g=H f⁻¹,or

gP· · ·gP gf∈H , or for somea₁, a₂, . . . , a_2k−1,

gp(a₁)gp(a₂)· · ·gp(a_2k−1)gf ∈H .

Note that thea_i are nonzero since there can be no returns. So let us look at g(y)p(a₁)· · ·g(y)p(a_2k−1)g(y)f (y)

=r^(2k−1)(y)·

−y y² 0 −y

=

y^k+1(−s_2k−1(y)) y^k+1(ys_2k−1(y)−s_2k−2(y)) y^k(−t_2k−1(y)) y^k+1(t_2k−1(y)−t_2k−2(y))

(3.6)

based on Lemma3.5(a), (c), (h), (j). We will use repeatedly throughout this proof the fact that, sinceq > k,two polynomials of degreekor smaller are constant multiples of one another if they have the same roots. Noting that plugging in each value ofyiin forymakes this, coordinate-wise, an element ofH ,we can conclude the following:

1. The row 1, column 2 entry of (3.6) must be zero for each value of y_i. Since deg(ys2k−1(y)−s_2k−2(y))=k,this means that for some constantc₁, we have

c₁

ys_2k−1(y)−s_2k−2(y)

=u_2k+2(y).

Note that, by Lemma 3.5(f), the constant term on the left is −c1(−1)^k−1= c₁(−1)^k, and on the right the constant term is (−1)^k_2k+1−k

k

=(−1)^k(k+1), and soc₁=k+1,giving us

(k+1)

ys_2k−1(y)−s_2k−2(y)

=u_2k+2(y). (3.7) Note that comparing leading coefficients gives us

(k+1)a1· · ·a2k−1=1. (3.8) 2. The ratio of the row 1, column 1 entry over the row 2, column 2 entry in (3.6)

must be constant for ally_i.Thus for some constantc2, we have y^k+1(−s_2k−1(y))

y^k+1(t2k−1(y)−t2k−2(y))=c2. Hence

c2

t2k−1(y)−t2k−2(y)

+s2k−1(y)=0. (3.9) Note that the left-hand side of (3.9) is at most a degree k−1 polynomial iny (s2k−1(y), t_2k−1(y) are degreek−1, t_2k−2(y) is degree k−2) with at least k distinct roots, and so the left-hand side of (3.9) must be identically 0, i.e., every coefficient is 0. Furthermore, the leading coefficient ofs2k−1(y)isa1a2· · ·a2k−1, and the leading coefficient ofc2t2k−1(y)is−c2a2a3· · ·a2k−1.Since all theai are nonzero (again, no returns and also (3.8)), we havec2=a1,and so

s2k−1(y)+a1t2k−1(y)−a1t2k−2(y)=0. (3.10)

3. Finally, the ratio of the row 2, column 1 entry over the row 1, column 1 entry in (3.6) must be constant for ally_i.Thus for some constantc₃, we have

y^k(−t2k−1(y)) y^k(−ys_2k−1(y))=c3.

So−c₃ys_2k−1(y)+t_2k−1(y)=0 must hold fory =y₁, . . . , y_k.Noting that, by Lemma3.5(c), (j),−c₃ys_2k−1(y)+t_2k−1(y)is a degreek polynomial iny, for some constantc₄, we get that

c₄

−c₃ys_2k−1(y)+t_2k−1(y)

=u_2k+2(y). (3.11) Since, by Lemma3.5(l), the constant term ofc4t2k−1(y)isc4(−1)^k and the con- stant term of u_2k+2(y) is (k+1)(−1)^k, we get c₄=k+1. Now, the leading coefficient of−(k+1)c3ys_2k−1(y)is−(k+1)c3a₁· · ·a_2k−1,and the leading co- efficient ofu_2k+2(y)is 1=(k+1)a1· · ·a_2k−1(from (3.8)), soc₃= −1,finally giving us

(k+1)

ys_2k−1(y)+t_2k−1(y)

=u_2k+2(y).

Comparing (3.7) and (3.11), we get that

s2k−2(y)= −t2k−1(y).

Using Lemma3.5(c), (j), the leading coefficient oft_2k−1(y)is−a₂· · ·a_2k−1, and the leading coefficient of−s2k−2(y)is−a1a2· · ·a2k−2,which means that

a_2k−1=a₁. (3.12)

Now, from (3.10), sincet2k−1(y)= −s2k−2(y),we get s_2k−1(y)−a1s_2k−2(y)=a1t_2k−2(y).

Noting (3.12), from part (d) of Lemma3.5we get

s_2k−1(y)−a₁s_2k−2(y)= −s_2k−3(y).

Combining these together, we get

s_2k−3(y)= −a1t_2k−2(y).

The leading coefficient of−s_2k−3(y)is−a₁a₂· · ·a_2k−3, and the leading coefficient ofa1t2k−2(y)is−a1a2· · ·a2k−3a2k−2,and so we conclude that

a_2k−2=1.

We now claim that

a₁=a₃=a₅= · · · =a_2k−3=a_2k−1, (3.13) a₂=a₄=a₆= · · · =a_2k−4=a_2k−2=1. (3.14)

We will proceed inductively. Assume that for somei >0, we have that

a_2k−1=a_2k−3= · · · =a_2k+1−2i=a₁, (3.15) a_2k−2=a_2k−4= · · · =a_2k−2i=1, (3.16) and that for all integers 1≤j≤i, we have

s_2k−2j(y)= −t_2k−2j+1(y), (3.17) s2k−2j−1(y)= −a1t2k−2j. (3.18) Again using part (d) of Lemma3.5and (3.16), we have

s2k−2i(y)=ya2k−2is2k−2i−1(y)−s2k−2i−2(y)

=ys2k−2i−1(y)−s2k−2i−2(y). (3.19) From part (k) of Lemma3.5, (3.15), (3.17), and (3.18), we have

s2k−2i(y)= −t2k−2i+1(y)

=ya_2k−2i+1

−t_2k−2i(y)

+t_2k−2i−1(y)

=ya1

−t2k−2i(y)

+t2k−2i−1(y)

=ys2k−2i−1(y)+t2k−2i−1(y). (3.20) Comparing (3.19) and (3.20), we get

s2k−2i−2(y)= −t2k−2i−1(y). (3.21) The leading coefficient ofs2k−2i−2(y)isa1a2· · ·a2k−2i−2, and the leading coefficient of−t2k−2i−1isa2· · ·a2k−2i−2a2k−2i−1,and so we conclude that

a2k−2i−1=a1. (3.22)

Again using part (d) of Lemma3.5and (3.22), we have

s2k−2i−1(y)=a2k−2i−1s2k−2i−2(y)−s2k−2i−3(y)

=a1s2k−2i−2(y)−s2k−2i−3(y). (3.23) From part (k) of Lemma3.5, (3.16), (3.18), and (3.21), we have

s2k−2i−1(y)=a1

−t2k−2i(y)

=a₁ a_2k−2i

−t_2k−2i−1(y)

+t_2k−2i−2(y)

=a1

−t_2k−2i−1(y)

+a1t_2k−2i−2(y)

=a1s2k−2i−2(y)+a1t2k−2i−2(y). (3.24)

Comparing (3.23) and (3.24), we get

s2k−2i−3(y)= −a1t2k−2i−2(y).

The leading coefficient ofs_2k−2i−3(y)isa₁a₂· · ·a_2k−2i−3, and the leading coefficient of−a₁t_2k−2i−2isa₁a₂· · ·a_2k−2i−3a_2k−2i−2,and so we conclude that

a2k−2i−2=1.

Therefore, by induction, we can continue this process indefinitely, and thus (3.13) and (3.14) must hold. Going back to (3.8), we have(k+1)a1· · ·a2k−1=1,and so (k+1)a^k₁=1,or

a₁^k= 1

k+1. (3.25)

Now, we go back to (3.7),(k+1)ys2k−1(y)−(k+1)s2k−2(y)=u2k+2(y), and look at the coefficient ofy^k−1.From part (e) of Lemma3.5, the coefficient ofy^k−1 in (k+1)ys2k−1(y)is

−(k+1)(2k−2)a₁^k−1.

The coefficient ofy^k−1in−(k+1)s2k−2(y)is just the leading coefficient, which is

−(k+1)a1· · ·a_2k−2= −(k+1)a^k₁⁻¹. Finally, the coefficient ofy^k−1inu_2k+2(y)is

(−1)¹

2k+1−1 1

= −2k.

Noting that

a^k₁⁻¹= 1 a1(k+1)

and equating the coefficient ofy^k−1on each side of (3.7), we have 2k−2

a1 + 1 a1 =2k, or

a1=2k−1

2k . (3.26)

Again, we go back to (3.7), but this time we look at the coefficient ofy.Using part (f) of Lemma3.5and then (3.26), the linear term of(k+1)ys2k−1(y)is

(k+1)(−1)^k−1(a₁+a₃+ · · · +a_2k−1)=(k+1)(−1)^k−1(ka₁)

=(−1)^k−1(k+1)2k−1 2 .

From part (g) of Lemma3.5and (3.26), the linear term of(k+1)s2k−2(y)is (−1)^k(k+1)(k−1)k

2

2k−1

2k =(−1)^k(k+1)(k−1)(2k−1)

4 .

Finally, the linear term inu2k+2(y)is (−1)^k−1

2k+1−k+1 k−1

=(−1)^k−1(k+2)(k+1)k

6 .

Putting these together, from (3.7) we get (k+1)(2k−1)

2 +(k+1)(k−1)(2k−1)

4 =(k+2)(k+1)k

6 ,

which simplifies to

(4k+3)(k−1)=0.

Case 1. Ifk−1=0,thenk=1 in GF(q). We know that a₁=2k−1

2k =1 2 in GF(q).From (3.25) we get that

(k+1)a₁^k=1,

(2) 1

2 k

=1,

2^k−1−1=0.

Thus we must havep|(k−1), p|(2^k−1−1).

Case 2. If 4k+3=0,thenk= −³₄in GF(q). We know that a1=2k−1

2k =5 3 in GF(q).Again from (3.25) we get

1 4

5 3

_k

=1,

5^k−4·3^k=0.

Thus we must havep|(4k+3), p|(5^k−4·3^k).

We now can easily prove the main results.

Proof of Theorem1.1 For a given evenm=2k+2,we construct our infinite family of near-polygonal graphs with special cycles of lengthmas in Lemma3.4. By Lemma 3.6these graphs all have girth at leastm−1,and by Theorem3.7for only finitely many primespcan the constructed graph have girthm−1.Hence there are infinitely many 2-arc transitive polygonal graphs of girthmfor all evenm≥4.

Proof of Corollary1.2 Combining the results of [4, Theorem 1.1] and Theorem1.1

proves this result.

References

1. Li, C.H., Seress, A.: Symmetrical path-cycle covers of a graph and polygonal graphs. J. Comb. Theory A 114(1), 35–51 (2007)

2. Perkel, M.: Near-polygonal graphs. Ars. Comb. A 26, 149–170 (1988)

3. Seress, A.: Polygonal graphs. In: Horizons of Combinatorics. Bolyai Society Mathematical Studies, vol. 17, pp. 179–188. Springer, Berlin (2008). Chap. 9

4. Swartz, E.: A construction of an infinite family of 2-arc transitive polygonal graphs of arbitrary odd girth. J. Comb. Theory, Ser. A 117(6), 783–789 (2010)