Network fault costs based on minimum leaf spanning trees

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 the smallest network(s) with fault cost k for all non-negative integers k ≤ 8, with the exception of k=1. 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.