Name
Abstract | ||
|---|---|---|
Switches are operations which make local changes to the edges of a graph, usually with the aim of preserving the vertex degrees. We study a restricted set of switches, called triangle switches. Each triangle switch creates or deletes at least one triangle. Triangle switches can be used to define Markov chains which generate graphs with a given degree sequence and with many more triangles (3-cycles) than is typical in a uniformly random graph with the same degrees. We show that the set of triangle switches connects the set of all d-regular graphs on n vertices, for all d >= 3. Hence, any Markov chain which assigns positive probability to all triangle switches is irreducible on these graphs. We also investigate this question for 2-regular graphs. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1007/978-3-030-79987-8_22 | COMBINATORIAL ALGORITHMS, IWOCA 2021 |
Keywords | DocType | Volume |
Regular graphs, Triangles, Markov chains, Irreducibility | Conference | 12757 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Colin Cooper | 1 | 287 | 30.73 |
| Martin E. Dyer | 2 | 529 | 116.66 |
| Catherine Greenhill | 3 | 628 | 62.40 |