Edge-connectivity and pairwise disjoint perfect matchings in regular graphs
From MaRDI portal
Publication:6548022
Consider regular graphs which may have parallel edges but no loops. If a graph has a set of \(k\) pairwise disjoint perfect matchings we say that it has a \(k\)-PDPM. For \(0 \leq t \leq r\), Let \(m(t,r)\) be the maximum number \(s\) such that every \(t\)-edge-connected \(r\)-graph has an \(s\)-PDPM. The authors improve upper bounds for \(m(t,r)\) by establishing that \(m(2l,r) \leq 3 l - 6\) for every \(l \geq 3\) and \(r \geq 2 l\).
Recommendations
- On the number of disjoint perfect matchings of regular graphs with given edge connectivity
- Pairwise Disjoint Perfect Matchings in r-Edge-Connected r-Regular Graphs
- Highly edge‐connected regular graphs without large factorizable subgraphs
- Perfect matchings in regular bipartite graphs
- Maximum matchings in a regular graph of specified connectivity and bounded order
Cites work
- Chromatic-index-critical graphs of even order
- Factorizing regular graphs
- Highly edge‐connected regular graphs without large factorizable subgraphs
- Indecomposabler-graphs and some other counterexamples
- On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
- Pairwise Disjoint Perfect Matchings in r-Edge-Connected r-Regular Graphs
- Regular n-valent n-connected non-Hamiltonian non n-edge-colourable graphs
This page was built for publication: Edge-connectivity and pairwise disjoint perfect matchings in regular graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6548022)
