The K-spread resistance of graph
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....
Saved in:
| Main Author: | |
|---|---|
| Format: | text |
| Published: |
Animo Repository
2010
|
| Subjects: | |
| Online Access: | https://animorepository.dlsu.edu.ph/faculty_research/7814 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | De La Salle University |
| Summary: | 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. |
|---|