In this section, we study a construction that adds a univeral point to a discrete graph.
Suppose that \((S, \rta)\) is a discrete graph and that \(e \notin S\). Extend \(\rta\) to \(S \cup \{e\}\) by making \(e\) a universal point so that \(x \rta e\) and \(e \rta x\) for all \(x \in S\). The graph \((S \cup \{e\}, \rta)\) is the cone graph associated with \((S, \rta)\) and \(e\).
This use of the term cone graph is not the only one, but is convenient for our purposes. The cone graph is also the join of \((S, \rta)\) and the null graph on \(\{e\}\).
Let \(\ms A\) denote the \(\sigma\)-algebra associated with \((S, \rta)\). Then the \(\sigma\)-algebra associated with the cone graph \((S \cup \{e\}, \rta)\) is \[\ms B = \ms A \cup \{A \cup \{e\}: A \in \ms A\}\]
Let \(A_x\) denote the set of right neighbors of \(x \in S\) for the graph \((S, \rta)\). By definition, the right neighbor sets for the corresponding cone graph \((S \cup \{e\}, \rta)\) are \(B_x = A_x \cup \{e\}\) for \(x \in S\) and \(B_t = S\). The \(\sigma\)-algebras associated with \((S, \rta)\) and \((S \cup \{e\}, \rta)\) are \(\ms A = \sigma(\{A_x: x \in S\})\) and \(\ms B = \sigma(\{B_x: x \in S\} \cup \{S\})\). So \(S \in \ms B\) and hence \(\{e\} \in \ms B\). Let \(\ms C = \ms A \cup \{A \cup\{e\}: A \in \ms A\}\). Then \(\ms C\) is a \(\sigma\)-algebra of subsets of \(S \cup \{e\}\) and contains \(B_x\) for \(x \in S\) and \(B_t\), so \(\ms B \subseteq \ms C\). On the other hand, the collections \(\ms D = \{A \subset S: A \in \ms B\}\) and \(\ms E = \{A \subset S: A \cup \{e\} \in \ms B\}\) are \(\sigma\)-algebras of subsets of \(S\) and each contains \(A_x\) for \(x \in S\). It follows that \(\ms A \subseteq \ms D\) and \(\ms A \subseteq \ms E\) and therefore \(\ms C \subseteq \ms B\).
It's easy to extend a probability distribution on \(S\) to one on \(S \cup \{e\}\).
Suppose that \(S\) is a countable set and \(e \notin S\). If \(f\) is a probability density function on \(S\) and \(p \in (0, 1)\), let \(g\) be the probability density function on \(S \cup \{e\}\) defined by \[g(x) = p f(x), \; x \in S; \quad g(e) = 1 - p\]
This is similar to the construction used for endpoint addition in Section 10: If \(Y\) is a random variable in \(S \cup \{e\}\) with density \(g\) then the conditional distribution of \(Y\) given \(Y \in S\) has density \(f\), and \(\P(Y \in S) = p\) so that \(\P(Y = e) = 1 - p\).
In the context of the construction in , suppose that \(F\) is the reliability function of \(f\) for the graph \((S, \rta)\) and \(G\) the reliability function of \(g\) for the cone graph \((S \cup \{e\}, \rta)\). Then \[G(x) = p F(x) + 1 - p, \; x \in S; \quad G(e) = p\]
As usual, we are particularly interested in distributions with constant rate for the cone graph.
Suppose again that \(f\) is a probability density function on \(S\) and that \(F\) is the reliability function of \(f\) for the graph \((S, \rta)\). If \(f = \alpha F + \alpha^2\) for some \(\alpha \in (0, \infty)\) then the density \(g\) constructed in definition with \(p = 1 / (1 + \alpha)\) has constant rate \(\alpha\) for the cone graph \((S \cup \{e\}, \rta)\).
Suppose that \(f = \alpha F + \alpha^2\) for some \(\alpha \in (0, \infty)\) and that \(g\) is constructed as in definition with \(p = 1 / (1 + \alpha)\). Then \begin{align*} g(x) & = p f(x) = \frac{1}{1 + \alpha} f(x) = \frac{\alpha}{1 + \alpha} F(x) + \frac{\alpha^2}{1 + \alpha}, \quad x \in S \\ g(e) & = 1 - p = \frac{\alpha}{1 + \alpha} \end{align*} and \begin{align*} G(x) & = p F(x) + 1 - p = \frac{1}{1 + \alpha} F(x) + \frac{\alpha}{1 + \alpha}, \quad x \in S \\ G(e) & = p = \frac{1}{1 + \alpha} \end{align*} Hence \(g = \alpha G\).
In general, is not very helpful. But if the original graph is right regular, more explicit results can be obtained for the corresponding cone graph. So in this subsection, suppose that \((S, \rta)\) is a right regular graph of order \(n\) and degree \(k\), where \(n, \, k \in \N_+\) with \(k \le n\).
The cone graph \((S \cup \{e\}, \rta)\) has a constant rate distribution with rate \[\alpha = \frac{2}{k + \sqrt{k^2 + 4 n}}\] and density funtion \(g\) given by \begin{align*} g(x) & = \frac{2}{2 n - k + \sqrt{k^2 + 4 n}}, \quad x \in S \\ g(e) & = \frac{\sqrt{k^2 + 4 n} - k}{2 n - k + \sqrt{k^2 + 4 n}} \end{align*}
Let \(f\) be the uniform density on \(S\) so that \(f(x) = 1 / n\) for \(x \in S\). Since the graph is right regular with degree \(k\) we have \(F(x) = k / n\) for \(x \in S\). From we have \[\frac{1}{n} = \alpha \frac{k}{n} + \alpha^2\] solving gives \[\alpha = \frac{\sqrt{k^2 + 4 n} - k}{2 n} = \frac{2}{k + \sqrt{k^2 + 4 n}}\] and then \[ p = \frac{1}{1 + \alpha} = \frac{2 n} {2 n - k + \sqrt{4 n + k^2}}\] So then the distribution with density \(g\) constructed in from \(f\) and \(p\) has constant rate \(\alpha\)
Let \(v_m\) denote the right walk function of order \(m \in \N_+\) for the cone graph \((S \cup \{e\}, \rta)\). Then \(v_m(x) = a_m\) for \(x \in S\) and \(v_m(e) = n a_{m - 1}\) where \[a_m = \left(\frac{1}{2} + \frac{k + 2}{2 \sqrt{k^2 + 4 n}}\right) \left(\frac{k + \sqrt{k^2 + 4 n}}{2}\right)^m + \left(\frac{1}{2} - \frac{k + 2}{2 \sqrt{k^2 + 4 n}}\right) \left(\frac{k - \sqrt{k^2 + 4 n}}{2}\right)^m\]
Since \((S, \rta)\) is right regular, \(v_m\) is constant on \(S\). So let \(a_m\) denote the constant value on \(S\) and let \(b_m = v_m(e)\). Then \begin{align*} a_{m + 1} & = k a_m + b_m \\ b_{m + 1} & = n a_m \end{align*} which leads to the second order difference equation \(a_{m + 2} - k a_{m + 1} - n a_m = 0\). The corresponding characteristic equation is \(r^2 - k r - n = 0\) which has roots \[\frac{k \pm \sqrt{k^2 + 4 n}}{2}\] Applying the initial conditions \(a_0 = 1\), \(a_1 = k + 1\) then leads to the result.
It follows that the number of walks of length \(m \in \N_+\) is \(w_m = n (a_m + a_{m - 1})\), and hence the right walk distribution of order \(m\) has density function \(g_m\) given by \begin{align*} g_m(x) & = \frac{a_m}{n (a_m + a_{m - 1})}, \quad x \in S \\ g_m(e) & = \frac{a_{m - 1}}{a_m + a_{m - 1}} \end{align*} It's easy to show directly that \(w_m / w_{m + 1} \to \alpha\) as \(m \to \infty\) and that \(g_m \to g\) as \(m \to \infty\) where \(\alpha\) is the rate constant and \(g\) the constant rate density function in . Of course, these results are guaranteed by the general theory in Section 5.
The following examples revisit graphs that we have already studied, as a check on our work.
Suppose that \((S, \ne)\) is the complete irreflexive graph of order \(n \in \N_+\). The corresponding cone graph \((S \cup \{e\}, \ne)\) is the complete irreflexive graph of order \(n + 1\). For the cone graph, the uniform distribution on \(S \cup \{e\}\) has constant rate \(\alpha = 1 / n\).
Of course, we know this must be the case for a regular graph of degree \(n\).
Suppose that \((S, \lfrta)\) is the (symmetric) cycle of order \(n \in \{3, 4, \ldots\}\) so that the corresponding cone graph is the wheel with parameter \(n\). The constant rate distribution for the wheel graph has rate \[\alpha = \frac{\sqrt{n + 1} - 1}{n}\] and density function \(g\) given by \begin{align*} g(x) &= \frac{1}{n - 1 + \sqrt{n + 1}}, \quad x \in S \\ g(e) &= \frac{\sqrt{n + 1} - 1}{n - 1 + \sqrt{n + 1}} \end{align*}
Again, this agrees with our previous work with the wheel graph.
The app below is a simulation of the constant rate distribution on the wheel graph with parameter \(n\). The center (universal) point is labeled 0, and the points on the cycle by \(1, 2, \ldots, n\), oriented clockwise, starting with the point in the horizontal right position. The parameter \(n\) can be varied with the scrollbar.
The following example is a wheel with a directed cycle.
Suppose that \((S, \rta)\) is the directed cycle of order \(n \in \{3, 4, \ldots\}\) so that the corresponding cone graph is a wheel with parameter \(n\) and a directed cyle. The constant rate distribution for the wheel graph has rate \[\alpha = \frac{\sqrt{4 n + 1} - 1}{2 n}\] and density function \(g\) given by \begin{align*} g(x) &= \frac{2}{2 n - 1 + \sqrt{4 n + 1}}, \quad x \in S \\ g(e) &= \frac{\sqrt{4 n + 1} - 1}{2 n - 1 + \sqrt{4 n + 1}} \end{align*}
The standard cube graph \((S, \lfrta)\) has 8 vertices and is regular with degree 3. For the corresponding cone graph, the constant rate distribution has rate \[ \alpha = \frac{\sqrt{41} - 3}{16} \approx 0.2127 \] and density function \(g\) given by \[ g(x) = \frac{2}{13 + \sqrt{41}} \approx 0.1031, \; x \in S; \quad g(e) = \frac{\sqrt{41} - 3}{13 + \sqrt{41}} \approx 0.1754\]
In this subsection, we study an interesting class of graphs that generalize the star and the Dutch windmill graphs that appear in several of the earlier sections of this chapter.
Suppose that \(\{S_1, S_2, \ldots, S_k\}\) is a disjoint collection of sets, each with \(d\) elements, where \(k, \, d \in \N_+\). Let \((S, \lfrta)\) denote the union of the complete irreflexive graphs \((S_i, \ne)\) over \(i \in \{1, 2, \ldots, k\}\). Finally, let \((S \cup \{e\}, \lfrta)\) denote the cone graph obtained by joining a universal point \(e \notin S\). This graph is the general windmill graph with parameters \(k\) and \(d\).
So \((S, \lfrta)\) consists of \(k\) disjoint copies of the complete irreflexive graph of order \(d\), and so is regular with order \(k d\) and degree \(d - 1\). When \(d = 1\), the windmill graph is the star graph with parameter \(k\) and when \(d = 2\), the windmill graph is the Dutch windmill graph with parameter \(k\). When \(k = 1\), the graph is the complete irreflexive graph of order \(d + 1\), already studied in
Suppose that \((S \cup \{e\}, \lfrta)\) is the windmill graph with parameters \(k, \, d \in \N_+\), as described in .
Suppose again that \((S \cup \{e\}, \lfrta)\) is the windmill graph with parameters \(k, \, d \in \N_+\), as described in . The walk function \(v_m\) of order \(m \in \N\) is given by \(v_m(x) = a_m\) for \(x \in S\) and \(v_m(e) = k d a_{m - 1}\) where \[a_m = \left(\frac 1 2 + \frac{d + 1}{2 \sqrt{(d - 1)^2 + 4 k d}}\right) \left(\frac{d - 1 + \sqrt{(d - 1)^2 + 4 k d}}{2}\right)^m + \left(\frac 1 2 - \frac{d + 1}{2 \sqrt{(d - 1)^2 + 4 k d}}\right) \left(\frac{d - 1 - \sqrt{(d - 1)^2 + 4 k d}}{2}\right)^m\]
Suppose again that \((S \cup \{e\}, \lfrta)\) is the windmill graph with parameters \(k, \, d \in \N_+\), as described in . The unique constant rate distribution for the graph has rate \[\alpha = \frac{2}{(d - 1) + \sqrt{(d - 1)^2 + 4 k d}}\] and density function \(f\) given by \begin{align*} f(x) & = \frac{2}{1 + d(2 k -1) + \sqrt{(d - 1)^2 + 4 k d}}, \quad x \in S \\ f(e) & = \frac{2}{(d + 1) + \sqrt{(d - 1) + 4 k d}} \end{align*}
As noted earlier, when \(d = 1\), the windmill graph in is the star with parameter \(k\). The constant rate distribution for the star graph has rate \(\alpha = 1 / \sqrt{k}\) and density function \(g\) given by \[g(x) = \frac{1}{k + \sqrt{k}}, \; x \in S; \quad g(e) = \frac{1}{1 + \sqrt{k}}\]
Again, this agrees with our previous work on the star graph.
The app below is a simulation of the constant rate distribution on the star graph with parameter \(k\). The center (universal) point is labeled 0 and the endpoints by \(1, 2, \ldots, k\) oriented clockwise, starting with the endpoint in the horizontal right position. The number of endpoints \(k\) can be varied with the scrollbar.
As noted earlier, when \(d = 2\), the windmill graph in is the Dutch windmill graph with parameter \(k\). The constant rate distribution for this graph has rate \[\alpha = \frac{1}{1 + \sqrt{1 + 8 k}}\] and density function \(g\) given by \begin{align*} g(x) & = \frac{2}{4 k - 1 + \sqrt{1 + 8 k}}, \; x \in S\\ g(e) &= \frac{2}{3 + \sqrt{1 + 8 k}} \end{align*}
Again, this agrees with our previous work.
The app below is a simulation of the constant rate distribution on the dutch windmill graph with parameter \(k\). The center (the universal point) is labeled 0 and the outer points by \(1, 2, \ldots, 2 k\) oriented clockwise, starting with the point in the horizontal right position. The parameter \(k\) can be varied with the scrollbar.