On the problem of a matching orthogonal to a 2-factorization

DOI10.1016/S0012-365X(99)00359-3MaRDI QIDQ1978164zbMATH OpenOpenAlexFDO

Authors Mateja Šajna

Publication date 15 September 2000

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(99)00359-3

zbMATH Keywords

2-factorizationorthogonal matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

Let \(F\) be a 2-factorisation of a \(2d\)-regular graph \(G\). A subgraph \(H\) of \(G\) is orthogonal to \(F\) if every factor in \(F\) shares exactly one edge with \(H\). Alspach has asked when \(H\) can be chosen to be a matching orthogonal to \(F\). This paper shows that for every choice of \(G\) and \(F\) it is possible to find \(H\) orthogonal to \(F\) such that every component of \(H\) is either a single edge or a path of length 2. In addition, an upper bound is given for the number of paths of length 2 needed. For large \(d\) this bound is \((4d+8)/15\).

Recommendations

• On the existence of a matching orthogonal to a 2-factorization
• Orthogonal matchings revisited
• On solutions of Alspach's problems
• scientific article; zbMATH DE number 1798169

Cited in

(6)

• On the existence of a matching orthogonal to a 2-factorization
• Orthogonal matchings revisited
• Rainbow and orthogonal paths in factorizations of K_n
• scientific article; zbMATH DE number 913267 (Why is no real title available?)
• Orthogonal matchings
• Orthogonal matchings

This page was built for publication: On the problem of a matching orthogonal to a 2-factorization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1978164)