Applied Graph Theory

On exact extensions of tournaments

A. A. Dolgov


Abstract: Graph $G^{*}=(V^{*},\alpha)$ is said to be an exact $k$-extension of a graph $G=(V,\alpha)$ if every graph obtained by removing any $k$ vertexes from $G^{*}$ and graph $G$ are isomorphic. We study the problem of constructing exact $k$-extension of tournaments. Two families of tournaments with their exact extensions are presented. Further, we introduce a special graph operation that helps to construct exact extensions using two other families.

UDC: 519.17