The maximum infection time of the \(P_3\) convexity in graphs with bounded maximum degree

DOI10.1016/J.DAM.2018.05.053zbMath1401.05159OpenAlexW2807750940MaRDI QIDQ1627866

Thiago Marcilon, Rudini Menezes Sampaio

Publication date: 3 December 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2018.05.053

zbMATH Keywords

graph convexitymaximum infection time\(P_3\) convexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Target set selection with maximum activation time

Cites Work

• Unnamed Item
• On slowly percolating sets of minimal size in bootstrap percolation
• Inapproximability results related to monophonic convexity
• Bootstrap percolation in living neural networks
• A simplified NP-complete satisfiability problem
• Bootstrap percolation in three dimensions
• The maximum infection time in the geodesic and monophonic convexities
• Growth rates and explosions in sandpiles
• Complexity results related to monophonic convexity
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• The hull number of a graph
• On local convexity in graphs
• Convex sets in graphs. II: Minimal path convexity
• Sharp metastability threshold for two-dimensional bootstrap percolation
• The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects
• The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
• On two geometric problems related to the travelling salesman problem
• Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
• Convexity in Graphs and Hypergraphs
• Hamilton Paths in Grid Graphs
• On the Carathéodory Number for the Convexity of Paths of Order Three
• The sharp threshold for bootstrap percolation in all dimensions

This page was built for publication: The maximum infection time of the \(P_3\) convexity in graphs with bounded maximum degree