On the critical group of the k-partite graph
Xinyu Dong Guangfeng Jiang Weili Guo



 
 
 
 
 
 





 
   


graphs, graphs.standard 

shapes.geometric, arrows




	node/.style=circle, draw, 
	edge/.style=->, thick, 
	arrow/.style=line width=0.5pt, 


  
a4paper,scale=0.75
qiquanfigs/
figuresection


lemmaLemma[section]
theoremTheorem[section]
corollaryCorollary[section]
definitionDefinition[section]
propositionProposition[section]
exampleExample[section]
proofProof[section]
remarkRemark[section]
























dingzfcpp4141@126.com



organization=College of Mathematics and Physics, Beijing University of Chemical Technology,
	addressline=15 North Third Ring East Road, 
	city=Beijing,
	postcode=100029, 
	state=Beijing,
	country=China



guowl@mail.buct.edu.cn

[cor1]Corresponding author
	

jianggf@mail.buct.edu.cn 


	
§ ABSTRACT 

The critical group of a connected graph is closely related to the graph Laplacian, and is of high research value in combinatorics, algebraic geometry, statistical physics, and several other areas of mathematics. In this paper, we study the k-partite graphs and introduce an algorithm to get the structure of their critical groups by calculating the Smith normal forms of their graph Laplacians. When k is from 2 to 6, we characterize the structure of the critical groups completely, which can generalize the results of the complete bipartite graphs. 





	critical group, graph Laplacian, k-partite graphs, Smith normal form


[2020] 05C50 20K01










§ INTRODUCTION


Chip firing game is a discrete dynamical model	 studied by physicists, in the context of self-organized critical state. The basic rule of the model is that chips (sand, dollars) are exchanged between the sites in a network. When the model system reaches a particular state, even a very small perturbation can lead to collapse. For instance, the addition of a grain of sand can cause a massive avalanche.  In nature, there are a huge number of similar phenomena, such as fires, earthquakes, extinction of species and many others. The research of such phenomena is of vital significance, while a large number of scientists are interested and have achieved numerous results including a group structure, which is an important algebraic invariant associated with the chip-firing process. 

In 1990, Lorenzini <cit.> named the group of components Φ(G) to approach the chip firing game from the viewpoint of arithmetic geometry. Dhar <cit.> defined the sandpile group from the perspective of physics. In 1997, Bacher <cit.> named this group Jacobian and Picard group, when working on the various lattices formed by graphs. In 1999, Biggs <cit.> defined this group as critical group,  when doing research on the economic process  under the  theory  of chip firing.  

Furthermore, the critical group of a graph is strictly associated with the structure of the graph. From the Kirchoff's Matrix Tree Theorem <cit.>, we get the following two  formulas.  


	
  (i)  The order κ(G)  of the critical group of a graph G is equal to the number of spanning trees in the graph,  
    κ(G)=(-1)^i+jdetL(G),

	
	where  L(G)  is a reduced Laplacian matrix obtained from  L(G)  by striking out any row  i  and column  j.
	
	
  (ii) If the eigenvalues of  L(G)  are indexed  λ_1, …, λ_n-1, λ_n, where  n is the number of vertices of G and  λ_n=0, then
	
    κ(G)=λ_1⋯λ_n-1/n .

	


In (i), we note that the critical group can be used to study the corresponding graph. Besides, the critical group of a connected graph is a  finite Abelian group. In 1990, Rushanan <cit.> found the comparable group related to the Smith normal form of adjacency matrices known as the Smith group. Then the algebraic structure of the critical group of a graph can be known from the Smith normal form of the Laplace matrix (or adjacency matrix). For a matrix, we can get the Smith normal form by the following row and column operations:


	
  * Add a non-zero integer multiple of one row (resp. column) to another row (resp. column), 
	
	
  * Permute rows or colums, 
	
	
  * Multiply a row or column by  - 1.



