Article in press
Authors:
María Gracia Cornet
Depto. de Matemática, Facultad de Ciencias Exactas, Ing. y Agrimensura, Universidad Nacional de Rosario
email: mgracia@fceia.unr.edu.ar
Pablo Torres
Facultad de Ciencias Exactas, Ingeniería y Agrimensura, Universidad Nacional de Rosario.
CONICET.
email: ptorres@fceia.unr.edu.ar
Title:
$k$-tuple domination in Kneser graphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2024-08-28 , Revised: 2025-09-17 , Accepted: 2025-09-17 , Available online: 2025-10-29 , https://doi.org/10.7151/dmgt.2608
Abstract:
Given a positive integer $k$, a $k$-tuple dominating set of a graph $G$ is a
subset of vertices $D\subseteq V(G)$ such that every vertex of $G$ has at least
$k$ neighbors in $D$. The $k$-tuple domination number of $G$, denoted
$\gamma_{× k}(G)$, is the minimum cardinality of a $k$-tuple dominating
set of $G$. In this paper we determine all the minimum $k$-tuple dominating
sets for the Kneser graphs $K(n,r)$ with $n$ large enough with respect to $r$.
In addition, we relate $k$-tuple dominating sets and $2$-packings in Kneser
graphs, and we compute the $2$-packing number of $K(3r-2,r)$ for $r\geq3$.
Finally, we obtain minimum sized $k$-tuple dominating sets of $K(n,2)$ for
$n\geq \Theta(\sqrt{k})$.
Keywords:
Kneser graphs, multiple domination, $k$-tuple domination, $2$-packings
References:
- J.A. Barrau, On the combinatory problem of Steiner, in: Proc. Sect. Sci. Konink. Akad. Wetensch. 11, (Amsterdam 1908) 352–360.
- N. Biggs, Some odd graph theory, Ann. New York Acad. Sci. 319 (1979) 71–81.
https://doi.org/10.1111/j.1749-6632.1979.tb32775.x - D. Božović, A. Kelenc, I. Peterin and I.G. Yero, Incidence dimension and $2$-packing number in graphs, RAIRO Oper. Res. 56 (2022) 199–211.
https://doi.org/10.1051/ro/2022001 - B. Brešar, T. Kos and P.D. Torres, Grundy domination and zero forcing in Kneser graphs, Ars Math. Contemp. 17 (2019) 419–430.
https://doi.org/10.26493/1855-3974.1881.384 - B. Brešar, T. Dravec, M.G. Cornet and M.A. Henning, $k$-Domination invariants on Kneser graphs, Ars Math. Contemp. 25 (2025) P4.02.
https://doi.org/10.26493/1855-3974.3294.7fd - A. Cabrera Mart\i nez, A note on the $k$-tuple domination number of graphs, Ars Math. Contemp. 22 (2022) P4.03.
https://doi.org/10.26493/1855-3974.2600.dcc - G.J. Chang, The upper bound on $k$-tuple domination numbers of graphs, European J. Combin. 29 (2008) 1333–1336.
https://doi.org/10.1016/j.ejc.2007.05.009 - N.E. Clarke and R.P. Gallant, On $2$-limited packings of complete grid graphs, Discrete Math. 340 (2017) 1705–1715.
https://doi.org/10.1016/j.disc.2016.11.001 - M.G. Cornet and P. Torres, $k$-tuple domination on Kneser graphs (2023).
arXiv: 2308.15603v1 - P. Erdős, C. Ko and R. Rado, Intersection theorems for system of finite sets, Q.J. Math. 12 (1961) 313–320.
https://doi.org/10.1093/qmath/12.1.313 - A. Gagarin and V.E. Zverovich, A generalised upper bound for the $k$-tuple domination number, Discrete Math. 308 (2008) 880–885.
https://doi.org/10.1016/j.disc.2007.07.033 - I. Gorodezky, Dominating Sets in Kneser Graphs, Master's Thesis (University of Waterloo, 2007).
- P. Hammond and D.H. Smith, Perfect codes in the graphs $O_k$, J. Combin. Theory Ser. B 19 (1975) 239–255.
https://doi.org/10.1016/0095-8956(75)90087-8 - C. Hartman and D.B. West, Covering designs and domination in Kneser graphs (2003), manuscript.
- T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Topics in Domination in Graphs, Dev. Math. 64 (Springer, Cham, 2020).
https://doi.org/10.1007/978-3-030-51117-3 - T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs, Advanced Topics (Marcel Dekker, New York, 1998).
https://doi.org/10.1201/9781315141428 - T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (CRC Press, Boca Raton, 1998).
https://doi.org/10.1201/9781482246582 - J. Ivančo and B. Zelinka, Domination in Kneser graphs, Math. Bohem. 118 (1993) 147–152.
https://doi.org/10.21136/MB.1993.126050 - P. Jalilolghadr and A. Behtoei, Total dominator chromatic number of Kneser graphs, AKCE Int. J. Graphs Comb. 20 (2023) 52–56.
https://doi.org/10.1080/09728600.2023.2170299 - M. Kneser, Aufgabe $300$, Jahresber. Dtsch. Math.-Ver. 2(27) (1955) 3–16.
- C.-S. Liao and G.J. Chang, $k$-tuple domination in graphs, Inform. Process. Lett. 87 (2003) 45–50.
https://doi.org/10.1016/S0020-0190(03)00233-3 - L. Lovász, Kneser's conjecture, chromatic numbers and homotopy, J. Combin. Theory Ser. A 25 (1978) 319–324.
https://doi.org/10.1016/0097-3165(78)90022-5 - J. Matoušek, A combinatorial proof of Kneser's conjecture, Combinatorica 24 (2004) 163–170.
https://doi.org/10.3929/ethz-b-000050671 - P.R.J. Östergård, Z. Shao and X. Xu, Bounds on the domination number of Kneser graphs, Ars Math. Contemp. 9 (2015) 187–195.
https://doi.org/10.26493/1855-3974.491.b02 - J. Przybyło, On upper bounds for multiple domination numbers of graphs, Discrete Appl. Math. 161 (2013) 2758–2763.
https://doi.org/10.1016/j.dam.2013.05.006 - G.V. Ramanan, Proof of a conjecture of Frankl and Füredi, J. Combin. Theory Ser. A 79 (1997) 53–67.
https://doi.org/10.1006/jcta.1997.2774 - M. Valencia-Pabon and J.-C. Vera, On the diameter of Kneser graphs, Discrete Math. 305 (2005) 383–385.
https://doi.org/10.1016/j.disc.2005.10.001 - T. Zec and M. Grbić, Several Roman domination graph invariants on Kneser graphs, Discrete Math. Theor. Comput. Sci. 25:1 (2023) 14.
https://doi.org/10.46298/dmtcs.10506 - IBM, ILOG CPLEX Optimization Studio $22.1.0$ (Accesed: 2024-03-30).
https://www.ibm.com/products/ilog-cplex-optimization-studio
Close