zbMATH — the first resource for mathematics

Nonseparating independent sets of Cartesian product graphs. (English) Zbl 1434.05106
Summary: 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.
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
Full Text: DOI Euclid
[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.