The critical group structures of some special  graphs are presently fully characterized, such as  the cycle graphs C_n <cit.>, the complete graphs K_n <cit.>, the wheel graphs W_n <cit.>, the bipartite graphs K_n_1, n_2 <cit.>,  the complete
multipartite graphs  K_n_1, ⋯ , n_k  <cit.>, the de Bruijn graphs DB(n,d) <cit.>, the Möbius ladders M(n) <cit.>, the square cycles C_n^2 <cit.>, the threshold graphs <cit.>, the 3 × n twisted bracelets <cit.>, the n-cubes Q_n <cit.>, the tree graphs <cit.>, the polygon flowers <cit.> and so on.
Moreover, there are also composite graphs such as the cartesian products of complete graphs <cit.>, P_4× C_n <cit.>, K_3× C_n <cit.>, K_m× P_n <cit.>,  P_m∨  P_n <cit.>  and so on. 

Base on the present researches, we study the  critical groups of a category of incomplete multipartite graphs which are introduced after the Definition <ref>, and our work includes the results of the bipartite graphs <cit.>. For the k-partite graph G_n_1, …, n_k, we supply the algorithm of the critical groups. Furthermore, the specific abelian groups of k-partite graphs isomorphic to the critical groups are computed and listed, when k=2, 3, ⋯ , 6.

This paper is organized as follows.  In the second section, we show the definitions and the invertible matrices associated with the row and column operations to get the simpler matrices L_3,  L_4, which can simplify the calculations to get the invariant factors of the critical groups K(G_n_1, …, n_k). Through	the algorithms, we can achieve the structures of critical groups in the case k=2, 3, ⋯ , 6 in the next sections. 



§ THE CRITICAL GROUP OF THE K-PARTITE GRAPH G_N_1, …, N_K


