The minimal extensions for a colored star graphs

Abstract

The article describes the results of the search for a minimal vertex and edge extensions of an undirected colored star graphs. This search is a part of the minimal extensions of a colored graphs problem research. A graph G^* is called a vertex (edge) k-extension of a graph G if, after removing any k vertices (edges) from the graph G^*, the resulting graph contains the original graph G. A vertex extension of a graph G is called minimal if it contains the minimum possible number of additional vertices and edges. An edge extension of a graph G is called minimal if it contains the same number of vertices as the graph G and the minimum possible number of additional edges. Most of the papers mainly deal with minimal extensions of graphs without colors. If colored graphs are considered, then the embedding is meant taking into account the colors. A star graph or star is a complete bipartite graph with a single vertex in one part. Earlier, the problem of constructing minimal vertex and edge extensions was solved for ordinary stars. This article provides a complete solution for colored stars. For all possible minimal edge and vertex extensions of a given class of graphs, corresponding schemes for constructing extensions with proofs are presented. The number of additional edges required to meet the minimum extension requirement is also provided.