Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

19
votes
1answer
302 views
+250

Zombie outbreak on a $k$-regular graph

Suppose we have a zombie outbreak on a connected $k$-regular graph of order $n$. There are $n_0$ initially infected zombie nodes, and each turn, each zombie infects its neighbors with probability ...
1
vote
1answer
31 views
+50

Proof completion: Determine a simple expression for $\tau(G)$ in terms of the vertex degrees of $G$. (details inside)

I need some help completing a proof I wrote (or seeing a simpler solution to the same problem). For a list of paths $P_1, \ldots , P_m$, let $L(P_1, \ldots, P_m)$ be the number of paths in $P_1, ...