×

Isolation of squares in graphs. (English) Zbl 07919612

Summary: Given a set \(\mathcal{F}\) of graphs, we call a copy of a graph in \(\mathcal{F}\) an \(\mathcal{F} \)-graph. The \(\mathcal{F} \)-isolation number of a graph \(G\), denoted by \(\iota(G, \mathcal{F})\), is the size of a smallest subset \(D\) of the vertex set \(V(G)\) such that the closed neighbourhood of \(D\) intersects the vertex sets of the \(\mathcal{F} \)-graphs contained by \(G\) (equivalently, \(G - N [D]\) contains no \(\mathcal{F} \)-graph). Thus, \( \iota(G, \{ K_1 \})\) is the domination number of \(G\). P. Borg [Graphs Comb. 36, No. 3, 631–637 (2020; Zbl 1439.05117)] showed that if \(\mathcal{F}\) is the set of cycles and \(G\) is a connected \(n\)-vertex graph that is not a triangle, then \(\iota(G, \mathcal{F}) \leq \lfloor \frac{ n}{ 4} \rfloor \). This bound is attainable for every \(n\) and solved a problem of Y. Caro and A. Hansberg [Filomat 31, No. 12, 3925–3944 (2017; Zbl 1488.05367)]. A question that arises immediately is how much smaller an upper bound can be if \(\mathcal{F} = \{ C_k \}\) for some \(k \geq 3\), where \(C_k\) is a cycle of length \(k\). The problem is to determine the smallest real number \(c_k\) (if it exists) such that for some finite set \(\mathcal{E}_k\) of graphs, \( \iota(G, \{ C_k \}) \leq c_k | V(G) |\) for every connected graph \(G\) that is not an \(\mathcal{E}_k\)-graph. The above-mentioned result yields \(c_3 = \frac{ 1}{ 4}\) and \(\mathcal{E}_3 = \{ C_3 \} \). The second author also showed that if \(k \geq 5\) and \(c_k\) exists, then \(c_k \geq \frac{ 2}{ 2 k + 1} \). We prove that \(c_4 = \frac{ 1}{ 5}\) and determine \(\mathcal{E}_4\), which consists of three 4-vertex graphs and six 9-vertex graphs. The 9-vertex graphs in \(\mathcal{E}_4\) were fully determined by means of a computer program. A method that has the potential of yielding similar results is introduced.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C38 Paths and cycles

References:

