Research article

Enumeration of dissociation sets in grid graphs

  • Received: 31 January 2024 Revised: 09 April 2024 Accepted: 15 April 2024 Published: 24 April 2024
  • MSC : 05C30, 05C69

  • 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

    Related Papers:

    [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 xpy(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 m1, and j is an integer and ranges from 0 to n1. The edges of the graph connect pairs of vertices (i,j) and (i,j) that satisfy the condition |ii|+|jj|=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.

    Figure 1.  The grid graph G6×6 and a dissociation set in G6×6.

    We illustrate all the dissociation sets in Gm×n for 1mn2 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.

    Figure 2.  The four dissociation sets in G1×2.

    When m=n=2, Figure 3 illustrates all eleven dissociation sets in G2×2.

    Figure 3.  The 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 Am 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,,m1, starting with

    V0=(1),W0=X0=(0).

    Theorem 1.1. Let Rtm be the transpose of Rm. Then

    Pm×n(z)=Lm(Vm+Wm)nRtm.

    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)2Rt2=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 I1I9 that are shown in Figure 4.

    Figure 4.  Nine mosaic tiles, and the sets N and Y.

    The mosaic corresponding to the dissociation set depicted in Figure 1 is illustrated in Figure 5.

    Figure 5.  The corresponding mosaic for the dissociation set shown in Figure 1.

    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.

    Figure 6.  The horizontal adjacency rule and the vertical adjacency rule.

    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 pm and qn 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.

    Figure 7.  A suitably adjacent mosaic C with st(C)=vwvw, sb(C)=wvwv, sr(C)=vvw, and sl(C)=wvv.

    Given three sequences sr, sb and st composed of the letters u, v, w and x, we obtain the state polynomial

    Psr,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 isb,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 1i4p, 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=Pv,εpi,λpj(z), wij=Pw,εpi,λpj(z), and xij=Px,ε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,,p1, 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=Pv,ε1i,λ1j(z), wi,j=Pw,ε1i,λ1j(z) and xi,j=Px,ε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 iv,v(d(I2))=1, so v2,1=Pv,v,u(z)=1z0=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 iv,u(d(I4))=iu,u(d(I1))=iu,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=Pv,ε1i,λ1j(z)=0 for i{1,4} or j{3,4}.

    Similarly, w1,3=Pw,w,w(z)=w1,4=Pw,w,x(z)=w4,3=Pw,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 iw,w(d(I5))=iw,x(d(I7))=ix,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

    Pw,ε11,λ13(z)=Pw,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

    Pw, 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

    Pw, wεi, wλj(z)=[the (i,j)-entry of (V+X)]z,
    Figure 8.  Expand the bar mosaic ()×1-mosaic C to the bar mosaic (+1)×1-mosaic.

    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=srPsr,ε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.

    Figure 9.  A suitably adjacent m×(k+1)-mosaic Cm×(k+1).

    Let

    Hm×(k+1)=(hij),Hm×k=(hij),and Hm×1=(hij).

    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=4mr=1hirhrj,

    which implies that

    Hm×(k+1)=Hm×kHm×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, LmHm×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, (LmHm×n)Rtm is a 1×1 matrix which is obtained from LmHm×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)=LmHm×nRtm. By Lemma 2.2,

    Pm×n(z)=Lm(Vm+Wm)nRtm.

    We finish the proof of Theorem 1.1.

    Some values of Pm×n(1) are computed by Matlab and listed in Table 1.

    Table 1.  Pm×n(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

     | Show Table
    DownLoad: CSV

    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
  • This article has been cited by:

    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
  • Reader Comments
  • © 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(1049) PDF downloads(41) Cited by(1)

Figures and Tables

Figures(9)  /  Tables(1)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog