The minimal extensions for a colored star graphs

Mikhail B. Abrosimov, Peter V. Razumovsky


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.

Full Text:

PDF (Russian)


J. P. Hayes, A graph model for fault-tolerant computing system, IEEE Trans. Comput., vol. C-25, no. 9, pp. 875-884, 1976.

F. Harary, J. P. Hayes, “Edge fault tolerance in graphs”, Networks, vol. 23, pp. 135-142, 1993.

M. B. Abrosimov, Fault Tolerance Graph Models. Saratov: Izdatel'stvo Saratovskogo universiteta, 2012 (In Russian).

P. V. Razumovsky, M. B. Abrosimov, Generation of colored graphs with isomorphism rejection, Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2021, vol. 21, iss. 2, pp. 267–277 (In Russian).

P. V. Razumovsky, The search for minimal edge 1-extension of an undirected colored graph, Izvestiya of Saratov University. New Series. Series: Mathematics. Mechanics. Informatics, vol. 21, no. 3, pp. 400-407, 2021.

M. B. Abrosimov, Minimal k-extensions of precomplete graphs // Izvestiya VUZov: Matematika, 2003, № 6(493), pp. 3-11 (In Russian).

M. B. Abrosimov, Minimal edge extensions of some precomplete graphs // Applied discrete mathematics, 2010, №1, pp. 105–117 (In Russian).

M. B. Abrosimov, Minimum edge extensions of directed and oriented stars // Applied discrete mathematics, 2011, № 2, pp.77–89 (In Russian).

M. B. Abrosimov, Minimum vertex extensions of directed stars // Discrete mathematics, 2011, № 23:2, pp. 93–102 (In Russian).

A. M. Bogomolov, V. N. Salii, Algebraic foundations of the theory of discrete systems. М.: Nauka, 1997 (In Russian).


  • There are currently no refbacks.

Abava  Кибербезопасность FRUCT 2023

ISSN: 2307-8162