The K-spread resistance of graph

College

College of Science

Department/Unit

Mathematics and Statistics Department

Document Type

Archival Material/Manuscript

Publication Date

2010

Abstract

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.

html

Disciplines

Mathematics

Note

Publication/creation date supplied
Abstract only

Keywords

Probabilities

Upload File

wf_no

This document is currently not available here.

Share

COinS