Network fault costs based on minimum leaf spanning trees
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915152518971392 |
|---|---|
| author | Goedgebeur, Jan Renders, Jarne Wiener, Gábor Zamfirescu, Carol T. |
| author_facet | Goedgebeur, Jan Renders, Jarne Wiener, Gábor Zamfirescu, Carol T. |
| contents | We study the fault-tolerance of networks from both the structural and computational point of view using the minimum leaf number of the corresponding graph $G$, i.e. the minimum number of leaves of the spanning trees of $G$, and its vertex-deleted subgraphs. We investigate networks that are leaf-guaranteed, i.e. which satisfy a certain stability condition with respect to minimum leaf numbers and vertex-deletion. Next to this, our main notion is the so-called fault cost, which is based on the number of vertices that have different degrees in minimum leaf spanning trees of the network and its vertex-deleted subgraphs. We characterise networks with vanishing fault cost via leaf-guaranteed graphs and describe, for any given network $N$, leaf-guaranteed networks containing $N$. We determine for all non-negative integers $k \le 8$ except $1$ the smallest network with fault cost $k$. We also give a detailed treatment of the fault cost $1$ case, prove that there are infinitely many $3$-regular networks with fault cost $3$, and show that for any non-negative integer $k$ there exists a network with fault cost exactly $k$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_10213 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Network fault costs based on minimum leaf spanning trees Goedgebeur, Jan Renders, Jarne Wiener, Gábor Zamfirescu, Carol T. Combinatorics Discrete Mathematics We study the fault-tolerance of networks from both the structural and computational point of view using the minimum leaf number of the corresponding graph $G$, i.e. the minimum number of leaves of the spanning trees of $G$, and its vertex-deleted subgraphs. We investigate networks that are leaf-guaranteed, i.e. which satisfy a certain stability condition with respect to minimum leaf numbers and vertex-deletion. Next to this, our main notion is the so-called fault cost, which is based on the number of vertices that have different degrees in minimum leaf spanning trees of the network and its vertex-deleted subgraphs. We characterise networks with vanishing fault cost via leaf-guaranteed graphs and describe, for any given network $N$, leaf-guaranteed networks containing $N$. We determine for all non-negative integers $k \le 8$ except $1$ the smallest network with fault cost $k$. We also give a detailed treatment of the fault cost $1$ case, prove that there are infinitely many $3$-regular networks with fault cost $3$, and show that for any non-negative integer $k$ there exists a network with fault cost exactly $k$. |
| title | Network fault costs based on minimum leaf spanning trees |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2502.10213 |