RUS  ENG
Full version
JOURNALS // Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] // Archive

Mat. Vopr. Kriptogr., 2012 Volume 3, Issue 3, Pages 105–128 (Mi mvk63)

This article is cited in 2 papers

Graph reduction in the construction of minimal clique cover

P. V. Roldugin

Moscow State Technical University of Radio Engineering, Electronics and Automatics, Moscow

Abstract: The problem of construction of a graph coverage with a minimum number of its complete subgraphs (cliques) is considered. We describe classes of subgraphs for which it is possible to reduce the graph coverage problem to the same problem for graphs of smaller orders. We show that these classes are wider than those known before.

Key words: classes of graphs, graph coverings, cliques.

UDC: 519.177.3+519.178

Received 20.V.2011

DOI: 10.4213/mvk63



© Steklov Math. Inst. of RAS, 2024