|
|||||
 |
|
|
|
|
|
|
|
New ordering
methods to construct contagious sets and induced degenerate
subgraphs
Connor C. Anderson, Akshaj Balasubramanian, Henry Poskanzer, Daniel Reichman and Gábor N. Sárközy |
|
Vol. 16 (2023), No. 1, 59–68
|
Abstract |
|
Randomly ordering vertices in graphs has been useful in deriving upper bounds for the minimal size of contagious sets (where every vertex has threshold ) and lower bounds on the cardinality of -degenerate induced subgraphs. We introduce a new method of randomly picking permutations from the family of all permutations for which the degree sequence is either nonincreasing or nondecreasing, and we show that this method may result in improved bounds for certain graphs for contagious sets or -degenerate induced subgraphs. We also reanalyze an algorithm by Reichman for finding contagious sets and obtain a stronger upper bound on the size of the contagious set produced by this algorithm. |
Keywords
contagious sets, degenerate subgraphs
|
Mathematical Subject Classification
Primary: 05C35
Secondary: 05C69
|
Milestones
Received: 28 July 2021
Revised: 5 April 2022
Accepted: 20 April 2022
Published: 14 April 2023
Communicated by Kenneth S. Berenhaut
|
Authors |
| Connor C. Anderson | |
| Computer Science Department Worcester Polytechnic Institute Worcester, MA United States |
|
| Akshaj Balasubramanian | |
| Computer Science Department Worcester Polytechnic Institute Worcester, MA United States |
|
| Henry Poskanzer | |
| Computer Science Department Worcester Polytechnic Institute Worcester, MA United States |
|
| Daniel Reichman | |
| Computer Science Department Worcester Polytechnic Institute Worcester, MA United States |
|
| Gábor N. Sárközy | |
| Computer Science Department Worcester Polytechnic Institute Worcester, MA United States |
|
| © 2023 MSP (Mathematical Sciences Publishers). |
