Graph Self-Transformation Model Based on the Operation of Change the End of the Edge

Article Sidebar

PDF (Русский)
Published: 09.05.2020
UDC 004.021 004.42
DOI: https://doi.org/10.26907/1562-5419-2020-23-3-315-335
Issue
Vol. 23 No. 3 (2020): Special issue «Scientific Services & Internet». Part 1

Main Article Content

Igor Borisovich Burdonov
Ivannikov Institute for System Programming of the RAS, Moscow

Abstract

We consider a distributed network whose topology is described by an undirected graph. The network itself can change its topology, using special “commands” provided by its nodes. The work proposes an extremely local atomic transformation acb of a change the end c of the edge ac, “moving” along the edge cb from vertex c to vertex b. As a result of this operation, the edge ac is removed, and the edge ab is added. Such a transformation is performed by a “command” from a common vertex c of two adjacent edges ac and cb. It is shown that from any tree you can get any other tree with the same set of vertices using only atomic transformations. If the degrees of the tree vertices are bounded by the number d (d 3), then the transformation does not violate this restriction. As an example of the purpose of such a transformation, the problems of maximizing and minimizing the Wiener index of a tree with a limited degree of vertices without changing the set of its vertices are considered. The Wiener index is the sum of pairwise distances between the vertices of a graph. The maximum Wiener index has a linear tree (a tree with two leaf vertices). For a root tree with a minimum Wiener index, its type and method for calculating the number of vertices in the branches of the neighbors of the root are determined. Two distributed algorithms are proposed: transforming a tree into a linear tree and transforming a linear tree into a tree with a minimum Wiener index. It is proved that both algorithms have complexity no higher than 2n–2, where n is the number of tree vertices. We also consider the transformation of arbitrary undirected graphs, in which there can be cycles, multiple edges and loops, without restricting the degree of the vertices. It is shown that any connected graph with n vertices can be transformed into any other connected graph with k vertices and the same number of edges in no more than 2(n+k)–2.

Article Details

Author Biography

Igor Borisovich Burdonov

Leading Researcher, Ivannikov Institute for System Programming of the RAS. Research interests - modeling and verification of software systems, graph theory, automata

References

Wiener H. Structural determination of paraffin boiling points // J. Am. Chem. Soc. 1947. No 69 (1). P. 17–20.

Кочкаров A.A., Сенникова Л.И., Кочкаров Р.А. Некоторые особенности применения динамических графов для конструирования алгоритмов взаимо-действия подвижных абонентов // Известия ЮФУ. Технические науки, раздел V, cистемы и пункты управления. 2015. №1. С. 207–214.

А.В. Проскочило, А.В. Воробьев, М.С. Зряхов, А.С. Кравчук. Анализ состояния и перспективы развития самоорганизующихся сетей // Научные ведомости, серия экономика, информатика, выпуск 36/1. 2015. № 19 (216). С. 177–186.

Pathan A.S.K. (ed.). Security of self-organizing networks: MANET, WSN, WMN, VANET. CRC press, 2010. 638 p.

Boukerche A. (ed.). Algorithms and protocols for wireless, mobile Ad Hoc networks // John Wiley & Sons, 2008. 496 p.

Chen Z., Li S., Yue W. SOFM Neural Network Based Hierarchical Topology Control for Wireless Sensor Networks // Hindawi Publishing Corporation. J. of Sensors. 2014. article ID 121278. 6 p. http://dx.doi.org/10.1155/2014/121278

Mo S., Zeng J.-C., Tan Y. Particle Swarm Optimization Based on Self-organizing Topology Driven by Fitness // International Conference on Computational Aspects of Social Networks, CASoN 2010, Taiyuan, China, 10.1109/CASoN. 2010. No 13. P. 23–26.

Wen C.-Y., Tang H.-K. Autonomous distributed self-organization for mobile wireless sensor networks // Sensors (Basel, Switzerland). 2009. V. 9, 11. P. 8961–8995.

Llorca J., Milner S.D., Davis C. Molecular System Dynamics for Self-Organization in Heterogeneous Wireless Networks // EURASIP J. on Wireless Communications and Networking. 2010. 10.1155/2010/548016. 13 p.

Wai-kai C. Net Theory And Its Applications: Flows In Networks. Imperial College Press (26 May 2003). 672 p.

Wang H. On the Extremal Wiener Polarity Index of Hückel Graphs // Computational and Mathematical Methods in Medicine. 2016. article ID 3873597. 6 p. http://dx.doi.org/10.1155/2016/3873597

Xu X., Gao Y., Sang Y., Liang Y. On the Wiener Indices of Trees Ordering by Diameter-Growing Transformation Relative to the Pendent Edges // Mathematical Problems in Engineering. 2019. article ID 8769428. 11 p. https://doi.org/ 10.1155/2019/8769428

The On-Line Encyclopedia of Integer Sequences (OEIS). http://oeis.org/

Fischerman M., Hoffmann A., Rautenbach D., Székely L., Volkmann L. Wiener index versus maximum degree in trees // Discrete Applied Mathematics. 2002. V. 122. Is. 1–3. P. 127–137.

Бурдонов И. Самотрансформация деревьев с ограниченной степенью вершин с целью минимизации или максимизации индекса Винера// Труды ИСП РАН. 2019. Т. 31. Вып. 4. С. 189–210.



Presenting an article for publication in the Russian Digital Libraries Journal (RDLJ), the authors automatically give consent to grant a limited license to use the materials of the Kazan (Volga) Federal University (KFU) (of course, only if the article is accepted for publication). This means that KFU has the right to publish an article in the next issue of the journal (on the website or in printed form), as well as to reprint this article in the archives of RDLJ CDs or to include in a particular information system or database, produced by KFU.

All copyrighted materials are placed in RDLJ with the consent of the authors. In the event that any of the authors have objected to its publication of materials on this site, the material can be removed, subject to notification to the Editor in writing.

Documents published in RDLJ are protected by copyright and all rights are reserved by the authors. Authors independently monitor compliance with their rights to reproduce or translate their papers published in the journal. If the material is published in RDLJ, reprinted with permission by another publisher or translated into another language, a reference to the original publication.

By submitting an article for publication in RDLJ, authors should take into account that the publication on the Internet, on the one hand, provide unique opportunities for access to their content, but on the other hand, are a new form of information exchange in the global information society where authors and publishers is not always provided with protection against unauthorized copying or other use of materials protected by copyright.

RDLJ is copyrighted. When using materials from the log must indicate the URL: index.phtml page = elbib / rus / journal?. Any change, addition or editing of the author's text are not allowed. Copying individual fragments of articles from the journal is allowed for distribute, remix, adapt, and build upon article, even commercially, as long as they credit that article for the original creation.

Request for the right to reproduce or use any of the materials published in RDLJ should be addressed to the Editor-in-Chief A.M. Elizarov at the following address: amelizarov@gmail.com.

The publishers of RDLJ is not responsible for the view, set out in the published opinion articles.

We suggest the authors of articles downloaded from this page, sign it and send it to the journal publisher's address by e-mail scan copyright agreements on the transfer of non-exclusive rights to use the work.