|
|||||
 |
|
|
|
|
|
|
|
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. |
PDF Access Denied
We have not been able to recognize your IP address
3.133.119.66
as that of a subscriber to this journal.
Online access to the content of recent issues is by
subscription, or purchase of single articles.
Please contact your institution's librarian suggesting a subscription, for example by using our journal-recommendation form. Or, visit our subscription page for instructions on purchasing a subscription.
You may also contact us at
contact@msp.org
or by using our
contact form.
Or, you may purchase this single article for USD 30.00:
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). |
