|
|
单和双圈图k-孤立数的上确界
|
Abstract:
对一个自然数
,若简单无向图
的顶点子集
满足条件:减去
的闭邻域后得到的图
不含
阶的星图
作为子图,则
被称为
的一个
-孤立集。图
的最小一个
-孤立集
的阶数被称为图
的
-孤立数。本文得到了单和双圈图的
-孤立数的上确界。
For a natural number k, a vertex subset D of a simple undirected graph G satisfies the condition that the graph
obtained by removing the closed neighborhood of D does not contain the star graph
of order
as a subgraph, then it is calwled a k-isolating set of the graph. The minimum order of such a k-isolating set in a
| [1] | Ore, O. (1962) Theory of Graphs. American Mathematical Society. https://doi.org/10.1090/coll/038 |
| [2] | Payan, C. and Xuong, N.H. (1982) Domination‐Balanced Graphs. Journal of Graph Theory, 6, 23-32. https://doi.org/10.1002/jgt.3190060104 |
| [3] | Haynes, T.W., Hedetniemi, S.T. and Slater, P.J. (1998) Fundamentals of Domination in Graphs. Marcel Dekker. |
| [4] | Caro, Y. and Hansberg, A. (2017) Partial Domination—The Isolation Number of a Graph. Filomat, 31, 3925-3944. https://doi.org/10.2298/fil1712925c |
| [5] | 张刚. 图的K1,2孤立[D]: [硕士学位论文]. 乌鲁木齐: 新疆大学, 2021. |
| [6] | Lewis, J.R., Hedetniemi, S.T., Haynes, T.W. and Fricke, G.H. (2010) Vertex-Edge Domination. Utilitas Mathematica, 81, 193-213. |
| [7] | Canales, S., Hernández, G., Martins, M. and Matos, I. (2015) Distance Domination, Guarding and Covering of Maximal Outerplanar Graphs. Discrete Applied Mathematics, 181, 41-49. https://doi.org/10.1016/j.dam.2014.08.040 |
| [8] | Cozzens, M.B. and Wu, S.-S.Y. (1996) Vertex-Neighbor-Integrity of Trees. Ars Combinatoria, 43, 169-180. |
| [9] | Żyliński, P. (2019) Vertex-Edge Domination in Graphs. Aequationes Mathematicae, 93, 735-742. https://doi.org/10.1007/s00010-018-0609-9 |
| [10] | 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 113903. https://doi.org/10.1016/j.disc.2024.113903 |
| [11] | 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 |
| [12] | Huang, Y., Zhang, G. and Jin, X. (2026) New Results on the 1-Isolation Number of Graphs without Short Cycles. Discrete Applied Mathematics, 379, 222-235. https://doi.org/10.1016/j.dam.2025.08.033 |
| [13] | Bartolo, K., Borg, P. and Scieluna, D. (2024) Solution to a 3-Path Isolation Problem for Subcubic Graphs. arXiv:2501.00419. |
| [14] | Fink, J.F., Jacobson, M.S., Kinch, L.F. and Roberts, J. (1985) On Graphs Having Domination Number Half Their Order. Periodica Mathematica Hungarica, 16, 287-293. https://doi.org/10.1007/bf01848079 |