Research article

$ k $-Independence in $ P_4 $-tidy graphs

  • Published: 10 November 2026
  • MSC : 05C69, 05C85

  • 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

    Related Papers:

  • 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
  • Reader Comments
  • © 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)

Metrics

Article views(106) PDF downloads(12) Cited by(0)

Article outline

Figures and Tables

Figures(2)  /  Tables(1)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog