On the power propagation time of a graph
classification
🧮 math.CO
keywords
powerpropagationtimegraphwhoseedgegivegraphs
read the original abstract
In this paper, we give Nordhaus-Gaddum upper and lower bounds on the sum of the power propagation time of a graph and its complement, and we consider the effects of edge subdivisions and edge contractions on the power propagation time of a graph. We also study a generalization of power propagation time, known as $k-$power propagation time, by characterizing all simple graphs on $n$ vertices whose $k-$power propagation time is $n-1$ or $n-2$ (for $k\geq 1$) and $n-3$ (for $k\geq 2$). We determine all trees on $n$ vertices whose power propagation time ($k=1$) is $n-3$, and give partial characterizations of graphs whose $k-$power propagation time is equal to 1 (for $k\geq 1$).
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.