The K-spread resistance of graph

• Main Author: Lapus, Raymond R.
• Format: text
• Published: Animo Repository 2010
• Subjects: Probabilities; Mathematics
• Online Access: https://animorepository.dlsu.edu.ph/faculty_research/7814
• Institution: De La Salle University

Let G = (V, E) be a finite, nontrivial and loopless graph. We define the spread process in recursive manner. At the start of the process; i.e., k = 0, we assume s ∈ V is labelled. We set t ∈ V \ { s} to be our target vertex. Suppose A ⊆ V is a nonempty set of labelled vertices at time step k > 0. At the succeeding time step, the (common) label in A propagates to some vertex on the neighbourhood of A with probability p. The process terminates when tis labelled for the first time. By the (s, t)-spread resistance of G, denoted by PG(s, t), we mean the expression PG ( s, t) = lim p • Tst ( G), p→0 where Tst(G) is the average time starting from s, that the propagation of labels reaches t for the first time. That is, pc(s, t) is the limit of the ratio between Tst(G) and the rate of propagation of label along the edge as p approaches 0. In this talk, we propose an inclusion-exclusion analogue for the well-established Pc(s, t) in the perspective of the process of spreading the label from s to at least one vertex in K ⊆ V such that s ∉ K.