On the number of minimal vertex and edge $1$-extensions of cycles

M. B. Abrosimov ; N. A. Kuznetsov

Prikladnaya Diskretnaya Matematika. Supplement, no. 5 (2012), pp. 84-86

Résumé

For a given graph $G$ with $n$ nodes, we say that graph $G^*$ is its vertex extension if for each vertex $v$ of $G^*$ the subgraph $G^*-v$ contains graph $G$ up to isomorphism. A graph $G^*$ is a minimal vertex extension of the graph $G$ if $G^*$ has $n+1$ nodes and there is no vertex extension with $n+1$ nodes of $G$ having fewer edges than $G^*$. A graph $G^*$ is edge extension of graph $G$ with $n$ nodes if every graph obtained by removing any edge from $G^*$ contains $G$. Edge extension of graph $G$ with $n$ vertices is called minimal if among all edge extensions of graph $G$ with $n$ vertices it has the minimum possible number of edges. We present the results of computational experiment in which all minimal vertex and edge extensions of cycles up to 17 vertices were found.