Let G=(V, E)  be a graph on  n  vertices. The graph Laplacian  L(G)  is the  n × n  matrix given by


    L(G)_i j={[                       -1, i ≠ j  and {v_i, v_j}∈ E;;                 deg(v_i),                      i=j;;                        0,                otherwise. ].





Let  A  be the  n × n  adjacency matrix of  G  and let D be the  n × n  diagonal matrix with diagonal given by the degree sequence of  G. Then the above definition can be written as



    L(G)=D-A .



When G  is connected, the kernel of  L(G)  is spanned by the vectors in  ℝ^|V|  which are constant on the vertices. 


Thinking of  L(G)  as a map  ℤ^|V|→ℤ^|V|, its cokernel has the form


	
    ℤ^|V| / im L(G) ≅ℤ⊕ K(G),

	
where  K(G)  is defined to be the critical group. 


For more details, please refer to  <cit.>. 


A k-partite graph is one whose vertex set can be partitioned into k subsets, or parts, in such a way that no edge has both ends in the same part. 


In this article, we consider one kind of  k-partite graph G with parts of sizes n_1 , n_2,
 ⋯ , n_k. Meanwhile, G is an incomplete graph, in which the vertices in the i-th subset are only adjacent to all vertices in the (i-1)-th and (i+1)-th subsets (i=2, 3, ⋯ ,  k-1). Specifically, the vertices in the first subset are only adjacent to all vertices in the second subset. Similarly, the vertices in the k-th subset are only adjacent to all vertices in the (k-1)-th subset. For example, while k=5, n_1=6 , n_2=4, n_3=5, n_4=3, n_5=4, G_n_1, n_2, … , n_5 is shown in the Figure <ref>.



For the sake of notation, let  I_n  denote an  n × n  identity matrix, O a zero matrix, and  J_m × n an  m × n  matrix with all entries equal to 1. Then it is easily seen that by ordering the vertices of  G_n_1, …, n_k in their groups of size  n_1, n_2, …, n_k, one has



    L(G_n_1, …, n_k)=[[          n_2 I_n_1        -J_n_1× n_2                  O                  ⋯                  O                  O;        -J_n_2× n_1     (n_1+n_3)I_n_2        -J_n_2× n_3                  ⋯                  O                  O;                  O        -J_n_3× n_2     (n_2+n_4)I_n_3                  ⋯                  O                  O;                  ⋮                  ⋮                  ⋱                  ⋱                  ⋮                  ⋮;                  O                  O                  ⋯    -J_n_k-1× n_k-2 (n_k-2+n_k)I_n_k-1      -J_n_k-1× n_k;                  O                  O                  ⋯                  O      -J_n_k× n_k-1         n_k-1I_n_k ]].



In the first stage of reduction, one can perform row and column operations on  L(G_n_1, …, n_k)  to make 

    P_1 	L(G_n_1, …, n_k)   Q_1=[[   L_1,1   L_2,2       O       ⋯       O       O;   L_2,1   L_1,2   L_2,3       ⋯       O       O;       O   L_2,2   L_1,3       ⋯       O       O;       ⋮       ⋮       ⋱       ⋱       ⋮       ⋮;       O       O       ⋯ L_2,k-2 L_1,k-1   L_2,k;       O       O       ⋯       O L_2,k-1   L_1,k ]],

where

    L_1,i=	[[ N_i   0   0   ⋯   0   0;   0 N_i   0   ⋯   0   0;   0   0 N_i   ⋱   ⋮   ⋮;   ⋮   ⋮   ⋱   ⋱   0   0;   0   0   ⋯   0 N_i   0;   0   0   ⋯   0   0 N_i ]],
    	L_2,i=[[ -n_i    0    0    ⋯    0   -1;    0    0    0    ⋯    0    0;    0    0    0    ⋱    ⋮    ⋮;    ⋮    ⋮    ⋱    ⋱    0    0;    0    0    ⋯    0    0    0;    0    0    ⋯    0    0    0 ]].


    N_i={[ (n_i-1+n_i+1),  i=2,3,⋯,k-1 ;;           n_2,           i=1;;         n_k-1,           i=k. ].





The matrices  P_1  and  Q_1  are block diagonal  P_1=diag(P_1,1, …, P_1,k),

 Q_1=diag(Q_1,1, …, Q_1,k), where  P_1,i  and  Q_1,i  are  n_i× n_i  matrices given as:


    P_1,i=[[      1      0      0      ⋯      0      0;     -1      1      0      ⋯      0      0;      0     -1      1      ⋱      ⋮      ⋮;      ⋮      ⋮      ⋱      ⋱      0      0;      0      0      ⋯     -1      1      0; -n_i+1      1      ⋯      1      1      1 ]],     Q_1,i=[[      1      0      0      ⋯      0      0;      1      1      0      ⋯      0      0;      1      1      1      ⋯      ⋮      ⋮;      ⋮      ⋮      ⋱      ⋱      0      0;      1      1      ⋯      1      1      0;      1 -n_i+2      ⋯     -2     -1      1 ]].


According to the above row and column operations on L(G_n_1, …, n_k), we can get the following proposition. 


	The critical group of the graph G_n_1, …, n_k has the following isomorphism, 
	
    ℤ⊕ K(G_n_1, …, n_k)≅(⊕_i=1^kℤ /  (N_iℤ)^⊕(n_i-2)) ⊕ coker L_3,

	where  L_3  is the  2k × 2k  matrix obtained by removing some rows and columns 
	
	
    L_3=[[    N_1      0   -n_2     -1      …      …      0      0;      0    N_1      0      0      ⋯      …      0      0;   -n_1     -1    N_2      0      ⋱      ⋱      ⋮      ⋮;      0      0      0    N_2      ⋱      ⋱      ⋮      ⋮;      ⋮      ⋮      ⋱      ⋱      ⋱      ⋱   -n_k     -1;      ⋮      ⋮             ⋱      ⋱      ⋱      0      0;      0      0      ⋯      ⋯ -n_k-1     -1    N_k      0;      0      0      ⋯      ⋯      0      0      0    N_k ]].




		
			After the operation P_1 	L(G_n_1, …, n_k)   Q_1, the resulting matrix is as follows: 
			
    L =[[  N_1    0    …    0 -n_2    0    …   -1    …    …    0    0    …    0;    0  N_1    …    0    0    0    ⋯    0    ⋯    …    0    0    …    0;    ⋮    ⋮    ⋱    ⋮    ⋮    ⋮    ⋱    ⋮    ⋯    ⋯    ⋮    ⋮    ⋱    ⋮;    0    0    …  N_1    0    0    ⋯    0    ⋯    …    0    0    …    0; -n_1    0    ⋯   -1  N_2    0    ⋯    0    ⋯    ⋯    0    0    ⋯    0;    0    0    ⋯    0    0  N_2    ⋯    0    ⋯    ⋯    0    0    ⋯    0;    ⋮    ⋮    ⋱    ⋮    ⋮    ⋮    ⋱    ⋮    ⋯    ⋯    ⋮    ⋮    ⋱    ⋮;    0    0    …    0    0    0    ⋯  N_2    ⋯    …    0    0    …    0;    0    0    …    0 -n_2    0    …   -1    …    …    0    0    …    0;    0    0    …    0    0    0    ⋯    0    ⋯    …    0    0    …    0;    ⋮    ⋮    ⋱    ⋮    ⋮    ⋮    ⋱    ⋮    ⋯    ⋯    ⋮    ⋮    ⋱    ⋮;    0    0    …    0    0    0    ⋯    0    ⋯    …    0    0    …    0;    ⋮    ⋮         ⋮    ⋮    ⋮    ⋮    ⋮    ⋮    ⋮;    ⋮    ⋮         ⋮    ⋮    ⋮    ⋮    ⋮    ⋮    ⋮;    0    0    …    0    0    0    …    0    …    …  N_k    0    …    0;    0    0    …    0    0    0    ⋯    0    ⋯    …    0  N_k    …    0;    ⋮    ⋮    ⋱    ⋮    ⋮    ⋮    ⋱    ⋮    ⋯    ⋯    ⋮    ⋮    ⋱    ⋮;    0    0    …    0    0    0    ⋯    0    ⋯    …    0    0    …  N_k;      ]].

			
			Consider the rows and columns of the integers N_1 in the matrix, we can find that the entries are only zeros in the same rows and columns as from the second to (n_1-1)-th entry N_1. The situations are same for the integer from N_2 to N_k. Hence, we can  obtain n_i-2 invariant factors N_i and the  2k × 2k  matrix L_3 by removing these rows and columns.
			▪ 
			
		
		




By calculation, we can obtain L_4=P_2L_3Q_2, where P_2, Q_2∈ G L_2 k(ℤ)   are as follows,  


    [ P_2=[[        B        A        O        O        O        ⋯        ⋯        O;   n_1B-D     n_2B        A        O        O        ⋯        ⋯        O;   n_1B-D   n_2B-D     n_3B        A        O        ⋯        ⋯        O;        ⋮        ⋮        ⋱        ⋱        ⋱        ⋱                 ⋮;        ⋮        ⋮                 ⋱        ⋱        ⋱        ⋱        ⋮;        ⋮        ⋮                          ⋱        ⋱        ⋱        O;   n_1B-D   n_2B-D        ⋯        ⋯        ⋯ n_k-2B-D   n_k-1B        A;   n_1R+S   n_2R+S        ⋯        ⋯        ⋯ n_k-2R+S n_k-1R+S   n_kR+T ]], ]



	
    [ Q_2=	[[   -n_1A+I_2           O           O           ⋯           O           O;           O   -n_2A+I_2           O           ⋯           O           O;           O           O   -n_3A+I_2           ⋱           ⋮           ⋮;           ⋮           ⋮           ⋱           ⋱           O           O;           O           O           ⋯           O -n_k-1A+I_2           O;           O           O           ⋯           O           O   -n_kA+I_2 ]], ]

	
where 




    A= [[ 0 0; 1 0 ]],    B= [[ 1 0; 0 0 ]],    C= [[  1  0;  0 -1 ]],    D= [[  0 -1;  0  0 ]],

 


    R= [[ 1 0; 1 0 ]],    S= [[ 0 1; 0 1 ]],    T= [[ 0 0; 0 1 ]].



Further reduction of  L_3  can be achieved by re-ordering rows and columns to obtain

    L_4=[[              -n_2B-T               N_2A+D                    C                    O                    O                    O                    ⋯                    ⋯                    O;                    O       n_2N_2B+n_1D-T            N_3A+n_2D                    C                    O                    O                    ⋯                    ⋯                    O;                    O                    O       n_3N_3B+n_2D-T            N_4A+n_3D                    C                    O                    ⋯                    ⋯                    O;                    ⋮                    ⋮                    ⋱                    ⋱                    ⋱                    ⋱                                         ⋮                    ⋮;                    ⋮                    ⋮                                         ⋱                    ⋱                    ⋱                    ⋱                    ⋮                    ⋮;                    ⋮                    ⋮                                                              ⋱                    ⋱                    ⋱                    ⋱                    ⋮;                    O                    O                    ⋯                    ⋯                    ⋯                    O n_k-2N_k-2B+n_k-3D-T        N_k-1A+n_k-2D                    C;                    O                    O                    ⋯                    ⋯                    ⋯                    ⋯                    O n_k-1N_k-1B+n_k-2D-T          N_kA+n_k-1D;                    O                    O                    ⋯                    ⋯                    ⋯                    ⋯                    O                    O       n_kN_kB+n_k-1D;                      ]] .
	


Now, L_4 is an upper triangular matrix and  upper 5-banded matrix, where the entries in the i-th row and j-th column are zeros for j<i and j≥ i+5. According to the algorithms in the paper <cit.>, we can reduce L_4 to an upper 2-banded matrix. And then we obtain its Smith normal form  by the algorithms in <cit.>. 


	By the above steps, for k≥ 4, the critical groups can be decomposed as 
	
	
    ℤ⊕ K(G_n_1, …, n_k)≅   ( ⊕_i=1^kℤ /  (N_iℤ)^⊕(n_i-2))   ⊕ℤ /  (n_2(n_1+n_3) ℤ) 
       ⊕ℤ /  (n_k-2(n_k-1+n_k) ℤ) 
    			⊕𝒢,

	where 𝒢 is a finite  Abelian group determined by the numbers n_1, n_2, ⋯,  n_k. And we can achieve the determinant of the graph Laplacian L(G_n_1, …, n_k)  is 
	
    det(L(G_n_1, …, n_k))= (∏_i=1^k N_i^n_i-1) ·(∏_i=2^k-1 n_i)
 
	which is the number of spanning trees in the graph G_n_1, …, n_k. 






	For the 2-partite graph  G_n_1,n_2, we can get the followings from  Equation (<ref>) to  Equation (<ref>),
	
    ℤ⊕ K(G_n_1, n_2)≅ℤ /  (n_1ℤ)^⊕(n_2-2)⊕ℤ /  (n_2ℤ)^⊕(n_1-2)⊕ coker L_3(G_n_1, n_2),

	
    L_3(G_n_1,n_2) =[[  n_2    0 -n_2   -1;    0  n_2    0    0; -n_1   -1  n_1    0;    0    0    0  n_1 ]].

	By some row and column operations, we get L_4(G_n_1,n_2) = P_3(G_n_1,n_2)L_3(G_n_1,n_2)Q_3(G_n_1,n_2), 
	where 
		
    [ P_3(G_n_1, n_2)=[[    1    0    0    0;    0    1    0    0; -n_1    0    1    0;    0    0    0    1 ]] ], 
    	[ Q_3(G_n_1,  n_2) =[[   0   0   0   1;   0   1 n_1 n_1;   0   0   1   1;   1   0   0 n_2;     ]], ]


    [ L_4(G_n_1, n_2)=[[     -1      0      0      0;      0     -1      0      0;      0      0 n_1n_2      0;      0      0      0      0 ]] ].

	
	Then we find
	
    ℤ⊕ K(G_n_1, n_2)≅ℤ /  (n_1ℤ)^⊕(n_2-2)⊕ℤ /  (n_2ℤ)^⊕(n_1-2)⊕ℤ /  (n_1n_2ℤ).

	
		


In this case, the result is identical to the one in <cit.>. It is straightforward to work out the critical group structures of complete bipartite graphs with our method.


	For k=3, G_n_1,n_2,n_3 is also a  complete bipartite graph. In other words, consider the n_1+n_3 vertices  of the first and third parts as one part of the bipartite graph, and the remaining n_2 vertices as the other part.




§ THE CRITICAL GROUP OF THE 4-PARTITE GRAPH


In this section, we can obtain the critical group of the 4-partite graph G_n_1, …, n_4. Following the above calculation steps from Equation (<ref>) to Equation (<ref>), we can achieve


    ℤ⊕ K(G_n_1, …, n_4)≅(⊕_i=1^4ℤ /  (N_iℤ)^⊕(n_i-2))  ⊕ coker L_4(G_n_1, …, n_4),

where 	
    L_4(G_n_1, …, n_4):=[[          n_2            0            0           -1            0            0            0            0;            0           -1      n_1+n_3            0            0           -1            0            0;            0            0 n_2(n_1+n_3)         -n_1            0          n_2            0            0;            0            0            0           -1      n_2+n_4            0            0           -1;            0            0            0            0 n_3(n_2+n_4)         -n_2            0         -n_3;            0            0            0            0            0           -1          n_3            0;            0            0            0            0            0            0       n_3n_4         -n_3;            0            0            0            0            0            0            0            0;              ]] .


By calculation, we can obtain L_5(G_n_1, …, n_4)=P_3(G_n_1, …, n_4)L_4(G_n_1, …, n_4)Q_3(G_n_1, …, n_4), where P_3(G_n_1, …, n_4), Q_3(G_n_1, …, n_4) ∈ G L_8(ℤ)  are


    [ P_3(G_n_1, …, n_4)=[[        1        0        0       -1        0        0        0        0;        0        1        0        0        0        0        0        0; -n_1-n_3        0        1      n_3       -1        0        0        0;        0        0        0        1        0        0        0        0;        0        0        0        0        1     -n_2       -1        0;        0        0        0        0        0        1        0        0;      n_3        0        0     -n_3        1     -n_2        0        0;        0        0        0        0        0        0        0        1;          ]] ],


    [ Q_3(G_n_1, …, n_4) =[[       0       0       1       0       0       0       0       1;       0       1    -n_3       0       0      -1    -n_3     n_1;       0       0       0       0       0       0       0       1;      -1       0     n_2       1       0       0       0     n_2;       0       0       1       0       1       0       1       1;       0       0     n_3       0       0       1     n_3     n_3;       0       0       1       0       0       0       1       1;       1       0     n_4       0 n_2+n_4       0 n_2+n_4     n_4;         ]], ]


and



    L_5(G_n_1, …, n_4):=[[            1            0            0            0            0            0            0            0;            0           -1            0            0            0            0            0            0;            0            0 n_2(n_1+n_3)            0            0            0            0            0;            0            0            0           -1            0            0            0            0;            0            0            0            0 n_3(n_2+n_4)            0            0            0;            0            0            0            0            0           -1            0            0;            0            0            0            0            0            0      -n_2n_3            0;            0            0            0            0            0            0            0            0;              ]] .
	

Hence, we can obtain the following therom. 


	The critical group of G_n_1,n_2,n_3,n_4 has the following structure
	
    ℤ⊕ K(G_n_1,n_2,n_3,n_4)≅   ℤ /  (n_2ℤ)^⊕(n_1-2)⊕ℤ /  ((n_1+n_3) ℤ)^⊕(n_2-2)
       ⊕ℤ /  ((n_2+n_4) ℤ)^⊕(n_3-2)⊕ℤ /  (n_3ℤ)^⊕(n_4-2)
       ⊕ℤ /  (n_2n_3) ℤ) ⊕ℤ /  (n_2(n_1+n_3) ℤ) ⊕ℤ /  (n_3(n_2+n_4) ℤ).







§ THE CRITICAL GROUP OF  THE 5-PARTITE GRAPH




In this section, we continue to calculate the critical group of the 5-partite graph with the same method as before. Then we can get 



    ℤ⊕ K(G_n_1, …, n_5)≅(⊕_i=1^5ℤ /  (N_iℤ)^⊕(n_i-2)) ⊕ coker L_4(G_n_1, …, n_5),

where 	
    L_4(G_n_1, …, n_5):=[[          n_2            0            0           -1            0            0            0            0            0            0;            0           -1      n_1+n_3            0            0           -1            0            0            0            0;            0            0 n_2(n_1+n_3)         -n_1            0         -n_2            0            0            0            0;            0            0            0           -1      n_2+n_4            0            0           -1            0            0;            0            0            0            0 n_3(n_2+n_4)         -n_2            0         -n_3            0            0;            0            0            0            0            0           -1          n_4            0            0           -1;            0            0            0            0            0            0 n_4(n_3+n_5)         -n_3            0         -n_4;            0            0            0            0            0            0            0           -1          n_4            0;            0            0            0            0            0            0            0            0       n_4n_5         -n_4;            0            0            0            0            0            0            0            0            0            0;              ]] .



By calculation ,we can obtain L_5(G_n_1, …, n_5)=P_3(G_n_1, …, n_5)L_4(G_n_1, …, n_5)Q_3(G_n_1, …, n_5), where P_3(G_n_1, …, n_5), Q_3(G_n_1, …, n_5) ∈ G L_10(ℤ)  are


    [ P_3(G_n_1, …, n_5)=[[        1        0        0       -1        0        0        0        1        0        0;        0        1        0        0        0        0        0        1        0        0; -n_1-n_3        0        1      n_3       -1        0        0        0        0        0;        0        0        0        1        0        0        0        1        0        0;      n_3        0        0     -n_3        1     -n_2        0        0        0        0;        0        0        0        0        0        1        0        0        0        0;        0        0        0        0        0        0        1     -n_3       -1        0;        0        0        0        0        0        0        0        1        0        0;        0        0        0        0        0        0        1     -n_3        0        0;        0        0        0        0        0        0        0        0        0        1;          ]] ],


    [ Q_3(G_n_1, …, n_5)=[[       0       0       0       0       1       0       0       0       0       1;       0       1 n_1+n_3       0 n_1+n_3      -1       0       0       1     n_1;       0       0       1       0       1       0       0       0       0       1; n_2+n_4       0       0       1       0       0       0      -1       0     n_2;       1       0       0       0       0       0       0       0       0       1;       0       0       0       0       0       1       0       0      -1     n_3;       0       0       0       0       0       0       1       0       0       1;       0       0       0       0       0       0       0       1       0     n_4;       0       0       0       0       0       0       0       0       0       1;       0       0       0       0       0       0     n_4       0       1     n_5;         ]], ]


and


    L_5(G_n_1, …, n_5)=[[     -n_2-n_4            0            0            0          n_2            0            0            0            0            0;            0           -1            0            0            0            0            0            0            0            0;            0            0 n_2(n_1+n_3)            0            0            0            0            0            0            0;            0            0            0           -1            0            0            0            0            0            0;            0            0            0            0       n_2n_3            0            0            0          n_2            0;            0            0            0            0            0           -1            0            0            0            0;            0            0            0            0            0            0 n_4(n_3+n_5)            0            0            0;            0            0            0            0            0            0            0           -1            0            0;            0            0            0            0            0            0            0            0         -n_4            0;            0            0            0            0            0            0            0            0            0            0 ]] .
	


	




By the row and column operations, we can further reduce  L_5(G_n_1, …, n_5) to obtain [[ L_6   O;   O L_7 ]], where L_6 is a diagonal matrix, and L_7=[[ -n_2-n_4      n_2        0;        0   n_2n_4      n_2;        0        0     -n_4 ]]. By calculating the Smith normal form of L_7, we get the invariant factors σ_1, σ_2/σ_1, det(L_7)/σ_2. Then we obtain the following theorem. 



	For the graph G_n_1,n_2,n_3,n_4,n_5, its critical group can be decomposed as following 
	
    ℤ⊕ K(G_n_1,n_2,n_3,n_4,n_5)≅   ℤ /  (n_2ℤ)^⊕(n_1-2)⊕ℤ /  ((n_1+n_3) ℤ)^⊕(n_2-2)
       ⊕ℤ /  ((n_2+n_4) ℤ)^⊕(n_3-2)⊕ℤ /  ((n_3+n_5) ℤ)^⊕(n_4-2)
       ⊕ℤ /  (n_4ℤ)^⊕(n_5-2)⊕ℤ /  (n_2(n_1+n_3) ℤ)⊕ℤ /  (n_4(n_3+n_5)) ℤ) 
       ⊕ℤ /  (σ_1ℤ)⊕ℤ /  ((σ_2/σ_1) ℤ) ⊕ℤ /  ((n_2n_3n_4(n_2+n_4) /σ_2) ℤ),
 
	where	
    σ_1=gcd(n_2,n_4,n_2+n_4,n_2n_3), 
       σ_2=gcd(n_2^2 , n_2n_4 , n_2n_3n_4 , n_2(n_2+n_4) , n_4(n_2+n_4) , n_2n_3(n_2+n_4) ).
 	








