A set $ S \subseteq V(G) $ of a graph $ G $ is $ k $-independent if every vertex of $ S $ has at most $ k-1 $ neighbors in $ S $, where $ k \in \mathbb{Z}^+ $. The $ k $-independence number $ \alpha_k(G) $ is the maximum cardinality of a $ k $-independent set of $ G $; determining it is $ \mathcal{NP} $-hard for general graphs. We study this parameter on $ P_4 $-tidy graphs, a class that properly contains cographs and $ P_4 $-sparse graphs. Exploiting the structural decomposition of $ P_4 $-tidy graphs, we derive closed formulas for $ \alpha_k $ under disjoint union and join, as well as for all types of spiders and quasi-spiders, expressed in terms of the $ k $-independence numbers of the graphs arising in the decomposition. These formulas yield a dynamic programming algorithm over the decomposition tree that computes $ \alpha_k(G) $ in $ O(k^3n + |E(G)|) $ time, with $ k $ part of the input. Although polynomial-time solvability on this class already follows from general algorithms for graphs of bounded clique-width, those algorithms run in $ n^{O(w)} $ time for clique-width $ w $ and provide no explicit formulas. Our results extend the closed formulas and the efficient algorithm previously known for $ P_4 $-sparse graphs to the full class of $ P_4 $-tidy graphs.
Citation: Márcia R. Cappelle, Luan César D. Carvalho. $ k $-Independence in $ P_4 $-tidy graphs[J]. AIMS Mathematics, 2026, 11(11): 37133-37157. doi: 10.3934/math.20261435
A set $ S \subseteq V(G) $ of a graph $ G $ is $ k $-independent if every vertex of $ S $ has at most $ k-1 $ neighbors in $ S $, where $ k \in \mathbb{Z}^+ $. The $ k $-independence number $ \alpha_k(G) $ is the maximum cardinality of a $ k $-independent set of $ G $; determining it is $ \mathcal{NP} $-hard for general graphs. We study this parameter on $ P_4 $-tidy graphs, a class that properly contains cographs and $ P_4 $-sparse graphs. Exploiting the structural decomposition of $ P_4 $-tidy graphs, we derive closed formulas for $ \alpha_k $ under disjoint union and join, as well as for all types of spiders and quasi-spiders, expressed in terms of the $ k $-independence numbers of the graphs arising in the decomposition. These formulas yield a dynamic programming algorithm over the decomposition tree that computes $ \alpha_k(G) $ in $ O(k^3n + |E(G)|) $ time, with $ k $ part of the input. Although polynomial-time solvability on this class already follows from general algorithms for graphs of bounded clique-width, those algorithms run in $ n^{O(w)} $ time for clique-width $ w $ and provide no explicit formulas. Our results extend the closed formulas and the efficient algorithm previously known for $ P_4 $-sparse graphs to the full class of $ P_4 $-tidy graphs.
| [1] |
J. F. Fink, M. S. Jacobson, $n$-Domination in graphs, In: Graph theory with applications to algorithms and computer science, New York: John Wiley and Sons, 1985,282–300. |
| [2] |
M. S. Jacobson, K. Peters, Complexity questions for $n$-domination and related parameters, Proceedings of the 18th Manitoba Conference on Numerical Mathematics and Computing, Winnipeg, Canada, 1989, 7–22. |
| [3] |
M. Blidia, M. Chellali, O. Favaron, N. Meddah, Maximal $k$-independent sets in graphs, Discuss. Math. Graph T., 28 (2008), 151–163. https://doi.org/10.7151/dmgt.1398 doi: 10.7151/dmgt.1398
|
| [4] |
Y. Caro, A. Hansberg, New approach to the $k$-independence number of a graph, Electron. J. Comb., 20 (2013), #P33. https://doi.org/10.37236/2646 |
| [5] |
M. Chellali, O. Favaron, A. Hansberg, L. Volkmann, $k$-Domination and $k$-independence in graphs: A survey, Graph. Combinator., 28 (2012), 1–55. https://doi.org/10.1007/s00373-011-1040-3 doi: 10.1007/s00373-011-1040-3
|
| [6] |
M. Cappelle, E. Coelho, O. Mortosa, J. Nascimento, Complexity results on $k$-independence in some graph products, RAIRO-Oper. Res., 58 (2024), 2367–2378. https://doi.org/10.1051/ro/2024098 doi: 10.1051/ro/2024098
|
| [7] |
C. T. Hoàng, Perfect graphs, PhD thesis, McGill University, Montreal, 1985. |
| [8] |
V. Giakoumakis, F. Roussel, H. Thuillier, On $P_4$-tidy graphs, Discrete Math. Theor., 1 (1997), 17–41. https://doi.org/10.46298/dmtcs.232 |
| [9] |
B. Brešar, T. Kos, G. Nasini, P. Torres, Total dominating sequences in trees, split graphs, and under modular decomposition, Discrete Optim., 28 (2018), 16–30. https://doi.org/10.1016/j.disopt.2017.10.002 doi: 10.1016/j.disopt.2017.10.002
|
| [10] |
P. Torres, Grundy double domination number: bounds, graph operations, and efficient computation for $P_4$-tidy graphs, Bull. Malays. Math. Sci. Soc., 49 (2026), 52. https://doi.org/10.1007/s40840-026-02055-z doi: 10.1007/s40840-026-02055-z
|
| [11] |
S. Klein, C. P. de Mello, A. Morgana, Recognizing well covered graphs of families with special $P_4$-components, Graph. Combinator., 29 (2013), 553–567. https://doi.org/10.1007/s00373-011-1123-1 doi: 10.1007/s00373-011-1123-1
|
| [12] |
M. R. Cappelle, E. Coelho, L. R. Foulds, H. J. Longo, Open-independent, open-locating-dominating sets: structural aspects of some classes of graphs, Discrete Math. Theor., 24 (2022), #5. https://doi.org/10.46298/dmtcs.8440 |
| [13] |
L. C. D. Carvalho, M. R. Cappelle, $k$-Independência em grafos $P_4$-esparsos, Anais do LIV Simpósio Brasileiro de Pesquisa Operacional, 54 (2022), 152990. |
| [14] |
B. Courcelle, J. A. Makowsky, U. Rotics, Linear time solvable optimization problems on graphs of bounded clique-width, Theor. Comput. Syst., 33 (2000), 125–150. https://doi.org/10.1007/s002249910009 doi: 10.1007/s002249910009
|
| [15] |
N. Betzler, R. Bredereck, R. Niedermeier, J. Uhlmann, On bounded-degree vertex deletion parameterized by treewidth, Discrete Appl. Math., 160 (2012), 53–60. https://doi.org/10.1016/j.dam.2011.08.013 doi: 10.1016/j.dam.2011.08.013
|
| [16] |
M. U. Gerber, D. Kobler, Algorithms for vertex-partitioning problems on graphs with fixed clique-width, Theor. Comput. Sci., 299 (2003), 719–734. https://doi.org/10.1016/S0304-3975(02)00725-9 doi: 10.1016/S0304-3975(02)00725-9
|
| [17] |
M. Lampis, Parameterized approximation schemes using graph widths, In: Automata, languages, and programming (ICALP 2014), Berlin: Springer, 2014,775–786. https://doi.org/10.1007/978-3-662-43948-7_64 |
| [18] |
B. Jamison, S. Olariu, A tree representation for $P_4$-sparse graphs, Discrete Appl. Math., 35 (1992), 115–129. https://doi.org/10.1016/0166-218X(92)90036-A doi: 10.1016/0166-218X(92)90036-A
|
| [19] |
M. R. Cappelle, L. C. D. Carvalho, Computational verification for $k$-independence in $P_4$-tidy graphs (Version v2.0.0) [Computer software], Zenodo, 2026. https://doi.org/10.5281/zenodo.23619639 |
| [20] |
R. M. McConnell, J. P. Spinrad, Modular decomposition and transitive orientation, Discrete Math., 201 (1999), 189–241. https://doi.org/10.1016/S0012-365X(98)00319-7 doi: 10.1016/S0012-365X(98)00319-7
|
| [21] |
M. Tedder, D. Corneil, M. Habib, C. Paul, Simpler linear-time modular decomposition via recursive factorizing permutations, In: Automata, languages and programming (ICALP 2008), Berlin: Springer, 2008,634–645. https://doi.org/10.1007/978-3-540-70575-8_52 |
| [22] |
B. Courcelle, J. A. Makowsky, U. Rotics, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, Discrete Appl. Math., 108 (2001), 23–52. https://doi.org/10.1016/S0166-218X(00)00221-3 doi: 10.1016/S0166-218X(00)00221-3
|
Spiders and quasi-spiders of weight $ 3 $. In the underlying spider, $ C = \{c_1, c_2, c_3\} $ is a clique, $ X = \{x_1, x_2, x_3\} $ is an independent set, and the head $ R $ (possibly empty) is complete to $ C $ and anticomplete to $ X $. In each quasi-spider, the vertex $ c_3 $ or $ x_3 $ of the underlying spider is replaced by a twin pair, enclosed by a dashed box: its two vertices have the same neighbors outside the pair and are adjacent (true twins) or nonadjacent (false twins)
A $ P_4 $-tidy graph $ G $ with nonempty head, its modular decomposition tree $ \mathit{MD}(G) $, and the labelled decomposition tree $ T(G) $ produced by Lemma 21. In (a), the double line indicates that $ R $ is complete to $ C $