betaFeedback

WorksMathematics

Fibre factorization and automorphisms of direct products of bipartite graphs

Abstract

We determine the automorphism groups of direct products of finite connected twin-free bipartite graphs whose factors are different from K2K_2. The product is generally disconnected, so the problem requires both the automorphism groups of its components and a criterion for component isomorphism. We retain the order of the bipartition classes and use the fibre product over K2K_2. An edge-relation construction, together with McKenzie's strict refinement theorem, yields unique fibre-prime factorization and a coordinate description of every specified isomorphism. After refining the original factors, component isomorphism classes are described by intersections of factor-symmetry orbits with a set of admissible labels. The stabilizer of a label acts faithfully as the fullautomorphism group of its component. These data determine the full automorphism group, including products with repeated or fibre-composite factors. For products of fibre powers of one prime graph, we compute the component groups and express their multiplicities through a subset-sum polynomial. We also obtain an explicit semidirect product for a mixed product with one nonbipartite factor and explain its relation to known stability results. An application recovers the known double-cover groups of bipartite generalized Petersen graphs.

Introduction

Motivation

The automorphism problem for a graph product asks how its symmetries are determined by the factors. For a direct product of connected bipartite graphs, there are two questions: what is the automorphism group of each connected component, and which components are isomorphic? The first determines the symmetries within components; the second determines which components may be permuted. We answer both questions from prime-factor data for connected twin-free bipartite factors, none isomorphic to K2K_2. The factorization used here is for the fibre product over K2K_2.

All graphs considered in this paper are finite and undirected and have no multiple edges. We write Γ0\Gamma_0 for the class of graphs in which loops are allowed, otherwise graphs are loopless. Write x∼Xyx \sim_X y when xx and yy are adjacent in XX. For a graph XX, let V(X)V(X), E(X)E(X), and Aut⁡(X)\operatorname{Aut}(X) denote its vertex set, edge set, and automorphism group, respectively, and let NX(x)N_X(x) denote the neighbourhood of a vertex xx. A graph is twin-free if distinct vertices have distinct neighbourhoods. We follow the graph terminology of [2, 11], the group terminology of [13] and the categorical terminology of [17].

The direct product [11] of two graphs XX and YY in Γ0\Gamma_0, denoted by X×YX \times Y, has vertex set V(X)×V(Y)V(X) \times V(Y), where (x,y)(x,y) is adjacent to (x′,y′)(x',y') if and only if {x,x′}∈E(X)\{x,x'\} \in E(X) and {y,y′}∈E(Y)\{y,y'\} \in E(Y). This product is commutative and associative up to the natural coordinate isomorphisms, and its unit is the graph with one vertex and one loop. A nonunit graph is prime if at least one factor is the unit in every factorization as a direct product. Two graphs are coprime if they have no common direct factor of order greater than one. For nonempty graphs XX and YY, the coordinatewise action gives a natural embedding

Aut⁡(X)×Aut⁡(Y)≤Aut⁡(X×Y).(1)\operatorname{Aut}(X) \times\operatorname{Aut}(Y) \leq\operatorname{Aut}(X \times Y). \tag*{(1)}

Determining when equality holds in (1), and describing the additional automorphisms when the inclusion is strict, are basic problems in the theory of graph products. A complete answer must account for the way automorphisms interact with the factor coordinates.

For connected nonbipartite graphs, prime factorization supplies the relevant coordinates. Such graphs have unique prime factorizations with respect to the direct product in Γ0\Gamma_0 [11, 14, 18]. Under the additional twin-free hypothesis, every isomorphism between products of prime factors is induced by factor isomorphisms and a permutation of the corresponding coordinates [4, 11]. Thus prime factorization determines not only the isomorphism types of the factors but also the coordinate form of isomorphisms between products.

For bipartite factors, two different issues intervene. First, Weichsel’s theorem [29], also stated in [11 Theorem 5.9], implies that a direct product of r≥1r \ge1 connected bipartite graphs, each with at least one edge, has 2r−12^{r-1} connected components. A description of its full automorphism group therefore requires both the automorphism groups of individual components and a criterion for deciding which components are isomorphic. Second, prime direct product factorizations of connected bipartite graphs need not be unique [11, 12]. Thus the nonbipartite coordinate theory cannot simply be applied to the components of the direct product of bipartite graphs. The component isomorphism question has a precise answer for two factors. Jha, Klavžar and Zmažek [15] proved that the two components are isomorphic if one factor admits an automorphism interchanging its bipartition classes, and conjectured the converse. Hammack studied the problem in [8] and proved the converse in [9]. A separate result of Hammack and Puffenberger [12], extending [10], shows that the unique bipartite prime factor occurring in any prime factorization of a connected bipartite graph is determined up to isomorphism. That theorem concerns a connected direct product with exactly one bipartite prime factor. Here we study the connected components of a product in which every factor is bipartite, and we seek the structure of their isomorphisms as well as their isomorphism types.

