A lower bound on the $k$-conversion number of graphs of maximum degree $k+1

‎‎We derive a new sharp lower bound on the $k$-conversion number of graphs of maximum degree $k+1$‎. ‎This generalizes a result of W.~Staton [Induced forests in cubic graphs‎, ‎Discrete Math.‎,49 (‎1984) ‎175--178‎]‎, ‎which established a lower bound on the $k$-conversion number of $(k+1)$-regular g...

Full description

Saved in:
Bibliographic Details
Published in:Transactions on combinatorics 2019-09, Vol.8 (3), p.1-12
Main Authors: Christina Mynhardt, Jane Wodlinger
Format: Article
Language:English
Subjects:
conversion number, conversion set
irreversible k-threshold conversion process
network diffusion process
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:‎‎We derive a new sharp lower bound on the $k$-conversion number of graphs of maximum degree $k+1$‎. ‎This generalizes a result of W.~Staton [Induced forests in cubic graphs‎, ‎Discrete Math.‎,49 (‎1984) ‎175--178‎]‎, ‎which established a lower bound on the $k$-conversion number of $(k+1)$-regular graphs‎.
ISSN:2251-8657
2251-8665
DOI:10.22108/toc.2019.112258.1579