§ DISCUSSION




With the above method, for k=6, 

    ℤ⊕ K(G_n_1,⋯ ,n_6)≅   ℤ /  (n_2ℤ)^⊕(n_1-2)⊕ℤ /  ((n_1+n_3) ℤ)^⊕(n_2-2)
       ⊕ℤ /  ((n_2+n_4) ℤ)^⊕(n_3-2)⊕ℤ /  ((n_3+n_5) ℤ)^⊕(n_4-2)
       ⊕ℤ /  ((n_4+n_6) ℤ)^⊕(n_5-2)⊕ℤ /  (n_5ℤ)^⊕(n_6-2)
       ⊕ℤ /  (n_2(n_1+n_3) ℤ) ⊕ℤ /  (n_5(n_4+n_6)) ℤ) ⊕ℤ /  (σ_1ℤ) 
       ⊕ℤ /  ((σ_2/σ_1) ℤ)⊕ℤ /  ((n_2n_3n_4n_5(n_2+n_4)(n_3+n_5) /σ_2) ℤ).
 
where 
    σ_1=   gcd(n_2n_3, n_2n_5, n_3(n_2+n_4), n_5(n_2+n_4), n_2(n_3+n_5), n_4(n_3+n_5)),
    σ_2=    gcd(n_2n_3^2(n_2+n_4) , n_2n_3n_5(n_2+n_4), n_2n_3(n_2+n_4)(n_3+n_5), n_2^2n_5(n_3+n_5),  
        n_5(n_2+n_4)^2(n_3+n_5) ) .


In this paper, we study the  critical group of the k-partite graph G_n_1, …, n_k. First of all, we obtain the algorithm of the critical group K(G_n_1, …, n_k) for the  arbitrary k.  When k = 2, G_n_1, n_2  is a completely bipartite graph, and our conclusion is consistent with the result in <cit.>. Then the decompositions of the critical groups of k-partite graphs are given for the cases k = 3, 4, 5, and 6.

For further research, we have two questions. 

Question I: Based on the k-partite graphs in this paper, randomly deleting some edges, how to calculate the critical groups of the modified graphs? 

Question II: What is the solution to compute the critical groups for the arbitrary incomplete multi-partite graphs? 


§ ACKNOWLEDGMENTS
 
	We would like to show our great gratitude to the anonymous referees for carefully reading this manuscript and improving its presentation and accuracy. The corresponding author is supported by National Science Fund for Distinguished Young Scholars 12201029. 

elsarticle-num 