Our approach retains an ordering of the two bipartition classes and replaces the direct product by the fibre product over K2K_2. For connected factors, the fibre product is the component in which the coordinate colours agree. It remains connected and retains the factor coordinates. We encode such ordered bipartite graphs by binary relations on their edge sets, prove that the relevant class of relations is closed under direct factors, and use McKenzie’s refinement theory [18] to obtain fibre prime factorizations and coordinate descriptions of specified isomorphisms. The resulting graph-theoretic description keeps track of factorization, bipartition reversals, and permutations of repeated isomorphic factors simultaneously.

The remaining problem is to recover the component isomorphism classes and their automorphism groups from prime-factor data. The wreath-product formula for the automorphism group of a disjoint union is classical. The essential task is to identify its constituent groups and their multiplicities directly from the factors, without treating the components as independent input data. This leads to the following question.

Problem 1.1. How can one describe the automorphism groups of the connected components of direct products of connected bipartite graphs and account for the interaction between bipartition reversals and permutations of repeated isomorphic factors?

Main results

The results proceed in three stages. First, Theorem 1.3 identifies the fibre-prime factors. Next, Theorems 1.4 and 1.5 show how a specified isomorphism acts on their coordinates, including a common colour-reversal sign. Finally, Theorem 1.6 uses these data to determine component isomorphism classes, their automorphism groups, and the automorphism group of the full direct product.

We first introduce the notation needed for the statements. Write F2\mathbb{F}_2 for the field with two elements, 0t,1t∈F2t\mathbf{0}_t,\mathbf{1}_t \in\mathbb{F}_2^t for the constant vectors, and Qt=F2t/⟨1t⟩Q_t = \mathbb{F}_2^t/\langle\mathbf{1}_t\rangle for t≥1t \ge1. A bar denotes the class of a binary vector in this quotient. Write StS_t for the symmetric group on {1,…,t}\{1,\ldots,t\}, with S0=1S_0 = 1. Maps act on the left and are composed from right to left. We use the same convention for relations: x(S∘R)zx(S \circ R)z means that xRyxRy and ySzySz for some yy. Write Zn=Z/nZ\mathbb{Z}_n = \mathbb{Z}/n\mathbb{Z}, and denote the path and cycle on nn vertices by PnP_n and CnC_n, respectively. For a finite set JJ, write SJS_J for its symmetric group. For a group GG, the notation G≀St=Gt⋊StG \wr S_t = G^t \rtimes S_t uses the action (σ⋅g)i=gσ−1(i)(\sigma\cdot g)_i = g_{\sigma^{-1}(i)}; we set G≀S0=1G \wr S_0 = 1. Bold lower-case letters denote tuples, whereas their subscripted entries are individual coordinates.

An ordered bipartite graph is a pair (B,ϱB)(B,\varrho_B), where BB is a bipartite graph and ϱB:B→K2\varrho_B:B \to K_2 is a surjective graph homomorphism. Equivalently, BB has a fixed ordered bipartition V(B)=B0⊔B1V(B) = B^0 \sqcup B^1, where Bi=ϱB−1(i)B^i = \varrho_B^{-1}(i) for i∈{0,1}i \in\{0,1\}. We call ϱB\varrho_B the colour map and write U(B)U(B) for the underlying graph of BB, obtained by forgetting the order of the two classes. A morphism from BB to CC is a graph homomorphism f:U(B)→U(C)f:U(B) \to U(C) satisfying

ϱC∘f=ϱB.\varrho_C \circ f = \varrho_B.

Ordered bipartite graphs and their colour-preserving homomorphisms form a category, denoted by Bip2_2. A graph isomorphism f:U(B)→U(C)f:U(B) \to U(C) is called an ordinary isomorphism. Such an isomorphism need not preserve the colour classes.

Definition 1.2. Let BB and CC be ordered bipartite graphs. Their fibre product over K2K_2, denoted by B⋆CB \star C, is the ordered bipartite graph with vertex set

V(B⋆C)={(b,c)∈V(B)×V(C):ϱB(b)=ϱC(c)}V(B \star C) = \{(b,c) \in V(B) \times V(C) : \varrho_B(b) = \varrho_C(c)\}

and edge set