[1] Borg, P., Isolation of cycles, Graphs Comb., 36, 631-637, 2020 · Zbl 1439.05117
[2] Borg, P., Isolation of connected graphs, Discrete Appl. Math., 339, 154-165, 2023 · Zbl 1528.05037
[3] Borg, P., Isolation of regular graphs, stars and k-chromatic graphs · Zbl 07899992
[4] Borg, P.; Fenech, K.; Kaemawichanurat, P., Isolation of k-cliques, Discrete Math., 343, Article 111879 pp., 2020 · Zbl 1440.05157
[5] Borg, P.; Fenech, K.; Kaemawichanurat, P., Isolation of k-cliques II, Discrete Math., 345, Article 112641 pp., 2022 · Zbl 1489.05109
[6] Borg, P.; Kaemawichanurat, P., Partial domination of maximal outerplanar graphs, Discrete Appl. Math., 283, 306-314, 2020 · Zbl 1442.05149
[7] Borg, P.; Kaemawichanurat, P., Extensions of the Art Gallery Theorem, Ann. Comb., 27, 31-50, 2023 · Zbl 1511.05176
[8] Campos, C. N.; Wakabayashi, Y., On dominating sets of maximal outerplanar graphs, Discrete Appl. Math., 161, 330-335, 2013 · Zbl 1254.05136
[9] Caro, Y.; Hansberg, A., Partial domination - the isolation number of a graph, Filomat, 31, 12, 3925-3944, 2017 · Zbl 1488.05367
[10] Chvátal, V., A combinatorial theorem in plane geometry, J. Comb. Theory, Ser. B, 18, 39-41, 1975 · Zbl 0278.05028
[11] Cockayne, E. J., Domination of Undirected Graphs - A Survey, Lecture Notes in Mathematics, vol. 642, 141-147, 1978, Springer · Zbl 0384.05052
[12] Cockayne, E. J.; Hedetniemi, S. T., Towards a theory of domination in graphs, Networks, 7, 247-261, 1977 · Zbl 0384.05051
[13] Dorfling, M.; Hattingh, J. H.; Jonck, E., Total domination in maximal outerplanar graphs II, Discrete Appl. Math., 339, 1180-1188, 2016 · Zbl 1328.05140
[14] Dorfling, M.; Hattingh, J. H.; Jonck, E., Total domination in maximal outerplanar graphs, Discrete Appl. Math., 217, 506-511, 2017 · Zbl 1358.05213
[15] Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Fundamentals of Domination in Graphs, 1998, Marcel Dekker, Inc.: Marcel Dekker, Inc. New York · Zbl 0890.05002
[16] (Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Domination in Graphs: Advanced Topics, 1998, Marcel Dekker, Inc.: Marcel Dekker, Inc. New York) · Zbl 0883.00011
[17] (Hedetniemi, S. T.; Laskar, R. C., Topics on Domination. Topics on Domination, Annals of Discrete Mathematics, vol. 48, 1991, North-Holland Publishing Co.: North-Holland Publishing Co. Amsterdam). (Hedetniemi, S. T.; Laskar, R. C., Topics on Domination. Topics on Domination, Annals of Discrete Mathematics, vol. 48, 1991, North-Holland Publishing Co.: North-Holland Publishing Co. Amsterdam), Discrete Math., 86, 1-3, 1990, Reprint of
[18] Hedetniemi, S. T.; Laskar, R. C., Bibliography on domination in graphs and some basic definitions of domination parameters, Discrete Math., 86, 257-277, 1990 · Zbl 0733.05076
[19] Henning, M. A.; Kaemawichanurat, P., Semipaired domination in maximal outerplanar graphs, J. Comb. Optim., 38, 911-926, 2019 · Zbl 1435.05155
[20] Horvát, S.; Podkalicki, J.; Csárdi, G.; Nepusz, T.; Traag, V.; Zanini, F.; Noom, D., IGraph/M: graph theory and network analysis for Mathematica, J. Open Sour. Softw., 8, 81, 4899, 2023
[21] Lemańska, M.; Zuazua, R.; Żyliński, P., Total dominating sets in maximal outerplanar graphs, Graphs Comb., 33, 991-998, 2017 · Zbl 1373.05144
[22] Li, Z.; Zhu, E.; Shao, Z.; Xu, J., On dominating sets of maximal outerplanar and planar graphs, Discrete Appl. Math., 198, 164-169, 2016 · Zbl 1327.05263
[23] Matheson, L. R.; Tarjan, R. E., Dominating sets in planar graphs, Eur. J. Comb., 17, 565-568, 1996 · Zbl 0862.05032
[24] McKay, B., 2023
[25] Ore, O., Theory of Graphs, American Mathematical Society Colloquium Publications, vol. 38, 1962, American Mathematical Society: American Mathematical Society Providence, R.I. · Zbl 0105.35401
[26] Tokunaga, S., Dominating sets of maximal outerplanar graphs, Discrete Appl. Math., 161, 3097-3099, 2013 · Zbl 1287.05109
[27] Tokunaga, S.; Jiarasuksakun, T.; Kaemawichanurat, P., Isolation number of maximal outerplanar graphs, Discrete Appl. Math., 267, 215-218, 2019 · Zbl 1420.05137
[28] West, D. B., Introduction to Graph Theory, 1996, Prentice Hall · Zbl 0845.05001
[29] Yan, J., Isolation of the diamond graph, Bull. Malays. Math. Sci. Soc., 45, 1169-1181, 2022 · Zbl 1487.05201
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.