Досконалі 1-коди на тривалентних дистанційно-транзитивних графах
Loading...
Date
2017
Authors
Олійник, Богдана
Лукашова, Марія
Лукашова, Тетяна
Journal Title
Journal ISSN
Volume Title
Publisher
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.
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.
Description
Keywords
дистанційно-транзитивний граф, кубічний граф, досконалі е-коди, distance-transitive graph, cubic graph, perfect 1-codes, стаття
Citation
Олійник Б. В. Досконалі 1-коди на тривалентних дистанційно-транзитивних графах / Олійник Б. В., Лукашова М. В., Лукашова Т. Д. // Наукові записки НаУКМА. Фізико-математичні науки. - 2017. - Т. 201. - С. 18-28.