E(B⋆C)={{(b,c),(b′,c′)}:(b,c),(b′,c′)∈V(B⋆C),{b,b′}∈E(B),{c,c′}∈E(C)}.E(B \star C) = \{\{(b,c),(b',c')\} : (b,c),(b',c') \in V(B \star C), \{b,b'\} \in E(B), \{c,c'\} \in E(C)\}.

The colour map is ϱB⋆C(b,c)=ϱB(b)=ϱC(c)\varrho_{B \star C}(b,c) = \varrho_B(b) = \varrho_C(c), so its two ordered colour classes are

(B⋆C)0=B0×C0,(B⋆C)1=B1×C1.(B \star C)^0 = B^0 \times C^0,\qquad(B \star C)^1 = B^1 \times C^1.

The graph K2K_2, equipped with its identity colour map, is the unit of this product. A connected nonunit ordered bipartite graph BB is called fibre-prime (or, f-prime) if, in every factorization B≅X⋆YB \cong X \star Y in Bip2_2, at least one of XX and YY is isomorphic to K2K_2.

The fibre product is associative and commutative up to the natural coordinate isomorphisms. We write ⋆i=1rBi\mathop{\star}_{i=1}^r B_i for an iterated fibre product and take the empty product to be K2K_2. The fibre product has a different unit and notion of primality from the ordinary direct product. The first theorem gives a common refinement of any two fibre product decompositions and, in particular, unique factorization into nonunit ff-prime factors.

Theorem 1.3. Let BB be a finite connected twin-free ordered bipartite graph. Let r,s≥0r,s \ge0, with empty fibre products interpreted as K2K_2, and suppose

B≅G1⋆⋯⋆Gr≅H1⋆⋯⋆HsB \cong G_1 \star\cdots\star G_r \cong H_1 \star\cdots\star H_s

in Bip2_2. Then the following statements hold.

(i) There are connected twin-free ff-prime ordered bipartite graphs BλB_\lambda and two indexed partitions of a finite set SS (with empty parts allowed),

S=U1⊔⋯⊔Ur=V1⊔⋯⊔VsS = U_1 \sqcup\cdots\sqcup U_r = V_1 \sqcup\cdots\sqcup V_s

such that

B≅⋆λ∈SBλ,Gi≅⋆λ∈UiBλ,Hj≅⋆λ∈VjBλ.B \cong\mathop{\star}_{\lambda\in S} B_\lambda,\qquad G_i \cong\mathop{\star}_{\lambda\in U_i} B_\lambda,\qquad H_j \cong\mathop{\star}_{\lambda\in V_j} B_\lambda.

Thus BB admits a factorization into ff-prime factors.

(ii) If G1⋆⋯⋆GrG_1 \star\cdots\star G_r and H1⋆⋯⋆HsH_1 \star\cdots\star H_s are already factorizations into nonunit ff-prime factors, then r=sr=s and there is a permutation σ∈Sr\sigma\in S_r such that for each 1≤i≤r1 \le i \le r, Gi≅Hσ(i)G_i \cong H_{\sigma(i)} in Bip2_2. Consequently, the multiset of nonunit ff-prime factors of BB is unique up to isomorphism in Bip2_2.

Unique factorization identifies the prime factors up to colour-preserving isomorphism and permutation. Determining automorphism groups requires additional information, namely a coordinate description of each specified isomorphism. The next theorem provides this description, covering cases where isomorphic factors repeat.

Theorem 1.4. Let B=B1⋆⋯⋆BrB=B_1\star\cdots\star B_r and C=C1⋆⋯⋆CsC=C_1\star\cdots\star C_s be products of connected twin-free nonunit ff-prime ordered bipartite graphs, where r,s≥1r,s\geq1. If φ:B→C\varphi:B\to C is an isomorphism in Bip2\mathbf{Bip}_2, then r=sr=s, and there exist a permutation σ∈Sr\sigma\in S_r and isomorphisms φi:Bi→Cσ(i)\varphi_i:B_i\to C_{\sigma(i)} in Bip2\mathbf{Bip}_2 for 1≤i≤r1\leq i\leq r such that, whenever φ(b1,…,br)=(c1,…,cr)\varphi(b_1,\ldots,b_r)=(c_1,\ldots,c_r), we have

cσ(i)=φi(bi),(2)c_{\sigma(i)}=\varphi_i(b_i), \tag*{(2)}

for every $1\leq i\leq r.

