On the lower bound for the spread process in a graph

Authors

Raymond R. Lapus

College

College of Science

Department/Unit

Mathematics and Statistics Department

Document Type

Conference Proceeding

Source Title

Colloquium on Combinatorics

Publication Date

2010

Abstract

Let G = (V, E) be a finite, nontrivial and loopless graph. We assume that s ∈ V is labelledat the start of the process. This label independently propagates along the edges of G to the neighbouring vertices in one discrete time step with the probability p. Define T_st(G) to be the expected time that the process of spreading the label reaches the target vertex t for the first time. In this talk, we propose a lower bound for T_st(G) in terms of the reliability polynomial of G.

html

Recommended Citation

Lapus, R. R. (2010). On the lower bound for the spread process in a graph. Colloquium on Combinatorics Retrieved from https://animorepository.dlsu.edu.ph/faculty_research/7815

Disciplines

Mathematics

Note

Abstract only

Keywords

Graph theory

Upload File

wf_no