Enumeration of dissociation sets in grid graphs

被引:1
作者
Zhou, Wenke [1 ]
Chen, Guo [1 ]
Deng, Hongzhi [1 ]
Tu, Jianhua [1 ]
机构
[1] Beijing Technol & Business Univ, Sch Math & Stat, Beijing 100048, Peoples R China
来源
AIMS MATHEMATICS | 2024年 / 9卷 / 06期
基金
北京市自然科学基金;
关键词
dissociation sets; enumeration; grid graphs; state matrix recursion algorithm; 3-PATH VERTEX COVER; NUMBER;
D O I
10.3934/math.2024721
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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.
引用
收藏
页码:14899 / 14912
页数:14
相关论文
共 50 条
[41]   Enumeration of graphs with the same Ihara zeta function [J].
Setyadi, A. ;
Storm, C. K. .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2013, 438 (01) :564-572
[42]   Enumeration of unlabelled bicolored graphs by degree parities [J].
Tazawa, S ;
Shirakura, T .
JOURNAL OF STATISTICAL PLANNING AND INFERENCE, 1997, 58 (01) :193-206
[43]   ASYMPTOTIC ENUMERATION AND LIMIT LAWS OF PLANAR GRAPHS [J].
Gimenez, Omer ;
Noy, Marc .
JOURNAL OF THE AMERICAN MATHEMATICAL SOCIETY, 2009, 22 (02) :309-329
[44]   Random Generation and Enumeration of Proper Interval Graphs [J].
Saitoh, Toshiki ;
Yamanaka, Katsuhisa ;
Kiyomi, Masashi ;
Uehara, Ryuhei .
WALCOM: ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2009, 5431 :177-+
[45]   Enumeration of labeled block-cactus graphs [J].
Voblyi V.A. ;
Meleshko A.K. .
Journal of Applied and Industrial Mathematics, 2014, 8 (3) :422-427
[46]   Random generation and enumeration of bipartite permutation graphs [J].
Saitoh, Toshiki ;
Otachi, Yota ;
Yamanaka, Katsuhisa ;
Uehara, Ryuhei .
JOURNAL OF DISCRETE ALGORITHMS, 2012, 10 :84-97
[47]   Independent sets in graphs with triangles [J].
Hofmeister, T ;
Lefmann, H .
INFORMATION PROCESSING LETTERS, 1996, 58 (05) :207-210
[48]   Counting independent sets in graphs [J].
Samotij, Wojciech .
EUROPEAN JOURNAL OF COMBINATORICS, 2015, 48 :5-18
[49]   INDEPENDENT SETS IN POLARITY GRAPHS [J].
Tait, Michael ;
Timmons, Craig .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2016, 30 (04) :2115-2129
[50]   Enumeration of labeled geodetic graphs with small cyclomatic number [J].
Voblyi, V. A. .
MATHEMATICAL NOTES, 2017, 101 (5-6) :790-794