Циклічні пентагональні розклади графа Кn

Abstract

Розроблено спосіб побудови базових компонент циклічного пентагонального розкладу графа Кп. На його основі складено алгоритми пошуку списків різних (К11, С5), (К21, С5)-розкладів, які реалізовані з використанням програмного середовища Delphi. Списки містять такі відомості: базову компоненту, кортеж довжин, індекс компоненти – специфікаційний інваріант для кожного розкладу. Для розрізнення-ототожнення цих розкладів випробувано специфікаційні інваріанти і введені в статті графічні інваріанти. За результатами дослідження отримано, що з точністю до ізоморфізму існують чотири циклічних (К11,С5)-розклади, два з них – 5-гомогенні, а також з точністю до ізоморфізму існує не менше, ніж 62 циклічних (К21,С5)-розклади. Доведено необхідну умову ізоморфності розкладів. Її проілюстровано при перевірці на ізоморфність двох різних (К11,С5)-розкладів, а також використано при розв’язуванні задачі ототожнення певних (К21,С5)-розкладів, які не вдалося розрізнити за допомогою специфікаційних і графічних інваріантів.

(Kn, G)-decomposition is a set of subgraphs of Kn such that every of the subgraphs is isomorphic to the graph G, and every edge of Kn belongs to one and only one of these subgraphs. If (Kn, G)-decomposition has an automorphism that contains some cyclic permutation then the decomposition is cyclic. Every (Кn, С5)-decomposition is called a pentagonal decomposition of Кn . The method to construct basic components of cyclic pentagonal decomposition of the graph Кn was developed. Using this method algorithms which find the lists for different (К11, С5), (К21, С5)-decompositons have been created. The algorithms were realized by means of the Delphi software environment. The lists contain the following information: the basic component, the tuple of the lengths, and the component index – specification invariant for every decomposition. For differentiation-identification of the decompositions specification invariants and graphical invariants (which are introduced in this paper) were tested. The results of the study testily that up to isomorphism there exist four cyclic (К11,С5)-decompositions, two of them 5-homogeneous, and that up to isomorphism there exist not less than 62 cyclic (К21,С5)-decompositions. Consecutive mapping of an orbit of cyclic (Кn, С5)-decomposition R1 into an orbit of another cyclic (Кn, С5)-decomposition R2 is defined as follows: if і-th component of decomposition R1 mapped into j-th component of decomposition R2 then і+1 is mapped into (j+l)mod n, і+2 into (j+2l)mod n etc., where l is the step of the mapping. In this paper the following necessary condition of the decomposition isomorphism is proved: in isomorphism of cyclic (Кn, С5)-decompositions, the consecutive mapping of one decomposition orbit into orbit of another decomposition remains unchanged. This is illustrated while verifying two different (К11,С5)-isomorphism, and it is also used to solve an identification problem of some (К21,С5)-decompositions, which were not identified by means of the specification invariants and/or graphical invariants.