Intersections of Cycling 2-factors

2014/05/05 by Drew J. Lipman, Lipman, Drew J.
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1405.0889

Presented at: Forty-Fifth Southeastern International Conference on Combinatorics, Graph Theory, and Computing

arxiv created 2014/05/05 · arxiv updated 2014/05/06

Abstract

Define an embedding of graph G=(V,E) with V a finite set of distinct points on the unit circle and E the set of line segments connecting the points. Let V₁,…,V_k be a labeled partition of V into equal parts. A 2-factor is said to be \em cycling if for each u∈ V, u∈ V_i implies u is adjacent to a vertex in V_{i+1 (mod k)} and a vertex in V_{i-1 (mod k)}. In this paper, we will present some new results about cycling 2-factors including a tight upper bound on the minimum number of intersections of a cycling 2-factor for k=3.

Related

• A spanning union of cycles in rectangular grid graphs, thick grid cylinders and Moebius strips
• A note on uniquely embeddable 2-factors
• A spanning union of cycles in thin cylinder, torus and Klein bottle grid graphs
• Cycle factors and renewal theory
• A note on the number of non-cycle components in a pseudo 2-factor of graphs