pith. sign in

arxiv: 1608.01189 · v2 · pith:45JGKYOFnew · submitted 2016-08-03 · 🧮 math.CO

On the power propagation time of a graph

classification 🧮 math.CO
keywords powerpropagationtimegraphwhoseedgegivegraphs
0
0 comments X
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.