Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Rainbow cycles in flip graphs

Tools
- Tools
+ Tools

Felsner, Stefan, Kleist, Linda, Mutze, Torsten and Sering, Leon (2020) Rainbow cycles in flip graphs. SIAM Journal on Discrete Mathematics, 34 (1). pp. 1-39. doi:10.1137/18M1216456

[img]
Preview
PDF
WRAP-Rainbow-cycles-flip-graphs-Mutze-2020.pdf - Accepted Version - Requires a PDF viewer.

Download (2753Kb) | Preview
Official URL: https://doi.org/10.1137/18M1216456

Request Changes to record.

Abstract

The flip graph of triangulations has as vertices all triangulations of a convex $n$-gon, and an edge between any two triangulations that differ in exactly one edge. An $r$-rainbow cycle in this graph is a cycle in which every inner edge of the triangulation appears exactly $r$~times. This notion of a rainbow cycle extends in a natural way to other flip graphs. In this paper we investigate the existence of $r$-rainbow cycles for three different flip graphs on classes of geometric objects: the aforementioned flip graph of triangulations of a convex $n$-gon, the flip graph of plane trees on an arbitrary set of $n$~points, and the flip graph of non-crossing perfect matchings on a set of $n$~points in convex position. In addition, we consider two flip graphs on classes of non-geometric objects: the flip graph of permutations of $\{1,2,\dots,n\}$ and the flip graph of $k$-element subsets of $\{1,2,\dots,n\}$. In each of the five settings, we prove the existence and non-existence of rainbow cycles for different values of~$r$, $n$ and~$k$.

Item Type: Journal Article
Alternative Title:
Subjects: Q Science > QA Mathematics
Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions: Faculty of Science > Computer Science
Library of Congress Subject Headings (LCSH): Graph theory, Gray codes, Spanning trees (Graph theory), Computer science -- Mathematics
Journal or Publication Title: SIAM Journal on Discrete Mathematics
Publisher: Society for Industrial and Applied Mathematics
ISSN: 0895-4801
Official Date: 2 January 2020
Dates:
DateEvent
2 January 2020Published
23 September 2019Accepted
Volume: 34
Number: 1
Page Range: pp. 1-39
DOI: 10.1137/18M1216456
Status: Peer Reviewed
Publication Status: Published
Publisher Statement: “First Published in SIAM Journal on Discrete Mathematics in 34,1, 2020, published by the Society for Industrial and Applied Mathematics (SIAM)” and the copyright notice as stated in the article itself (e.g., “Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.”)
Access rights to Published version: Restricted or Subscription Access
Copyright Holders: © 2020, Society for Industrial and Applied Mathematics
Related URLs:
  • https://epubs.siam.org/doi/abs/10.1137/1...
Open Access Version:
  • https://arxiv.org/abs/1712.07421

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us