Досконалі 1-коди на тривалентних дистанційно-транзитивних графах

Abstract

Досліджено існування досконалих 1-кодів на тривалентних дистанційно-транзитивних графах. Спираючись на результати Нормана Біґґса, показано, що серед усіх таких графiв необхiдну умову їснування досконалого 1-коду задовольняють повний граф К4, гіперкуб, граф Дезарга, граф Коксетера та граф Фостера. Доведено, що графи Дезарга і Фостера не можуть мати досконалих одиничних кодів, а для повного графа К4, гіперкуба та графа Коксетера знайдено та побудовано досконалі одиничні коди.

The existence of perfect 1-codes on cubic distance-transitive graphs is investigated. Based on the results of Norman Biggs, it has been shown that among all of such graphs, the perfect 1-codes may exist on the complete graph K4, on the graph of the cube, on the Desargues graph, Coxeter graph, and Foster graph. It is proved that there are no perfect 1-codes on the Desargues graph and Foster graph. Perfect 1-codes are constructed for the complete graph K4, the graph of the cube, and the Coxeter graph.