Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2411.09926 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911108210622464 |
|---|---|
| author | Gunasekara, Ajani De Vas Horsley, Daniel |
| author_facet | Gunasekara, Ajani De Vas Horsley, Daniel |
| contents | A $k$-star is a complete bipartite graph $K_{1,k}$. A partial $k$-star design of order $n$ is a pair $(V,\mathcal{A})$ where $V$ is a set of $n$ vertices and $\mathcal{A}$ is a set of edge-disjoint $k$-stars whose vertex sets are subsets of $V$. If each edge of the complete graph with vertex set $V$ is in some star in $\mathcal{A}$, then $(V,\mathcal{A})$ is a (complete) $k$-star design. We say that $(V,\mathcal{A})$ is completable if there is a $k$-star design $(V,\mathcal{B})$ such that $\mathcal{A} \subseteq \mathcal{B}$. In this paper we determine, for all $k$ and $n$, the minimum number of stars in an uncompletable partial $k$-star design of order $n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_09926 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Completing partial $k$-star designs Gunasekara, Ajani De Vas Horsley, Daniel Combinatorics 05C51 A $k$-star is a complete bipartite graph $K_{1,k}$. A partial $k$-star design of order $n$ is a pair $(V,\mathcal{A})$ where $V$ is a set of $n$ vertices and $\mathcal{A}$ is a set of edge-disjoint $k$-stars whose vertex sets are subsets of $V$. If each edge of the complete graph with vertex set $V$ is in some star in $\mathcal{A}$, then $(V,\mathcal{A})$ is a (complete) $k$-star design. We say that $(V,\mathcal{A})$ is completable if there is a $k$-star design $(V,\mathcal{B})$ such that $\mathcal{A} \subseteq \mathcal{B}$. In this paper we determine, for all $k$ and $n$, the minimum number of stars in an uncompletable partial $k$-star design of order $n$. |
| title | Completing partial $k$-star designs |
| topic | Combinatorics 05C51 |
| url | https://arxiv.org/abs/2411.09926 |