Nonseparating independent sets of Cartesian product graphs.

*(English)*Zbl 1434.05106Summary: A set of vertices \(S\) of a connected graph \(G\) is a nonseparating independent set if \(S\) is independent and \(G-S\) is connected. The nsis number \(\mathcal{Z}(G)\) is the maximum cardinality of a nonseparating independent set of \(G\). It is well known that computing the nsis number of graphs is NP-hard even when restricted to \(4\)-regular graphs. In this paper, we first present a new sufficient and necessary condition to describe the nsis number. Then, we completely solve the problem of counting the nsis number of hypercubes \(Q_n\) and Cartesian product of two cycles \(C_m \square C_n\), respectively. We show that \(\mathcal{Z}(Q_n) = 2^{n-2}\) for \(n \geq 2\), and \(\mathcal{Z}(C_m \square C_n) = n + \lfloor (n+2)/4 \rfloor\) if \(m = 4, m + \lfloor (m+2)/4 \rfloor\) if \(n = 4\) and \(\lfloor mn/3 \rfloor\) otherwise. Moreover, we find a maximum nonseparating independent set of \(Q_n\) and \(C_m \square C_n\), respectively.

##### MSC:

05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |

05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |

05C76 | Graph operations (line graphs, products, etc.) |

05C05 | Trees |

05C40 | Connectivity |

##### Keywords:

nonseparating independent set; connected vertex cover; hypercube; Cartesian product of two cycles; spanning tree; Xuong-tree##### References:

[1] | B. Escoffier, L. Gourvès and J. Monnot, Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs, J. Discrete Algorithms 8 (2010), no. 1, 36-49. · Zbl 1214.05162 |

[2] | H. Fernau and D. F. Manlove, Vertex and edge covers with clustering properties: complexity and algorithms, J. Discrete Algorithms 7 (2009), no. 2, 149-167. · Zbl 1187.68342 |

[3] | M. R. Garey and D. S. Johnson, The rectilinear Steiner tree problem is NP-complete, SIAM J. Appl. Math. 32 (1977), no. 4, 826-834. · Zbl 0396.05009 |

[4] | J. L. Gross and T. W. Tucker, Topological Graph Theory, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, New York, 1987. |

[5] | Y. Huang and Y. Liu, Maximum genus and maximum nonseparating independent set of a \(3\)-regular graph, Discrete Math. 176 (1997), no. 1-3, 149-158. · Zbl 0888.05020 |

[6] | Y. Li, Z. Yang and W. Wang, Complexity and algorithms for the connected vertex cover problem in \(4\)-regular graphs, Appl. Math. Comput. 301 (2017), 107-114. · Zbl 1411.05247 |

[7] | S. Long and H. Ren, The decycling number and maximum genus of cubic graphs, J. Graph Theory 88 (2018), no. 3, 375-384. · Zbl 1393.05166 |

[8] | B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2001. |

[9] | H. Moser, Exact algorithms for generalizations of vertex cover, Fakulätfür Mathematik und Informatik, Friedrich-Schiller-Universität Jena, 2005 Mas-ters thesis. |

[10] | D. A. Pike and Y. Zou, Decycling Cartesian products of two cycles, SIAM J. Discrete Math. 19 (2005), no. 3, 651-663. · Zbl 1096.05030 |

[11] | S. Ueno, Y. Kajitani and S. Gotoh, On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three, Discrete Math. 72 (1988), no. 1-3, 355-360. · Zbl 0678.05026 |

[12] | T. Wanatabe, S. Kajita and K. Onaga, Vertex covers and connected vertex covers in \(3\)-connected graphs, in: 1991., IEEE International Sympoisum on Circuits and Systems, (1991), 1017-1020. |

[13] | N. H. Xuong, How to determine the maximum genus of a graph, J. Combin. Theory Ser. B 26 (1979), no. 2, 217-225. · Zbl 0403.05035 |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.