Young domination on Hamming rectangles
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918326291136512 |
|---|---|
| author | Gravner, Janko Krnc, Matjaž Milanič, Martin Raymond, Jean-Florent |
| author_facet | Gravner, Janko Krnc, Matjaž Milanič, Martin Raymond, Jean-Florent |
| contents | We introduce a family of domination-type problems in Cartesian products of two graphs. The framework captures several well-studied topics, including variants of bootstrap percolation, line growth, distance domination, and target set selection. We focus on Cartesian products of two complete graphs and formulate the notion of Young domination number in terms of a growth rule determined by a Young diagram; this number is the smallest cardinality of an initial set that covers the entire vertex set in a prescribed number $L$ of iterations of the rule.
We compute the Young domination number with $L=1$ for several natural cases, including $k$-domination for Cartesian products of two complete graphs of the same order, thereby proving a conjecture from 2009 due to Burchett, Lane, and Lachniet. We show that the case of $L=1$ of Young domination is equivalent to computing bipartite Turán numbers for families of double stars, yielding implications of our results in extremal graph theory. For arbitrary fixed $L$, we devise constant-factor approximation algorithms for the problem. Our approach is based on a variety of techniques, including duality between Young diagrams, algebraic formulations, explicit constructions, and dynamic programming. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_03788 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Young domination on Hamming rectangles Gravner, Janko Krnc, Matjaž Milanič, Martin Raymond, Jean-Florent Combinatorics Discrete Mathematics Data Structures and Algorithms 05C35 (Primary) 05C69, 05C85, 68W25 (Secondary) We introduce a family of domination-type problems in Cartesian products of two graphs. The framework captures several well-studied topics, including variants of bootstrap percolation, line growth, distance domination, and target set selection. We focus on Cartesian products of two complete graphs and formulate the notion of Young domination number in terms of a growth rule determined by a Young diagram; this number is the smallest cardinality of an initial set that covers the entire vertex set in a prescribed number $L$ of iterations of the rule. We compute the Young domination number with $L=1$ for several natural cases, including $k$-domination for Cartesian products of two complete graphs of the same order, thereby proving a conjecture from 2009 due to Burchett, Lane, and Lachniet. We show that the case of $L=1$ of Young domination is equivalent to computing bipartite Turán numbers for families of double stars, yielding implications of our results in extremal graph theory. For arbitrary fixed $L$, we devise constant-factor approximation algorithms for the problem. Our approach is based on a variety of techniques, including duality between Young diagrams, algebraic formulations, explicit constructions, and dynamic programming. |
| title | Young domination on Hamming rectangles |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms 05C35 (Primary) 05C69, 05C85, 68W25 (Secondary) |
| url | https://arxiv.org/abs/2501.03788 |