|
|
几类特殊图的孤立数
|
Abstract:
图的孤立集是顶点集的子集使得图中减去它的闭领域后剩下部分构成孤立点集，图的孤立数是图中最小孤立集的基数。孤立数相关概念在日常生活中起着重要的作用，如在流行病学中，可以用来评估孤立措施的有效性；在网络安全领域，孤立数的概念可以用于识别和孤立异常行为或潜在的威胁等。本文确定友谊图、风车图、轮图、风筝图以及杠铃图等几类特殊图的孤立数，并讨论平面格子图的孤立数。
The isolation set of a graph is a subset of the vertex set such that the remaining part after subtracting its closed neighborhood from the graph constitutes an isolated vertex set, and the isolation number of a graph is the cardinality of the smallest isolated set in the graph. The concept of isolation numbers plays an important role in daily life, such as in epidemiology, where it can be used to evaluate the effectiveness of isolation measures; in the field of cybersecurity, the concept of isolation numbers can be used to identify and isolate abnormal behavior or potential threats. This article determines the isolation numbers of several special types of graphs, such as friendship graphs, windmill graphs, wheel graphs, kite graphs, and barbell graphs, and discusses the isolation numbers of plane grid graphs.
| [1] | Caro, Y. and Hansberg, A. (2017) Partial Domination—The Isolation Number of a Graph. Filomat, 31, 3925-3944. https://doi.org/10.2298/fil1712925c |
| [2] | Lemańska, M., Souto-Salorio, M.J., Dapena, A. and Vazquez-Araujo, F.J. (2021) Isolation Number versus Domination Number of Trees. Mathematics, 9, Article 1325. https://doi.org/10.3390/math9121325 |
| [3] | Lemańska, M., Mora, M. and Souto-Salorio, M.J. (2024) Graphs with Isolation Number Equal to One Third of the Order. Discrete Mathematics, 347, Article ID: 113903. https://doi.org/10.1016/j.disc.2024.113903 |
| [4] | Boyer, G. and Goddard, W. (2024) Disjoint Isolating Sets and Graphs with Maximum Isolation Number. Discrete Applied Mathematics, 356, 110-116. https://doi.org/10.1016/j.dam.2024.05.022 |
| [5] | 张刚. 图的孤立[D]: [硕士学位论文]. 乌鲁木齐: 新疆大学, 2021. |
| [6] | Borg, P., Fenech, K. and Kaemawichanurat, P. (2020) Isolation of k-Cliques. Discrete Mathematics, 343, Article ID: 111879. https://doi.org/10.1016/j.disc.2020.111879 |
| [7] | Borg, P., Fenech, K. and Kaemawichanurat, P. (2022) Isolation of k-Cliques II. Discrete Mathematics, 345, Article ID: 112641. https://doi.org/10.1016/j.disc.2021.112641 |
| [8] | Wei, X., Zhang, G. and Zhao, B. (2023) On the C4-Isolation Number of a Graph. arXiv: 2310.17337. |
| [9] | Cui, Q. and Zhang, J. (2023) A Sharp Upper Bound on the Cycle Isolation Number of Graphs. Graphs and Combinatorics, 39, Article No. 117. https://doi.org/10.1007/s00373-023-02717-w |
| [10] | Zhang, G. and Wu, B. (2024) On the Cycle Isolation Number of Triangle-Free Graphs. Discrete Mathematics, 347, Article ID: 114190. https://doi.org/10.1016/j.disc.2024.114190 |
| [11] | Chen, J. and Xu, S. (2023) P5-Isolation in Graphs. Discrete Applied Mathematics, 340, 331-349. https://doi.org/10.1016/j.dam.2023.07.018 |
| [12] | Zhang, G. and Wu, B. (2024) k-Isolation in Graphs. Discrete Applied Mathematics, 357, 99-111. https://doi.org/10.1016/j.dam.2024.06.005 |
