Abstract:
The influence of the gluing and cloning on operations of subgraphs on the graph diameter is studied. The vertex-diameter graphs are defined as graphs, all vertices of which belong to diametric chains. The possibilities of their use in scaling graphs with a diameter limitation are considered. Examples of scaling of trees, fat trees, and vertex-diameter graphs using the operations of cloning and gluing are given. The diameter and complexity of the synthesis of such graphs are estimated.
Keywords:trees, fat trees, vertex-diameter graphs, diameter, dominating set with neighborhood, gluing and cloning operations.
Received: 16.02.2023
Document Type:
Article
UDC:519.175.2
Language: Russian
Citation:
M. A. Iordanskii, “Scaling Graphs with Diameter Constraint”, Diskr. Mat., 35:4 (2023), 46–57