$k$-fault-tolerant graphs for $p$ disjoint complete graphs of order $c$
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912026054361088 |
|---|---|
| author | Cichacz, Sylwia Görlich, Agnieszka Suchan, Karol |
| author_facet | Cichacz, Sylwia Görlich, Agnieszka Suchan, Karol |
| contents | Vertex-fault-tolerance was introduced by Hayes~\cite{Hayes1976} in 1976, and since then it has been systematically studied in different aspects. In this paper we study $k$-vertex-fault-tolerant graphs for $p$ disjoint complete graphs of order $c$, i.e., graphs in which removing any $k$ vertices leaves a graph that has $p$ disjoint complete graphs of order $c$ as a subgraph. The main contribution is to describe such graphs that have the smallest possible number of edges for $k=1$, $p \geq 1$, and $c \geq 3$. Moreover, we analyze some properties of such graphs for any value of $k$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_06892 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | $k$-fault-tolerant graphs for $p$ disjoint complete graphs of order $c$ Cichacz, Sylwia Görlich, Agnieszka Suchan, Karol Combinatorics 05C69, 05C70, 05C35 Vertex-fault-tolerance was introduced by Hayes~\cite{Hayes1976} in 1976, and since then it has been systematically studied in different aspects. In this paper we study $k$-vertex-fault-tolerant graphs for $p$ disjoint complete graphs of order $c$, i.e., graphs in which removing any $k$ vertices leaves a graph that has $p$ disjoint complete graphs of order $c$ as a subgraph. The main contribution is to describe such graphs that have the smallest possible number of edges for $k=1$, $p \geq 1$, and $c \geq 3$. Moreover, we analyze some properties of such graphs for any value of $k$. |
| title | $k$-fault-tolerant graphs for $p$ disjoint complete graphs of order $c$ |
| topic | Combinatorics 05C69, 05C70, 05C35 |
| url | https://arxiv.org/abs/2212.06892 |