# The average size of ordered binary subgraphs

J. van Leeuwen (Editor), Pieter H. Hartel

Research output: Contribution to conferencePaperpeer-review

## Abstract

To analyse the demands made on the garbage collector in a graph reduction system, the change in size of an average graph is studied when an arbitrary edge is removed. In ordered binary trees the average number of deleted nodes as a result of cutting a single edge is equal to the average size of a subtree. Under the assumption that all trees with n nodes are equally likely to occur, the expected size of a subtree is found to be approximately $\sqrt{\pi n}$. The enumeration procedure can be applied to graphs by considering spanning trees in which the nodes that were shared in the graph are marked in the spanning tree. A correction to the calculation of the average is applied by ignoring subgraphs that have a marked root. Under the same assumption as above the average size of a subgraph is approximately $\sqrt{\pi n}-2(m+1)$, where $m$ represents the number of shared nodes and $m \ll n$.
Original language Undefined 327-351 25 https://doi.org/10.1007/3-540-50728-0_55 Published - Jun 1988 14th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1988 - Amsterdam, NetherlandsDuration: 15 Jun 1988 → 17 Jun 1988Conference number: 14

### Conference

Conference 14th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1988 WG Netherlands Amsterdam 15/06/88 → 17/06/88

• IR-55756
• EWI-1248