Skip to main content

Research Repository

Advanced Search

The complexity of growing a graph

Mertzios, G.B.; Michail, O.; Skretas, G.; Spirakis, P.G.; Theofilatos, M.


O. Michail

G. Skretas

P.G. Spirakis

M. Theofilatos


We study a new algorithmic process of graph growth. The process starts from a single initial vertex u0 and operates in discrete timesteps, called slots. In every slot t ≥ 1, the process updates the current graph instance to generate the next graph instance Gt. The process first sets Gt = Gt−1. Then, for every u ∈ V (Gt−1), it adds at most one new vertex u 0 to V (Gt) and adds the edge uu0 to E(Gt) alongside any subset of the edges {vu0 | v ∈ V (Gt−1) is at distance at most d − 1 from u in Gt−1}, for some integer d ≥ 1 fixed in advance. The process completes slot t after removing any (possibly empty) subset of edges from E(Gt). Removed edges are called excess edges. Gt is the graph grown by the process after t slots. The goal of this paper is to investigate the algorithmic and structural properties of this process of graph growth.


Mertzios, G., Michail, O., Skretas, G., Spirakis, P., & Theofilatos, M. (2022). The complexity of growing a graph. In ALGOSENSORS 2022: Algorithmics of Wireless Networks (123-137).

Conference Name 18th International Symposium on Algorithmics of Wireless Networks (ALGOSENSORS 2022)
Conference Location Potsdam, Germany
Start Date Sep 5, 2022
End Date Sep 9, 2022
Acceptance Date Aug 1, 2022
Online Publication Date Dec 13, 2022
Publication Date Dec 13, 2022
Deposit Date Sep 27, 2022
Publicly Available Date Dec 14, 2023
Publisher Springer Verlag
Volume 13707
Pages 123-137
Series Title Lecture Notes in Computer Science
Book Title ALGOSENSORS 2022: Algorithmics of Wireless Networks
ISBN 9783031220494
Additional Information September 8–9, 2022


This file is under embargo until Dec 14, 2023 due to copyright restrictions.

You might also like

Downloadable Citations