
A dissociation set of a graph G refers to a set of vertices inducing a subgraph with maximum degree at most 1 and serves as a generalization of two fundamental concepts in graph theory: Independent sets and induced matchings. The enumeration of specific substructures in grid graphs has been a captivating area of research in graph theory. Over the past few decades, the enumeration problems related to various structures in grid graphs such as Hamiltonian cycles, Hamiltonian paths, independent sets, maximal independent sets, and dominating sets have been deeply studied. In this paper, we enumerated dissociation sets in grid graphs using the state matrix recursion algorithm.
Citation: Wenke Zhou, Guo Chen, Hongzhi Deng, Jianhua Tu. Enumeration of dissociation sets in grid graphs[J]. AIMS Mathematics, 2024, 9(6): 14899-14912. doi: 10.3934/math.2024721
[1] | Jianhua Tu, Lei Zhang, Junfeng Du, Rongling Lang . Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree. AIMS Mathematics, 2022, 7(1): 569-578. doi: 10.3934/math.2022036 |
[2] | Jianhua Tu, Junyi Xiao, Rongling Lang . Counting the number of dissociation sets in cubic graphs. AIMS Mathematics, 2023, 8(5): 10021-10032. doi: 10.3934/math.2023507 |
[3] | Ali N. A. Koam, Sikander Ali, Ali Ahmad, Muhammad Azeem, Muhammad Kamran Jamil . Resolving set and exchange property in nanotube. AIMS Mathematics, 2023, 8(9): 20305-20323. doi: 10.3934/math.20231035 |
[4] | Yasmina Khiar, Esmeralda Mainar, Eduardo Royo-Amondarain, Beatriz Rubio . High relative accuracy for a Newton form of bivariate interpolation problems. AIMS Mathematics, 2025, 10(2): 3836-3847. doi: 10.3934/math.2025178 |
[5] | M. Haris Mateen, Muhammad Khalid Mahmmod, Dilshad Alghazzawi, Jia-Bao Liu . Structures of power digraphs over the congruence equation xp≡y(modm) and enumerations. AIMS Mathematics, 2021, 6(5): 4581-4596. doi: 10.3934/math.2021270 |
[6] | Igal Sason . On H-intersecting graph families and counting of homomorphisms. AIMS Mathematics, 2025, 10(3): 6355-6378. doi: 10.3934/math.2025290 |
[7] | Xue Yu, Qingshan Zhang . Orientable vertex transitive embeddings of Kp. AIMS Mathematics, 2023, 8(7): 15024-15034. doi: 10.3934/math.2023767 |
[8] | Raúl M. Falcón, Laura Johnson, Stephanie Perkins . A census of critical sets based on non-trivial autotopisms of Latin squares of order up to five. AIMS Mathematics, 2021, 6(1): 261-295. doi: 10.3934/math.2021017 |
[9] | Zhichao Fang, Ruixia Du, Hong Li, Yang Liu . A two-grid mixed finite volume element method for nonlinear time fractional reaction-diffusion equations. AIMS Mathematics, 2022, 7(2): 1941-1970. doi: 10.3934/math.2022112 |
[10] | Adeel Farooq, Musawwar Hussain, Muhammad Yousaf, Ahmad N. Al-Kenani . A new algorithm to compute fuzzy subgroups of a finite group. AIMS Mathematics, 2023, 8(9): 20802-20814. doi: 10.3934/math.20231060 |
A dissociation set of a graph G refers to a set of vertices inducing a subgraph with maximum degree at most 1 and serves as a generalization of two fundamental concepts in graph theory: Independent sets and induced matchings. The enumeration of specific substructures in grid graphs has been a captivating area of research in graph theory. Over the past few decades, the enumeration problems related to various structures in grid graphs such as Hamiltonian cycles, Hamiltonian paths, independent sets, maximal independent sets, and dominating sets have been deeply studied. In this paper, we enumerated dissociation sets in grid graphs using the state matrix recursion algorithm.
Let G be a simple, undirected graph. An independent set of G is a subset of its vertices inducing a subgraph in which each vertex is an isolated vertex. Moreover, an induced matching in a graph G, denoted as M, is a matching where no two edges in M are joined by edges in graph G. One can identify an induced matching by searching for a subset of vertices that induces a 1-regular subgraph. Both independent sets and induced matchings are fundamental concepts in graph theory and have undergone extensive research. A dissociation set of G is a subset of vertices inducing a subgraph in which each vertex has a degree of at most 1, thus generalizing the concepts of independent sets and induced matchings.
The concept of the dissociation set was first introduced in the 1980s by Yannakakis [17] who demonstrated that determining a maximum dissociation set in bipartite graphs is an NP-hard problem. In contrast, finding a maximum independent set in bipartite graphs can be solved in polynomial time. Over the past few decades, scholars have approached the dissociation set from various perspectives [1,2,6,12,13,15,16,17,18]. There has been a surge of interest in exploring the problem of identifying the largest number of dissociation sets (or maximal dissociation sets, or maximum dissociation sets) in some classes of graphs [4,13,15,18].
In this study, we focus on the enumeration of dissociation sets in grid graphs. A grid graph with parameters m and n, denoted as Gm×n, is composed of vertices representing all points on a two-dimensional coordinate plane which have coordinates (i,j), where i is an integer and ranges from 0 to m−1, and j is an integer and ranges from 0 to n−1. The edges of the graph connect pairs of vertices (i,j) and (i′,j′) that satisfy the condition |i′−i|+|j′−j|=1. Alternatively, the grid graph Gm×n can be viewed as the Cartesian product of two paths, one with m vertices and the other with n vertices. To illustrate this concept, Figure 1 presents an example of a grid graph G6×6 along with a dissociation set in it. We use solid circles to represent the vertices in the dissociation set.
We illustrate all the dissociation sets in Gm×n for 1≤m≤n≤2 by giving examples. The empty set is also assumed to be a dissociation set.
When m=n=1, the grid graph G1×1 is the graph K1 and contains two distinct dissociation sets.
When m=1 and n=2, Figure 2 illustrates all four dissociation sets in G1×2.
When m=n=2, Figure 3 illustrates all eleven dissociation sets in G2×2.
The enumeration problem in grid graphs has its roots in the 1980s, when researchers began exploring the enumeration of Hamiltonian paths and Hamiltonian cycles in grid graphs [5,14]. Over time, researchers extended this line of inquiry to consider the enumeration of various discrete substructures in grid graphs, including independent sets, maximal independent sets, dominating sets, and more [3,9,10,11]. In this study, we target the enumeration of dissociation sets in grid graphs and employ the state matrix recursion algorithm, originally introduced by Oh [11], as a means to tackle this problem.
We derive the dissociation polynomial of a graph G as
PG(z)=ϕ(G)∑d=0 y(d)zd, |
where ϕ(G) is the cardinality of a maximum dissociation set and y(d) is the number of dissociation sets in G containing d vertices. The summation is taken over all dissociation sets of each size in G. The dissociation polynomial of a grid graph Gm×n is simply written as Pm×n(z). Clearly, Pm×n(1) is the total number of all dissociation sets in Gm×n.
Let
Lm=(1100)⊗m and Rm=(0110)⊗m, |
where A⊗m is the m-fold tensor product of a matrix A. Let 0k be the 4k×4k zero-matrix. Matrices Vm, Wm and Xm are 4m×4m matrices recursively defined by
Vk+1=(0k0k0k0kVk+WkVk+Wk0k0kVk+WkVk+Wk0k0k0k0k0k0k),Wk+1=(0k0kz(Vk+Xk)zVk0k0k0k0k0k0k0k0k0k0kzVk0k),Xk+1=(0k0kzVk0k0k0k0k0k0k0k0k0k0k0k0k0k), |
for k=0,…,m−1, starting with
V0=(1),W0=X0=(0). |
Theorem 1.1. Let Rtm be the transpose of Rm. Then
Pm×n(z)=Lm⋅(Vm+Wm)n⋅Rtm. |
For example, as for m=n=2, we can obtain the expressions of V2 and W2 are
V2=(000000000000000000000000000000000000000000000000000000000000000000zz00zz000000001100110000000000110011000000000000z000z00000000000zz00zz000000001100110000000000110011000000000000z000z0000000000000000000000000000000000000000000000000000000000000000000000000), |
W2=(0000000000z20000000000000zz00zz0000000000zz00zz00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000zz00000000000000zz0000000000000000000000). |
The row vectors L2 and R2 are
L2=(1100110000000000),R2=(0000011001100000). |
Theorem 1 provides the expression of the dissociation polynomial P2×2 is
P2×2(z)=L2⋅(V2+W2)2⋅Rt2=6z2+4z+1. |
We can obtain that the number of the dissociation sets in G2×2 is equal to P2×2(1)=11 and the result is in line with prior research.
In this section, we utilize the state matrix recursion algorithm to investigate the enumeration of dissociation sets in grid graphs and prove Theorem 1.1. This algorithm, which has been employed for enumerating independent sets, maximal independent sets, and dominating sets in grid graphs [9,10,11], consists of the following three stages:
Stage 1. Construct a mosaic system for dissociation sets in Gm×n.
Stage 2. Explore the state matrices and recursive matrix-relations.
Stage 3. Derive the dissociation polynomial of Gm×n by analyzing the state matrices and recursive matrix-relations obtained in Stage 2.
To accurately and effectively represent the states of a quantum knot system, Lomonaco and Kauffman [7,8] introduced the concept of a mosaic system. In the context of knot mosaic enumeration, Oh [9] formulated a state matrix argument, which later evolved into the state matrix recursion algorithm. This algorithmic advancement allowed Oh to tackle the enumeration of monomer-dimer coverings in grid graphs [9].
Following the terminology and notion in [7,8], we construct a corresponding mosaic C for F for each dissociation set F in Gm×n. In this construction, a tile of C is defined as a square centered at one of the vertices of Gm×n. If the vertex at the center of a tile belongs to F, we mark the tile's center with a dot. Every tile's four side edges are labeled with four letters u, v, w and x, according to the following rules.
(1) If a tile contains a dot corresponding to an isolated vertex in the induced subgraph Gm×n[F], all its side edges are labeled with w.
(2) If a tile contains a dot corresponding to a vertex of degree 1 in Gm×n[F], the side edge of it adjoining another tile containing a dot is labeled with x, and the remaining three side edges are labeled with w.
(3) For tiles without dots, the left and right side edges are both labeled with v. As for the top or bottom side edge, it is labeled with u if it adjoins a tile with a dot; otherwise, it is also labeled with v.
Thus, there are in total nine mosaic tiles I1–I9 that are shown in Figure 4.
The mosaic corresponding to the dissociation set depicted in Figure 1 is illustrated in Figure 5.
Let
N={I1,I2,I3,I4} and Y={I5,I6,I7,I8,I9}. |
The sets N and Y are derived by classifying the nine mosaic tiles based on the presence or absence of a dot. Specifically, the side edges of the mosaic tiles belonging to N are exclusively labeled with the letters u and v, whereas the side edges of the mosaic tiles in Y are labeled only with the letters w and x.
In defining an m×n-mosaic, we envision it as an m×n rectangular array C=(Cij) of tiles. Each entry Cij represents a mosaic tile positioned in the i-th column from right to left, and the j-th row from top to bottom. Our interest lies only in the mosaics whose tiles match their neighboring tiles correctly to represent dissociation sets. As following are the rules we have created for this purpose.
● Horizontal adjacency rule: In a row, the adjacent tiles' abutting edges are labeled with one of the following letter pairs: v|v, v|w, x|x.
● Vertical adjacency rule: In a column, the adjacent tiles' abutting edges are labeled with one of the following letter pairs: u|w, v|v, x|x.
● Boundary rule: Every boundary edge of a mosaic may be labeled with the letters v or w.
The horizontal adjacency rule and the vertical adjacency rule are shown in Figure 6.
An m×n-mosaic is deemed suitably adjacent when every adjacent pair of tiles adheres to two adjacency rules, furthermore, if it also satisfies the boundary rule, it is called a dissociation set m×n-mosaic.
There exists a one-to-one mapping from dissociation sets in Gm×n to dissociation set m×n-mosaics. It is clear that the number of vertices in a dissociation set equals the number of tiles belonging to the set Y in its corresponding dissociation set m×n-mosaic. Based on the one-to-one mapping, enumerating dissociation sets in Gm×n is equivalent to enumerating dissociation set m×n-mosaics.
In this subsection, we recall from [10] states and state polynomials. Let p≤m and q≤n be two positive integers and C be a suitably adjacent p×q-mosaic. We denote by d(C) the number of tiles of C belonging to the set Y.
We introduce four distinct states for C: The t-state st(C), b-state sb(C), r-state sr(C), and l-state sl(C). Each state corresponds to a finite sequence composed of the letters u, v, w, and x. Specifically, the t-state st(C) and b-state sb(C) are sequences of length p derived by reading the labels on the top and bottom boundary edges of C from right to left, respectively. Analogously, the r-state sr(C) and l-state sl(C) are sequences of length q derived by reading the labels on the right and left boundary edges of C from top to bottom, respectively. A suitably adjacent mosaic and its four states are shown and described in Figure 7.
Given three sequences sr, sb and st composed of the letters u, v, w and x, we obtain the state polynomial
P⟨sr,sb,st⟩(z)=∑Ci(d)zd, |
where the summation is taken over all suitably adjacent p×q-mosaics C with the property that sr(C)=sr, sb(C)=sb, st(C)=st and sl(C) satisfies the boundary rule, and i(d) is the number of suitably adjacent p×q-mosaics C with d(C)=d. We use i⟨sb,st⟩(d) to denote the number of mosaics satisfying b-state is sb and t-state is st. Note that none of sr(C), sb(C) and st(C) needs to satisfy the boundary rule.
A bar mosaic of length p is a suitably adjacent p×1-mosaic and has at most 4p different t- and b-states, which are especially called bar states. The bar states are arranged in the following two orders; (1) The uvwx-order (for example, the order of bar states of length p=2 and p=3 is as follows: p=2: uu, uv, uw, ux, vu, vv, vw, vx, wu, wv, ww, wx, xu, xv, xw, xx; And p=3: uuu, uuv, uuw, uux, uvu, uvv, uvw, uvx, uwu, uwv, uww, uwx, uxu, uxv, uxw, uxx, vuu, vuv, vuw, vux, vvu, vvv, vvw, vvx, vwu, vwv, vww, vwx, vxu, vxv, vxw, vxx, wuu, wuv, wuw, wux, wvu, wvv, wvw, wvx, wwu, wwv, www, wwx, wxu, wxv, wxw, wxx, xuu, xuv, xuw, xux, xvu, xvv, xvw, xvx, xwu, xwv, xww, xwx, xxu, xxv, xxw, xxx.); (2) The wvux-order (for example, the order of bar states of length p=2 and p=3 is as follows: p=2: ww, wv, wu, wx, vw, vv, vu, vx, uw, uv, uu, ux, xw, xv, xu, xx. p=3: www, wwv, wwu, wwx, wvw, wvv, wvu, wvx, wuw, wuv, wuu, wux, wxw, wxv, wxu, wxx, vww, vwv, vwu, vwx, vvw, vvv, vvu, vvx, vuw, vuv, vuu, vux, vxw, vxv, vxu, vxx, uww, uwv, uwu, uwx, uvw, uvv, uvu, uvx, uuw, uuv, uuu, uux, uxw, uxv, uxu, uxx, xww, xwv, xwu, xwx, xvw, xvv, xvu, xvx, xuw, xuv, xuu, xux, xxw, xxv, xxu, xxx). For a positive integer 1≤i≤4p, we denote by εpi and λpi the i-th bar states in the set of states of length p in the wvux- and uvwx-order, respectively (for example, ε21=ww, λ21=uu).
Bar state matrices Vp, Wp and Xp for the set of suitably adjacent bar mosaics of length p are 4p×4p matrices whose entries vij, wij, and xij are respectively given by
vij=P⟨v,εpi,λpj⟩(z), wij=P⟨w,εpi,λpj⟩(z), and xij=P⟨x,εpi,λpj⟩(z). |
εpi is the i-th state in uvwx-order, and λpj is j-th state in wvux-order. So we define εpi and λpj as the row index and column index of aij(a=v,w,x) respectively.
Lemma 2.1. The matrices Vp, Wp, and Xp can be recursively derived as follows:
Vk+1=(0k0k0k0kVk+WkVk+Wk0k0kVk+WkVk+Wk0k0k0k0k0k0k),Wk+1=(0k0kz(Vk+Xk)zVk0k0k0k0k0k0k0k0k0k0kzVk0k),Xk+1=(0k0kzVk0k0k0k0k0k0k0k0k0k0k0k0k0k), |
for k=1,⋯,p−1, with seed matrices
V1= u v w x(w0000v1100u1100x0000),W1= u v w x(w00zzv0000u0000x00z0),X1= u v w x(w00z0v0000u0000x0000). |
Remark. According to the lemma, we can also start with matrices
V0=(1) and W0=X0=(0). |
We present a detailed step-by-step process for deriving vi,j, wi,j and xi,j while p=1 before proving Lemma 2.
The matrices V1, W1 and X1 are the bar state matrices for three sets of the 1×1 mosaics C whose r-states are v, w and x, respectively. So vi,j=P⟨v,ε1i,λ1j⟩(z), wi,j=P⟨w,ε1i,λ1j⟩(z) and xi,j=P⟨x,ε1i,λ1j⟩(z).
As for the matrix V1, the row index of v2,1 is v and the column index is u, and all possible corresponding mosaic satisfying sb(C)=v and st(C)=u is I2 shown in Figure 5. Furthermore, d(I2)=0 and i⟨v,v⟩(d(I2))=1, so v2,1=P⟨v,v,u⟩(z)=1⋅z0=1. Now we write vi,j individually. Initially, we focus on the non-zero entries (v2,1 has been been given). The sets of all possible corresponding mosaics for v2,2, v3,1 and v3,2 are {I4}, {I1} and {I3} respectively. Furthermore, d(I4)=d(I1)=d(I3)=0 and i⟨v,u⟩(d(I4))=i⟨u,u⟩(d(I1))=i⟨u,v⟩(d(I3))=1, that is v2,2=v3,1=v3,2=1. There is no mosaic C satisfying sb(C)=ε1i and st(C)=λ1j, so the entries vi,j=P⟨v,ε1i,λ1j⟩(z)=0 for i∈{1,4} or j∈{3,4}.
Similarly, w1,3=P⟨w,w,w⟩(z)=w1,4=P⟨w,w,x⟩(z)=w4,3=P⟨w,x,w⟩(z)=z, because the sets of all possible corresponding mosaics for w1,3, w1,4 and w4,3 are {I5}(I8 doesn't satisfying the boundary rule), {I7}, and {I6} respectively. Then d(I5)=d(I7)=d(I6)=1 and i⟨w,w⟩(d(I5))=i⟨w,x⟩(d(I7))=i⟨x,w⟩(d(I6))=1. The elements xi,j of X1 can also be obtained similarly in this way.
Proof. We prove Lemma 2.1 by induction on k. When k=1, we can obtain the seed matrices by straightforward observations. For example, the (1, 3)-entry of W1 is
P⟨w,ε11,λ13⟩(z)=P⟨w,w,w⟩(z)=z, |
because of the following facts: (1) ε11=w in the wvux-order, (2) λ13=w in the uvwx-order, (3) sl(C)=w because of the boundary rule, (4) there exists a unique mosaic tile I5 that satisfies sl(C)=w, sr(C)=w, sb(C)=w, and st(C)=w. Moreover, d(C)=1.
Suppose that Vℓ, Wℓ, and Xℓ have been obtained recursively. Consider the matrix Wℓ+1, and divide the matrix of size 4ℓ+1×4ℓ+1 into 16 block submatrices of size 4ℓ×4ℓ. For the (1, 3)-submatrix of Wℓ+1, which is the (1, 3)-component lying in the 1st row and 3rd column in the 4×4 array of the 16 blocks, the (i,j)-entry of it is the state polynomial
P⟨w, wεℓi, wλℓj⟩(z), |
where wεℓi is the combination of two states w and εℓi, which indicates the rightmost letter of the bottom state is w (wλℓj is similar), in other words, this new state is obtained by reading the letter w before reading the state εℓi from right to left. Thus a suitably adjacent (ℓ+1)×1-mosaic can be obtained by pasting a 1×1-mosaic C′ satisfying sr(C′)=w, sb(C′)=w, and st(C′)=w to the rightmost of an ℓ×1-mosaic C satisfying sb(C)=εℓi and st(C)=λℓj. The mosaic tile C′ belongs to Y, d(C′)=1. The l-state of C′ must be w or x, which implies the r-state of the corresponding ℓ×1-mosaic C can only be v or x, as shown in Figure 8.
Thus, we have
P⟨w, wεℓi, wλℓj⟩(z)=[the (i,j)-entry of (Vℓ+Xℓ)]⋅z, |
which implies that the (1, 3)-submatrix of Wℓ+1 is (Vℓ+Xℓ)⋅z. In the same way, we can obtain the other submatrices of Wℓ+1, Vℓ+1, and Xℓ+1.
The proof of Lemma 2.1 is complete.
For the set of suitably adjacent m×q-mosaics, we obtain the state matrix Hm×q as a 4m×4m matrix where the (i,j)-entry is
hij=∑srP⟨sr,εmi,λmj⟩(z), |
which the summation is taken over all r-states sr of length q satisfying the boundary rule. Moreover, the rows and columns of the state matrix are indexed in the same way as the bar state matrix.
Lemma 2.2.
Hm×n=(Vm+Wm)n. |
Proof. We prove Lemma 2.2 by induction on n. When n=1, because of the boundary rule, the r-state of the m×1-mosaics considered can be only v or w. Thus,
Hm×1=Vm+Wm. |
Suppose that Hm×k=(Vm+Wm)k. For a suitably adjacent m×(k+1)-mosaic Cm×(k+1), by removing the topmost bar mosaic of Cm×(k+1), we can divide Cm×(k+1) into two mosaics: Cm×1 and Cm×k. Furthermore, every top boundary side edge of Cm×k and its abutting bottom boundary side edge of Cm×1 must satisfy the vertical adjacency rule. Specifically, when transitioning from st(Cm×k) to sb(Cm×1), the letter u is substituted by w, and vice versa, w is replaced by u. Please refer to Figure 9 for further clarification. Thus, there exist some r∈{1,⋯,4m} such that sb(Cm×1)=εmr and st(Cm×k)=λmr.
Let
Hm×(k+1)=(hij),Hm×k=(h′ij),and Hm×1=(h′′ij). |
The entry hij of Hm×(k+1) is the state polynomial for the set of suitably adjacent m×(k+1)-mosaics C, which can be divided into Cm×1 and Cm×k such that st(Cm×1)=st(C)=λmj, sb(Cm×k)=sb(C)=εmi, and st(Cm×k)=λmr and sb(Cm×1)=εmr for some r∈{1,⋯,4m}. So
Hij=4m∑r=1h′ir⋅h′′rj, |
which implies that
Hm×(k+1)=Hm×k⋅Hm×1=(Vm+Wm)k+1. |
The proof of Lemma 2.2 is complete.
We are now in a position to prove Theorem 1.1 by analyzing the state matrix Hm×n.
Proof of Theorem 1.1. For every suitably adjacent m×n-mosaic C which is considered in the (i,j)-entry of Hm×n, the states sr(C) and sl(C) satisfy the boundary rule. According to the one-to-one mapping, the dissociation sets in Gm×n correspond to the suitably adjacent m×n-mosaics C whose l-, r-, b-, and t-states satisfy the boundary rule. Hence the dissociation polynomial Pm×n(z) of Gm×n is the sum of all entries hij whose column index λmj and row index εmi consist of letters v and w. Therefore, Pm×n(z) can be obtained by deleting the entries hij of Hm×n associated with sb(C) and st(C) consisting of at least one letter of u and x, and then adding up the rest.
Recall that
Lm=(1100)⊗m and Rm=(0110)⊗m. |
Thus, Lm⋅Hm×n is a 1×4m matrix which is obtained from Hm×n by first deleting the rows whose row index in the wvux-order contains at least one letter of u and x, and then adding up all of the remaining non-zero entries by columns. Again, (Lm⋅Hm×n)⋅Rtm is a 1×1 matrix which is obtained from Lm⋅Hm×n by first deleting the columns whose column index in the uvwx-order contains at least one letter of u and x, and then adding up all of the remaining non-zero entries. Thus, Pm×n(z)=Lm⋅Hm×n⋅Rtm. By Lemma 2.2,
Pm×n(z)=Lm⋅(Vm+Wm)n⋅Rtm. |
We finish the proof of Theorem 1.1.
Some values of Pm×n(1) are computed by Matlab and listed in Table 1.
m=1 | m=2 | m=3 | m=4 | m=5 | m=6 | |
n=1 | 2 | 4 | 7 | 13 | 24 | 44 |
n=2 | 4 | 11 | 33 | 98 | 291 | 865 |
n=3 | 7 | 33 | 163 | 803 | 3971 | 19587 |
n=4 | 13 | 98 | 803 | 6547 | 53389 | 435027 |
n=5 | 24 | 291 | 3971 | 53389 | 720417 | 9706901 |
n=6 | 44 | 865 | 19587 | 435027 | 9706901 | 216173426 |
n=7 | 81 | 2570 | 96693 | 3546870 | 130854309 | 4817792042 |
n=8 | 149 | 7637 | 477297 | 28911809 | 1763845523 | 107354061547 |
n=9 | 274 | 22693 | 2355925 | 235681253 | 23775564134 | 2392171690343 |
n=10 | 504 | 67432 | 11629027 | 1921212987 | 320481684651 | 53305366529469 |
n=11 | 927 | 200373 | 57401721 | 15661161199 | 4319920870201 | ≈1.18781×1015 |
n=12 | 1705 | 595405 | 283338413 | 127665372304 | 58230152122968 | ≈2.64682×1016 |
n=13 | 3136 | 1769236 | 1398577069 | 1040691953095 | 784910642479634 | ≈5.89796×1017 |
n=14 | 5768 | 5257255 | 6903468049 | 8483425185009 | ≈1.05802×1016 | ≈1.31425×1019 |
n=15 | 10609 | 15621845 | 34075967931 | 69154476414585 | ≈1.42615×1017 | ≈2.92857×1020 |
n=16 | 19513 | 46420050 | 168201202963 | 563727672983607 | ≈1.92237×1018 | ≈6.52579×1021 |
n=17 | 35890 | 137936399 | 830252119477 | ≈4.59535×1015 | ≈2.59125×1019 | ≈1.45415×1023 |
n=18 | 66012 | 409875693 | 4098178655825 | ≈3.74600×1016 | ≈3.49286×1020 | ≈3.24031×1024 |
n=19 | 121415 | 1217938738 | 20228877377719 | ≈3.05363×1017 | ≈4.70819×1021 | ≈7.22045×1025 |
n=20 | 223317 | 3619084505 | 99851059281979 | ≈2.48923×1018 | ≈6.34638×1022 | ≈1.60894×1027 |
The concept of dissociation sets emerged in the 1980s as a generalization of independent sets. In the last few decades, it has gained the interest of many scholars. In this paper, we deeply discuss the enumeration problem of dissociation sets in grid graphs and use the state matrix recursion algorithm to calculate the number of dissociation sets in a grid graph.
Using this algorithm, we derive the dissociation polynomial Pm×n(z) for the grid graph Gm×n. When z=1, we can precisely calculate the number of dissociation sets in Gm×n for different values of m and n, as presented in Table 1. A notable observation from Table 1 is that as n increases, the size of the matrices obtained and analyzed in Section 2 is significantly smaller than the total number of dissociation sets in Gm×n. This demonstrates the superiority of the algorithm.
The state matrix recursion algorithm has been applied to several other enumeration problems. Due to its intuitive nature and wide applicability, the algorithm can be effectively extended to enumeration problems involving other substructures of graph.
The authors declare that they have not used Artificial Intelligence (AI) tools in the creation of this article.
This work was supported by Beijing Natural Science Foundation (No. 1232005).
The authors declare that they have no conflicts of interest.
[1] |
F. Bock, J. Pardey, L. D. Penso, D. Rautenbach, A bound on the dissociation number, J. Graph Theory, 103 (2023), 661–673. https://doi.org/10.1002/jgt.22940 doi: 10.1002/jgt.22940
![]() |
[2] |
F. Bock, J. Pardey, L. D. Penso, D. Rautenbach, Relating the independence number and the dissociation number, J. Graph Theory, 104 (2023), 320–340. https://doi.org/10.1002/jgt.22965 doi: 10.1002/jgt.22965
![]() |
[3] |
N. J. Calkin, H. S. Wilf, The number of independent sets in a grid graph, SIAM J. Discrete Math., 11 (1998), 54–60. https://doi.org/10.1137/S089548019528993X doi: 10.1137/S089548019528993X
![]() |
[4] |
S. Cheng, B. Wu, Number of maximal 2-component independent sets in forests, AIMS Math., 7 (2023), 13537–13562. https://doi.org/10.3934/math.2022748 doi: 10.3934/math.2022748
![]() |
[5] |
A. Itai, C. H. Papadimitriou, J. L. Szwarcfiter, Hamilton paths in grid graphs, SIAM. J. Comput., 11 (1982), 676–686. https://doi.org/10.1137/0211056 doi: 10.1137/0211056
![]() |
[6] |
F. Kardoš, J. Katrenič, I. Schiermeyer, On computing the minimum 3-path vertex cover and dissociation number of graphs, Theoret. Comput. Sci., 412 (2011), 7009–7017. https://doi.org/10.1016/j.tcs.2011.09.009 doi: 10.1016/j.tcs.2011.09.009
![]() |
[7] | S. Lomonaco, L. Kauffman, Quantum knots, Proc. SPIE, 5436 (2004), 268–284. https://doi.org/10.1117/12.544072 |
[8] | S. Lomonaco, L. Kauffman, Quantum knots and mosaics, Quantum Inform. Process., 7 (2008), 85–115. https://doi.org/10.1007/s11128-008-0076-7 |
[9] |
S. Oh, State matrix recursion method and monomer-dimer problem, Discrete Math., 342 (2019), 1434–1445. https://doi.org/10.1016/j.disc.2019.01.022 doi: 10.1016/j.disc.2019.01.022
![]() |
[10] |
S. Oh, Number of dominating sets in cylindric square grid graphs, Graphs Combin., 37 (2021), 1357–1372. https://doi.org/10.1007/s00373-021-02323-8 doi: 10.1007/s00373-021-02323-8
![]() |
[11] |
S. Oh, S. Lee, Enumerating independent vertex sets in grid graphs, Linear Alg. Appl., 510 (2016), 192–204. https://doi.org/10.1016/j.laa.2016.08.025 doi: 10.1016/j.laa.2016.08.025
![]() |
[12] |
Y. Orlovich, A. Dolgui, G. Finke, V. Gordon, F. Werner, The complexity of dissociation set problems in graphs, Discrete Appl. Math., 159 (2011), 1352–1366. https://doi.org/10.1016/j.dam.2011.04.023 doi: 10.1016/j.dam.2011.04.023
![]() |
[13] |
W. Sun, S. Li, On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number, Taiwanese J. Math., 27 (2023), 647–683. https://doi.org/10.11650/tjm/230204 doi: 10.11650/tjm/230204
![]() |
[14] |
G. L. Thompson, Hamiltonian tours and paths in rectangular lattice graphs, Math. Mag., 50 (1977), 147–150. https://doi.org/10.1080/0025570X.1977.11976635 doi: 10.1080/0025570X.1977.11976635
![]() |
[15] |
J. Tu, Z. Zhang, Y. Shi, The maximum number of maximum dissociation sets in trees, J. Graph Theory, 96 (2021), 472–489. https://doi.org/10.1002/jgt.22627 doi: 10.1002/jgt.22627
![]() |
[16] |
M. Xiao, S. Kou, Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems, Theoret. Comput. Sci., 657 (2017), 86–97. https://doi.org/10.1016/j.tcs.2016.04.043 doi: 10.1016/j.tcs.2016.04.043
![]() |
[17] |
M. Yannakakis, Node-deletion problems on bipartite graphs, SIAM J. Comput., 10 (1981), 310–327. https://doi.org/10.1137/0210022 doi: 10.1137/0210022
![]() |
[18] |
L. Zhang, J. Tu, C. Xin, Maximum dissociation sets in subcubic trees, J. Comb. Optim., 46 (2023), 8. https://doi.org/10.1007/s10878-023-01076-9 doi: 10.1007/s10878-023-01076-9
![]() |
1. | Bo-Jun Yuan, Ni Yang, Hong-Yan Ge, Shi-Cai Gong, The number of dissociation sets in connected graphs, 2025, 373, 0166218X, 196, 10.1016/j.dam.2025.04.057 |
m=1 | m=2 | m=3 | m=4 | m=5 | m=6 | |
n=1 | 2 | 4 | 7 | 13 | 24 | 44 |
n=2 | 4 | 11 | 33 | 98 | 291 | 865 |
n=3 | 7 | 33 | 163 | 803 | 3971 | 19587 |
n=4 | 13 | 98 | 803 | 6547 | 53389 | 435027 |
n=5 | 24 | 291 | 3971 | 53389 | 720417 | 9706901 |
n=6 | 44 | 865 | 19587 | 435027 | 9706901 | 216173426 |
n=7 | 81 | 2570 | 96693 | 3546870 | 130854309 | 4817792042 |
n=8 | 149 | 7637 | 477297 | 28911809 | 1763845523 | 107354061547 |
n=9 | 274 | 22693 | 2355925 | 235681253 | 23775564134 | 2392171690343 |
n=10 | 504 | 67432 | 11629027 | 1921212987 | 320481684651 | 53305366529469 |
n=11 | 927 | 200373 | 57401721 | 15661161199 | 4319920870201 | ≈1.18781×1015 |
n=12 | 1705 | 595405 | 283338413 | 127665372304 | 58230152122968 | ≈2.64682×1016 |
n=13 | 3136 | 1769236 | 1398577069 | 1040691953095 | 784910642479634 | ≈5.89796×1017 |
n=14 | 5768 | 5257255 | 6903468049 | 8483425185009 | ≈1.05802×1016 | ≈1.31425×1019 |
n=15 | 10609 | 15621845 | 34075967931 | 69154476414585 | ≈1.42615×1017 | ≈2.92857×1020 |
n=16 | 19513 | 46420050 | 168201202963 | 563727672983607 | ≈1.92237×1018 | ≈6.52579×1021 |
n=17 | 35890 | 137936399 | 830252119477 | ≈4.59535×1015 | ≈2.59125×1019 | ≈1.45415×1023 |
n=18 | 66012 | 409875693 | 4098178655825 | ≈3.74600×1016 | ≈3.49286×1020 | ≈3.24031×1024 |
n=19 | 121415 | 1217938738 | 20228877377719 | ≈3.05363×1017 | ≈4.70819×1021 | ≈7.22045×1025 |
n=20 | 223317 | 3619084505 | 99851059281979 | ≈2.48923×1018 | ≈6.34638×1022 | ≈1.60894×1027 |
m=1 | m=2 | m=3 | m=4 | m=5 | m=6 | |
n=1 | 2 | 4 | 7 | 13 | 24 | 44 |
n=2 | 4 | 11 | 33 | 98 | 291 | 865 |
n=3 | 7 | 33 | 163 | 803 | 3971 | 19587 |
n=4 | 13 | 98 | 803 | 6547 | 53389 | 435027 |
n=5 | 24 | 291 | 3971 | 53389 | 720417 | 9706901 |
n=6 | 44 | 865 | 19587 | 435027 | 9706901 | 216173426 |
n=7 | 81 | 2570 | 96693 | 3546870 | 130854309 | 4817792042 |
n=8 | 149 | 7637 | 477297 | 28911809 | 1763845523 | 107354061547 |
n=9 | 274 | 22693 | 2355925 | 235681253 | 23775564134 | 2392171690343 |
n=10 | 504 | 67432 | 11629027 | 1921212987 | 320481684651 | 53305366529469 |
n=11 | 927 | 200373 | 57401721 | 15661161199 | 4319920870201 | ≈1.18781×1015 |
n=12 | 1705 | 595405 | 283338413 | 127665372304 | 58230152122968 | ≈2.64682×1016 |
n=13 | 3136 | 1769236 | 1398577069 | 1040691953095 | 784910642479634 | ≈5.89796×1017 |
n=14 | 5768 | 5257255 | 6903468049 | 8483425185009 | ≈1.05802×1016 | ≈1.31425×1019 |
n=15 | 10609 | 15621845 | 34075967931 | 69154476414585 | ≈1.42615×1017 | ≈2.92857×1020 |
n=16 | 19513 | 46420050 | 168201202963 | 563727672983607 | ≈1.92237×1018 | ≈6.52579×1021 |
n=17 | 35890 | 137936399 | 830252119477 | ≈4.59535×1015 | ≈2.59125×1019 | ≈1.45415×1023 |
n=18 | 66012 | 409875693 | 4098178655825 | ≈3.74600×1016 | ≈3.49286×1020 | ≈3.24031×1024 |
n=19 | 121415 | 1217938738 | 20228877377719 | ≈3.05363×1017 | ≈4.70819×1021 | ≈7.22045×1025 |
n=20 | 223317 | 3619084505 | 99851059281979 | ≈2.48923×1018 | ≈6.34638×1022 | ≈1.60894×1027 |