THE DECK RATIO AND SELF-REPAIRING GRAPHS

Abstract. In this paper we define, for a graph invariant ψ, the deck ratio of ψ byDψ(G) = ψ(G) P v∈V (G) ψ(G−v). We give generic upper and lower bounds on Dψ for monotone increasing and monotone decreasing invariants ψ, respectively. Then we proceed to consider the Wiener index W (G), showing that DW (G) ≤ 1|V (G)|−2. We show that equality is attained for a graph G if and only if every induced P3 subgraph of G is contained in a C4 subgraph. Such graphs have been previously studied under the name of self-repairing graphs. We show that a graph on n ≥ 4 vertices with at least n2−3n+62 edges is necessarily a self-repairing graph and that this is the best possible result. We also show that a 2-connected graph is self-repairing iff all factors in its Cartesian product decomposition are. Finally, some open problems about the deck ratio and about self-repairing graphs are posed at the end of the paper