минимальное реберное расширение

On Lower Bound of Edge Number of Minimal Edge 1-Extension of Starlike Tree

For a given graph G with n nodes, we say that graph G∗ is its 1-edge extension if for each edge e of G∗ the subgraph G∗ −e contains graph G up to isomorphism. Graph G∗ is minimal 1-edge extension of graph G if G∗ has n nodes and there is no 1-edge extension with n nodes of graph G having fewer edges than G. A tree is called starlike if it has exactly one node of degree greater than two. We give a lower bound of edge number of minimal edge 1-extension of starlike tree and provide family on which this bound is achieved.