Cite this article as:
Kurnosova S. G. T-irreducible extension for unions of complete graphs. Izv. Saratov Univ. (N. S.), Ser. Math. Mech. Inform., 2005, vol. 5, iss. 1, pp. 107-?.
T-irreducible extension for unions of complete graphs
T-irreducible extension is one of kinds of optimal extensions of graphs. Constructions of optimal extensions are used in diagnosis of discrete systems and in cryptography. A graph H with n+1 vertices is called an extension of a graph G with n vertices if G can be embedded in every maximal subgraph of H. Any graph Ghas the trivial extension that is the join ng+of G with some outer vertex v. T-irreducible extensions are obtained from the trivial extension by removal of maximal number of edges in such a way that the extension property is preserved. The problem of finding of the initial graph from any of its T-irreducible extensions has a linear complexity, but until now there is no efficient algorithm for finding of all T-irreducible extensions of a given graph. Graphs studied in this paper are unions of complete graphs each of which has more than one vertex. An algorithm of construction of all T-irreducible extensions for such graphs is presented. Also an estimate of a total amount of the resulting extensions is made.
[1] Авиженис А., “Отказоустойчивость — свойство, обеспечивающее постоянную работоспособность цифровых систем”, Тр. Ин-та инженеров по электротехнике и радиоэлектронике, 66:1О (1978), 5–25
[2] Hayes P., “A graph model for fault-tolerant computing system”, IEEE Trans. Comput., С-25:9 (1976), 875–884
[3] Салий В. Н., “Доказательства с нулевым разглашением в задачах о расширениях графов”, Вестн. Томск. ун-та, 2003, № 6, Прил., 63–65
[4] Курносова С. Г., Т-неприводимые расширения 3-, 4-, 5- и 6-вершинных графов, Деп. в ВИНИТИ 21.06.2003, № 1203-B2003, Саратов, 2003, 18 с.
[5] Курносова С. Г., “Т-неприводимые расширения для некоторых классов графов”, Теоретические проблемы информатики и ее приложений, 6, Саратов, 2005
[6] Курносова С. Г., Каталог Т-неприводимых расширений для деревьев с числом вершин не более 1О, Деп. в ВИНИТИ 30.06.2004, № 1126-82004, Саратов, 2004, 16 с.
[7] Курносова С. Г., “Т-неприводимые расширения бесповторных объединений полных графов”, Молодежь. Образование. Экономика, Т. 4, Сб. науч. ст., Ярославль, 2004, 289–292