References

  1. [1]B. Alspach and L. Liu, On the Hamilton connectivity of generalized Petersen graphs, Discrete Math. 309 (2009), 5461–5473.DOI
  2. [2]N. Biggs, Algebraic Graph Theory, Cambridge University Press, Cambridge, 2001.
  3. [3]C. C. Chang, Cardinal factorization of finite relational structures, Fund. Math. 60 (1967), 251–269.DOI
  4. [4]W. Dörfler, Primfaktorzerlegung und automorphismen des Kardinalproduktes von graphen, Glasnik Mat. 9 (1974), 15–27.
  5. [5]B. Fernandez and A. Hujdurović, Canonical double covers of circulants, J. Combin. Theory Ser. B 154 (2022), 49–59.DOI
  6. [6]R. Frucht, J. E. Graver and M. E. Watkins, The groups of the generalized Petersen graphs, Proc. Cambridge Philos. Soc. 70 (1971), 211–218.DOI
  7. [7]Y. Gan, W. Liu and B. Xia, Unexpected automorphisms in direct product graphs, J. Combin. Theory Ser. B 171 (2025), 140–164.DOI
  8. [8]R. Hammack, Isomorphic components of direct products of bipartite graphs, Discuss. Math. Graph Theory 26 (2006), 231–248.DOI
  9. [9]R. Hammack, Proof of a conjecture concerning the direct product of bipartite graphs, European J. Combin. 30 (2009), 1114–1118.DOI
  10. [10]R. Hammack, On uniqueness of prime bipartite factors of graphs, Discrete Math. 313(9) (2013), 1018–1027.DOI
  11. [11]R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, 2nd ed., CRC Press, Boca Raton, 2011.DOI
  12. [12]R. Hammack and O. Puffenberger, A prime factor theorem for bipartite graphs, European J. Combin. 47 (2015), 123–140.DOI
  13. [13]T. W. Hungerford, Algebra, Springer, New York, 2003.
  14. [14]W. Imrich, Factoring cardinal product graphs in polynomial time, Discrete Math. 192 (1998), 119–144.DOI
  15. [15]P. K. Jha, S. Klavžar and B. Zmazek, Isomorphic components of Kronecker product of bipartite graphs, Discuss. Math. Graph Theory 17 (1997), 301–309.DOI
  16. [16]J. Lauri, R. Mizzi and R. Scapellato, Unstable graphs: a fresh outlook via TF-automorphisms, Ars Math. Contemp. 8 (2015), 115–131.arxiv.org/abs/1401.6552
  17. [17]S. Mac Lane, Categories for the Working Mathematician, 2nd ed., Graduate Texts in Mathematics 5, Springer, New York, 1998.
  18. [18]R. McKenzie, Cardinal multiplication of structures with a reflexive relation, Fund. Math. 70 (1971), 59–101.DOI
  19. [19]D. Marušić, R. Scapellato and N. Zagaglia Salvi, A characterization of particular symmetric (0, 1) matrices, Linear Algebra Appl. 119 (1989), 153–162.DOI
  20. [20]Y.-L. Qin, B. Xia and S. Zhou, Stability of circulant graphs, J. Combin. Theory Ser. B 136 (2019), 154–169.arxiv.org/abs/1802.04921
  21. [21]Y.-L. Qin, B. Xia and S. Zhou, Canonical double covers of generalized Petersen graphs, and double generalized Petersen graphs, J. Graph Theory 97 (2021), 70–81.DOI
  22. [22]Y.-L. Qin, B. Xia and S. Zhou, Stability of graph pairs involving vertex-transitive graphs, Discrete Math. 347 (2024), no. 4 Paper No. 113856, 6 pp.arxiv.org/abs/2210.06777
  23. [23]Y.-L. Qin, B. Xia, J.-X. Zhou and S. Zhou, Stability of graph pairs, J. Combin. Theory Ser. B 147 (2021), 71–95.DOI
  24. [24]D. Surowski, Stability of arc-transitive graphs, J. Graph Theory 38 (2001), 95–110.DOI
  25. [25]D. Surowski, Automorphism groups of certain unstable graphs, Math. Slovaca 53 (2003), 215–232.
  26. [26]X. Wang, Y.-L. Qin and B. Xia, The existence of unexpected automorphisms in direct product graphs, https://arxiv.org/abs/2509.26170.
  27. [27]X. Wang, S.-J. Xu and S. Zhou, Stability of graph pairs involving cycles, Graphs Combin. 41 (2025) no. 2 Paper No. 49, 22 pp.arxiv.org/abs/2403.01220
  28. [28]X. Wang and X. Gao, Stability of nontrivial graph pairs, https://arxiv.org/abs/2606.02203.
  29. [29]P. M. Weichsel, The Kronecker product of graphs, Proc. Amer. Math. Soc. 13 (1962), 47–52.DOI
  30. [30]S. Wilson, Unexpected symmetries in unstable graphs, J. Combin. Theory Ser. B 98 (2008), 359–383.DOI

Paper details

vlnc:W_g7hedzde
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents