Geodesic
On the number of $k$-dominating independent sets in planar graphs
Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 1, pp. 109-128 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

A set $J_k$ of graph vertices is said to be $k$-dominating independent ($k \geq 1$) if its vertices are pairwise adjacent and every vertex not in $J_k$ is adjacent to at least $k$ vertices in $J_k.$ In the present paper, we obtain new upper bounds for the number of $k$-dominating independent sets for $k \geq 2$ in some planar graph classes. Illustr. 7, bibliogr. 15.
Keywords: independent set, dominating set, $k$-dominating independent set, planar graph. 
@article{DA_2024_31_1_a5,
     author = {D. S. Taletskii},
     title = {On the number of $k$-dominating independent sets in~planar graphs},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {109--128},
     year = {2024},
     volume = {31},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2024_31_1_a5/}
}
TY  - JOUR
AU  - D. S. Taletskii
TI  - On the number of $k$-dominating independent sets in planar graphs
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2024
SP  - 109
EP  - 128
VL  - 31
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DA_2024_31_1_a5/
LA  - ru
ID  - DA_2024_31_1_a5
ER  - 
%0 Journal Article
%A D. S. Taletskii
%T On the number of $k$-dominating independent sets in planar graphs
%J Diskretnyj analiz i issledovanie operacij
%D 2024
%P 109-128
%V 31
%N 1
%U http://geodesic.mathdoc.fr/item/DA_2024_31_1_a5/
%G ru
%F DA_2024_31_1_a5
D. S. Taletskii. On the number of $k$-dominating independent sets in planar graphs. Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 1, pp. 109-128. http://geodesic.mathdoc.fr/item/DA_2024_31_1_a5/

[1] Nagy Z. L., “On the number of $k$-dominating independent sets”, J. Graph Theory, 84:4 (2017), 566–580 | DOI | MR | Zbl

[2] Gerbner D., Keszegh B., Methuku A., Patkós B., Vizer M., “An improvement on the maximum number of $k$-dominating independent sets”, J. Graph Theory, 91:1 (2019), 88–97 | DOI | MR | Zbl

[3] Moon J., Moser L., “On cliques in graphs”, Israel J. Math., 3:1 (1965), 23–28 | DOI | MR | Zbl

[4] Wood D. R., “On the number of maximal independent sets in a graph”, Discrete Math. Theor. Comput. Sci., 13:3 (2011), 17–19 | MR

[5] Griggs J., Grinstead C., Guichard D., “The number of maximal independent sets in a connected graph”, Discrete Math., 68 (1988), 211–220 | DOI | MR | Zbl

[6] Wilf H., “The number of maximal independent sets in a tree”, SIAM J. Algebr. Discrete Methods, 7:1 (1986), 125–130 | DOI | MR | Zbl

[7] Liu J., “Maximal independent sets in bipartite graphs”, J. Graph Theory, 17:4 (1993), 495–507 | DOI | MR | Zbl

[8] Hujter M., Tuza Z., “The number of maximal independent sets in triangle-free graphs”, SIAM J. Discrete Math., 6:2 (1993), 284–288 | DOI | MR

[9] Jou M. J., Chang G., “Maximal independent sets in graphs with at most one cycle”, Discrete Appl. Math., 79 (1997), 67–73 | DOI | MR | Zbl

[10] Ying G. C., Meng K. K., Sagan B. E., Vatter V. E., “Maximal independent sets in graphs with at most $r$ cycles”, J. Graph Theory, 53:4 (2006), 270–282 | DOI | MR | Zbl

[11] Koh K. M., Goh C. Y., Dong F. M., “The maximum number of maximal independent sets in unicyclic connected graphs”, Discrete Math., 308:17 (2008), 3761–3769 | DOI | MR | Zbl

[12] Włoch A., “On 2-dominating kernels of graphs”, Australas. J. Comb., 52 (2012), 273–284 | MR

[13] Bednarz P., Włoch I., “On (2-$d$)-kernels in the Cartesian product of graphs”, Ann. Univ. Mariae Curie-Skłodowska. Sect. A, 70 (2016), 1–8 | MR | Zbl

[14] Bednarz P., “On (2-$d$)-kernels in the tensor product of graphs”, Symmetry, 13 (2021), 230, 9 pp. | DOI

[15] Bednarz P., “On (2-$d$)-kernels in two generalizations of the Petersen graph”, Symmetry, 13 (2021), 1948, 10 pp. | DOI