# Product of Locally Primitive Graphs

Authors: Amir Assari
Journal: International Journal of Mathematics and Mathematical Sciences
 (2014)

---

## Abstract

Many large graphs can be constructed from existing smaller graphs by using graph operations, such as the product of two graphs. Many properties of such large graphs are closely related to those of the corresponding smaller ones. In this paper we consider the product of two locally primitive graphs and prove that only tensor product of them will also be locally primitive.


---

## Body

## 1. Introduction

LetΓ=(V,E) be a simple graph, where V is the set of vertices and E is the set of edges of Γ. An edge joining the vertices u and v is denoted by {u,v}. The group of automorphisms of Γ is denoted by Aut(Γ), which acts on vertices of Γ. Γ is called vertex transitive if Aut(Γ) acts transitively on the set of vertices. Γ is called X-locally transitive or X-locally primitive for X⩽Aut(Γ) (or simply locally primitive or locally transitive when X=Aut(Γ)) if Xv acts transitively or primitively on Γ(v), respectively, for each vertex v∈V(Γ), where Γ(v) is the set of vertices which are adjacent to v and Xv is the stabilizer of v in X. It is known that 2-arc-transitive graphs form a proper subclass of vertex transitive locally primitive graphs.LetG be a group and let S be a nonempty subset of G. The Cayley graph of G with respect to S is denoted by Γ=Cay(G,S) is defined as a graph with vertex set G and {x,y} is an edge of Γ if and only if for some s∈S we have y=sx.Many large graphs can be constructed by expanding of small graphs; thus it is important to know which properties of small graphs can be transferred to the expanded one; for example, Li et al. in [1] proved that the lexicographic product of vertex transitive graphs is also vertex transitive as well as the lexicographic product of edge transitive graphs, and Jaradat et al. in [2] found the basis number of the semicomposition product of two paths and a cycle with a path. Here we consider seven products of graphs as the expander graph which is described below, and hence when we talk about the product of graphs, we mean that the product is one of the following products.Definition 1.
LetΓ1=(V1,E1) and Γ2=(V2,E2) be two graphs. Γ=(V,E), the product of them, is a graph with vertex set V=V1×V2, and the vertex (u1,u2) is adjacent to (v1,v2) in Γ if one of the relevant conditions happens depending on the product. (1)
Cartesian product:u1 is adjacent to v1 in Γ1 and u2=v2 or u1=v1 and u2 is adjacent to v2 in Γ2.(2)
Tensor product:u1 is adjacent to v1 in Γ1 and u2 is adjacent to v2 in Γ2.(3)
Strong product:u1 is adjacent to v1 in Γ1 and u2=v2 or u1=v1 and u2 is adjacent to v2 in Γ2 or u1 is adjacent to v1 in Γ1 and u2 is adjacent to v2 in Γ2.(4)
Lexicographic:u1 is adjacent to v1 in Γ1 or u1=v1 and u2 is adjacent to v2 in Γ2.(5)
Conormal product:u1 is adjacent to v1 in Γ1 or u2 is adjacent to v2 in Γ2.(6)
Modular product:u1 is adjacent to v1 in Γ1 and u2 is adjacent to v2 in Γ2 or u1 is not adjacent to v1 in Γ1 and u2 is not also adjacent to v2 in Γ2.(7)
Rooted product with rooth1∈V2:u1 is adjacent to v1 in Γ1 and u2=v2=h1 or u1=v1 and u2 is adjacent to v2 in Γ2.Locally primitive Cayley graphs and 2-arc-transitive graphs have been extensively studied; see, for example, [3–8] and references therein. These motivated the author to investigate if the product of two locally transitive or locally primitive graphs has the property as well.


## 2. Main Results

Theorem 2.
LetΓ1=(V1,E1) and Γ2=(V2,E2) be two simple graphs, let X be a subgroup of Aut(Γ1), and let Y be a subgroup of Aut(Γ2). Then X×Y is also a subgroup of Aut(Γ), where Γ is the product of Γ1 and Γ2.Proof.
Supposeα=(σ,δ)∈X×Y. Thus σ is an automorphism of Γ1 and δ is an automorphism of Γ2. σ is a bijection of V1 and δ is a bijection of V2, which implies α is also a bijection of V=V1×V2, the vertex set of Γ. Now assume (u1,u2) and (v1,v2) are two arbitrary adjoint vertices of Γ. We distinguish seven kinds of products as follows.
(
1
) Cartesian product: suppose Γ is the Cartesian product of the graphs Γ1 and Γ2. If (u1,u2) and (v1,v2) are adjoint in the Cartesian product, by the definition of Cartesian product, we have u1=v1 and u2 is adjacent to v2 in Γ2 or vice versa.
For the caseu1=v1, u2 and v2 are adjoint in Γ2. σ is a map; thus σ(u1)=σ(v1). δ is an automorphism of Γ2; hence δ(u2) is adjacent to δ(v2) in Γ2. Thus (σ(u1),δ(u2)) is adjacent to (σ(v1),δ(v2)), which says α((u1,u2)) is also adjacent to α((v1,v2)) in Γ.
Similar argument can be done for the caseu1 being adjacent to v1 in Γ1 and u2=v2 as well, which says α preserves the edges of the graph Γ.
(
2
) Tensor product: suppose Γ is tensor product of the graphs Γ1 and Γ2. If (u1,u2) and (v1,v2) are adjoint in the graph Γ, by the definition of tensor product, we imply that (u1,v1) and (u2,v2) are edges of Γ1 and Γ2, respectively.
σ is an automorphism of the graph Γ1, implying (σ(u1),σ(v1)) is an edge of the graph Γ1. Being δ an automorphism of the graph Γ2 yields (δ(u2),δ(v2)) will be an edge of Γ2; that is, α((u1,u2)) and α((v1,v2)) are also adjacent in the graph Γ; that is, α preserves the edges of the graph Γ.
(
3
) Strong product: from the case 1 and case 2 we can deduce that in this case we can also say α preserves the edges of the graph Γ.
(
4
) Lexicographic product: if Γ is the lexicographic product of the graphs Γ1 and Γ2 and (u1,u2) and (v1,v2) are joint by an edge in the graph Γ, by the definition of lexicographic product, (u1,v1) is an edge of Γ1, or u1=v1 and u2 is adjacent to v2 in Γ2.
Ifu1 is adjacent to v1 in Γ1, then σ(u1) is also adjacent to σ(v1) in Γ1, since σ is an automorphism of the graph Γ1, and hence by the definition of the lexicographic product, (σ(u1),δ(u2)) is adjacent to (σ(v1),δ(v2)) in the graph Γ; that is, α((u1,u2)) and α((v1,v2)) are joined by an edge in the graph Γ.
For the caseu1=v1 and u2 being adjacent to v2 in Γ2 the same argument in case 1 can be done to show that α((u1,u2)) is also adjacent to α((v1,v2)) in the graph Γ.
(
5
) Conormal product: if Γ is the conormal product of the graphs Γ1 and Γ2 and (u1,u2) and (v1,v2) are joint by an edge in the graph Γ, by the definition of conormal product we have either (u1,v1)∈E1 or (u2,v2)∈E2, where E1 and E2 are the edge set of the graphs Γ1 and Γ2, respectively.
For the first case, sinceσ is an automorphism of Γ1, thus (σ(u1),σ(v1))∈E1, and by the definition of conormal product, (σ(u1),δ(u2)) is adjacent to (σ(v1),δ(v2)) in the graph Γ.
And for the case(u2,v2)∈E2 we will have (δ(u2),δ(v2))∈E2, since δ is an automorphism of the graph Γ2. And hence (σ(u1),δ(u2)) is adjacent to (σ(v1),δ(v2)) in the graph Γ.
Therefore in both cases we have thatα((u1,u2)) and α((v1,v2)) are joint by an edge in the graph Γ; that is α preserves the edges.
(
6
) Modular product: we have (ui,vi)∈Ei for i=1,2 if and only if (σ(u1),σ(v1))∈E1 and (δ(u2),δ(v2))∈E2, because σ and δ are automorphisms of the graphs Γ1 and Γ2 respectively. Therefore (ui,vi)∉Ei for i=1,2 if and only if (σ(u1),σ(v1))∉E1 and (δ(u2),δ(v2))∉E2.
Now ifΓ is the modular product of the graphs Γ1 and Γ2 and (u1,u2) and (v1,v2) are joint by an edge in the graph Γ, by the definition of modular product, we have (ui,vi)∈Ei, or (ui,vi)∉Ei for i=1,2, where Ei is the set of edges of Γi.
For the first case we have(σ(u1),σ(v1))∈E1 and (δ(u2),δ(v2))∈E2, implying (σ(u1),δ(u2)) is adjacent to (σ(v1),δ(v2)) in the graph Γ.
For the latter case we have(σ(u1),σ(v1))∉E1 and (δ(u2),δ(v2))∉E2; that is (σ(u1),δ(u2)) is adjacent to (σ(v1),δ(v2)) in the graph Γ.
And we conclude thatΓ preserve the edges.
(
7
) Rooted product: similar argument of case (1) can be done to prove that Γ, the rooted product of graphs Γ1 and Γ2, also preserve the edges, but we have considered that if Γ is rooted product with root h1, then the image of it with respect to α will be a rooted graph with root δ(h1).
Thus ifΓ is one of the 7 kinds of products of Γ1 and Γ2, then X×Y will be a bijection on V=V1×V2 which preserves the edges of the graph Γ, implying X×Y is an automorphism of the graph Γ.Next lemma is simple to prove but useful in the literature. Thus we mention it without proof.Lemma 3.
For two simple graphsΓ1=(V1,E1) and Γ2=(V2,E2) and (u1,u2)∈V=V1×V2, If Γ is the product of graphs Γ1 and Γ2, then the neighbourhood of vertex (u1,u2) of the vertex set of Γ is as follows. (1)
Cartesian product:Γ((u1,u2))=(Γ1(u1)×{u2})∪({u1}×Γ2(u2)).(2)
Tensor product:Γ((u1,u2))=Γ1(u1)×Γ2(u2).(3)
Strong product:Γ((u1,u2))=(Γ1(u1)×{u2})∪({u1}×Γ2(u2))∪(Γ1(u1)×Γ2(u2)).(4)
Lexicographic product:Γ((u1,u2))=(Γ1(u1)×V2)∪({u1}×Γ2(u2)).(5)
Conormal product:Γ((u1,u2))=(Γ1(u1)×V2)∪(V1×Γ2(u2)).(6)
Modular product:Γ((u1,u2))=(Γ1(u1)×Γ2(u2))∪(Γ1(u1)c×Γ2(u2)c), where Γi(ui)c is the complement set of Γi(ui) in the vertex set Vi for i=1,2.(7)
Rooted product with root{h1}: Γ((u1,h1))=(Γ1(u1)×{h1})∪({u1}×Γ2(h1)) and Γ((u1,u2))={u1}×Γ2(u2), for u2≠h1.Now we focus on simple graphs, by which we mean an undirected graph with no loops.Theorem 4.
LetΓ1=(V1,E1) and Γ2=(V2,E2) be X- and Y-locally transitive nonempty (nonedgeless) simple graphs, respectively, then Γ, the product of Γ1 and Γ2, is also X×Y-locally transitive graph if and only if Γ is the tensor product of them.Proof.
By the definition of locally transitive graph, we have to determine ifΓ is one of the seven kinds of graph product of Γ1 and Γ2; (X×Y)w acts transitively on the set Γ(w), where w=(u1,u2) is any arbitrary element of the vertex set of Γ and (X×Y)w is the stabilizer of w in X×Y.
Ifα=(σ,δ) is in the stabilizer of w=(u1,u2) in X×Y, then α(w)=w and we have
(1)α(w)=(σ,δ)(u1,u2)=(σ(u1),δ(u2))=(u1,u2)=w.
Thus σ(u1)=u1 and δ(u2)=u2, implying σ∈Xu1 and δ∈Yu2; that is, α=(σ,δ)∈Xu1×Yu2. The converse is also true which says
(2)(X×Y)w=Xu1×Yu2.
LetΓ be Cartesian product of Γ1 and Γ2. Lemma 3 implies that Γ(w)=(Γ1(u1)×{u2})∪({u1}×Γ2(u2)). Now for every α=(σ,δ)∈(X×Y)w we have σ(u1)=u1, since σ is in the stabilizer of u1 in x. Similar argument shows that δ(u2)=u2. Γ1 and Γ2 both are edgeless and hence the sets Γ1(u1) and Γ2(u2) are nonempty for some u1∈V1 and u2∈V2 which are disjoint from the sets {u1} and {u2}, respectively. Thus there is not any α∈(X×Y)w which sends (u1,u2′) to (u1′,u2) for some u1′∈Γ1(u1) and u2′∈Γ2(u2), implying Γ is not locally transitive.
Similar argument shows that ifΓ is strong product, lexicographic product, conormal product, or rooted product (consider Γ(u1,h1) for some u1 in an edge of Γ1); then it is not locally transitive graph.
Forσ∈Xu1 and v∈Γ1(u1) we have σ(v)∈Γ1(v), which implies σ(v) can not be in Γ1(u1)c; that is, modular product of them can not be locally transitive.
IfΓ is the tensor product of Γ1 and Γ2, then by Lemma 3, Γ(w)=Γ1(u1)×Γ2(u2). Now if Γ1 and Γ2 are X- and Y-locally transitive, respectively, then Xu1 and Yu2 act transitively on the set of Γ1(u1) and Γ2(u2), respectively, for every u1∈V1 and u2∈V2, and we conclude that (X×Y)w acts transitively on the set Γ(w) for every w∈V1×V2; that is, Γ is locally transitive.Lemma 5.
LetΓ1=(V1,E1) and Γ2=(V2,E2) be two simple graphs which are X- and Y-locally primitive, respectively; then Γ is X×Y-locally primitive graph, where Γ is the tensor product of Γ1 and Γ2.Proof.
By Theorem2, X×Y is a subgroup of the automorphism group of graph Γ.
Suppose(u1,u2)∈V1×V2 be an arbitrary vertex of the graph Γ. By Lemma 3 we have Γ(u1,u2)=Γ1(u1)×Γ2(u2).
α
=
(
σ
,
δ
) is in stabilizer of (u1,u2) in X×Y if and only if (σ,δ)(u1,u2)=(u1,u2) if and only if σ(u1)=u1 and δ(u2)=u2; that is, (X×Y)(u1,u2)=Xu1×Yu2.
By assumptionXu1 acts on Γ1(u1) primitively as well as Yu2 on Γ2(u2). Thus it is enough to show that Xu1×Yu2 acts primitively on Γ1(u1)×Γ2(u2). But transitivity of it arises from Theorem 4, and hence we should prove that it does not have any nontrivial block.
Suppose not, and take some nontrivial blockB of Xu1×Yu2 in Γ1(u1)×Γ2(u2). Set A=π1-1(B) and C=π2-1(B), where πi is the projective map of ith coordinate.
Forσ∈Xu1, if Aσ∩A≠∅, that is, s′∈A exists such that for some s∈A we have sσ=s′, then for some t,t′∈Γ2(u2), both of (s,t) and (s′,t′) belong to B.
We also knowYu2 acts on Γ2(u2) primitively and so transitively; thus we can say, for some δ∈Yu2, (s,t)α=(s′,t′); that is (s′,t′)∈B∩Bα for some α∈Xu1×Yu2, and by permittivity condition B should be the same as Bα; thus, for every s∈A, some t∈Γ2(u2) exists such that (s,t)∈B implies (s,t)α=(sσ,tα)∈Bα=B; therefore sσ should belong to A, and thus Aσ⊆A. But σ is bijection and so Aσ=A; that is, A is a block for Γ1(u1).
Similarly,C is also a block for Γ2(u2). Thus if B is a nontrivial block, then either A or C should also be a nontrivial block which is a contradiction to the assumption.By the definition of locally permittivity and Lemma5 and Theorem 4 we conclude the following theorem.Theorem 6.
LetΓ1=(V1,E1) and Γ2=(V2,E2) be two nonempty simple graphs which are X- and Y-locally primitive, respectively, then Γ, the product of Γ1 and Γ2, is X×Y-locally primitive if and only if Γ is the tensor product.In [9], the authors proved the following lemma for semigroups and hence we can conclude it is valid for groups.Lemma 7.
LetH and K be two groups and let S and T be inverse closed subsets of them, respectively, which does not contain the identity element. If Γ1=Cay(H,S) and Γ2=Cay(K,T), then Γ the tensor product of the graphs Γ1 and Γ2 is also a Cayley graph of the group H×K with respect to the subset S×T.Now by the Theorem6 and Lemma 7 we can conclude the following theorem.Theorem 8.
LetH and K be two groups, let S be an inverse closed subset of H, and let T be an inverse closed subset of K and none of them have the identity. If Γ1=Cay(H,S) is X-locally primitive and Γ2=Cay(K,T) is Y-locally primitive Cayley graph, then Γ=Cay(H×K,S×T) is X×Y locally primitive Cayley graph.



---

*Source: 308718-2014-05-04.xml*