Highly edge‐connected regular graphs without large factorizable subgraphs

DOI10.1002/JGT.22729MaRDI QIDQ6056797zbMATH OpenOpenAlexFDO

Authors Davide Mattiolo, Eckhard Steffen

Publication date 4 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.09704

zbMATH Keywords

\(r\)-graphsfactorizationsperfect matchingsregular graphs

Mathematics Subject Classification ID

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

Abstract: We construct highly edge-connected $r$-regular graph which do not contain $r-2$ pairwise disjoint perfect matchings. The results partially answer a question stated by Thomassen [Factorizing regular graphs, J. Comb. Theory Ser. B (2019), https://doi.org/10.1016/j.jctb.2019.05.002 (article in press)].

Recommendations

• Pairwise Disjoint Perfect Matchings in r-Edge-Connected r-Regular Graphs
• On the number of disjoint perfect matchings of regular graphs with given edge connectivity
• Regular factors in regular graphs
• \(k\)-factors in regular graphs and edge-connectivity
• Perfect matchings in highly cyclically connected regular graphs

Cites work

• An upper bound for the excessive index of an r-graph
• Factorizing regular graphs
• Indecomposabler-graphs and some other counterexamples
• Regular n-valent n-connected non-Hamiltonian non n-edge-colourable graphs

Cited in

(7)

• scientific article; zbMATH DE number 3884203 (Why is no real title available?)
• Isomorphic factorizations VII. Regular graphs and tournaments
• Indecomposabler-graphs and some other counterexamples
• Maximally edge‐connected realizations and Kundu's k k‐factor theorem
• Pairwise Disjoint Perfect Matchings in r-Edge-Connected r-Regular Graphs
• Edge-connectivity and pairwise disjoint perfect matchings in regular graphs
• On a conjecture that strengthens Kundu's k-factor theorem

This page was built for publication: Highly edge‐connected regular graphs without large factorizable subgraphs

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