Factorizations of regular graphs

DOI10.1016/0095-8956(92)90008-LMaRDI QIDQ922555zbMATH OpenOpenAlexFDO

Authors Cun-Quan Zhang, Yongjin Zhu

Publication date 1992

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0095-8956(92)90008-l

zbMATH Keywords

edge-disjoint 1-factorsfactorizationHamilton pathk-regular graph

Mathematics Subject Classification ID

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

Review text

Let G be a k-regular graph of order 2n such that \(k\geq n\). \textit{A. J. W. Hilton} [J. Graph Theory 9, 193-196 (1985; Zbl 0624.05050)] proved that G contains at least \(\lfloor k/3\rfloor\) edge-disjoint 1-factors. Hilton's theorem is improved in this paper that G contains at least \(\lfloor k/2\rfloor\) edge-disjoint 1-factors. The following result is also proved in this paper. Let G be a 2-connected, k-regular, non-bipartite graph of order at most 3k-3 and x, y be a pair of distinct vertices. If \(G\setminus \{x,y\}\) is connected, then g contains an (x,y)-Hamilton path.

Recommendations

• scientific article; zbMATH DE number 4106904
• \(k\) -factors in regular graphs
• Regular factors in regular graphs
• Hamiltonian ?-factors in graphs
• \(k\)-factors in regular graphs and edge-connectivity

Cites work

• Factorizations of regular graphs of high degree
• Graph theory with applications
• scientific article; zbMATH DE number 3884203 (Why is no real title available?)
• scientific article; zbMATH DE number 4085685 (Why is no real title available?)
• scientific article; zbMATH DE number 4106904 (Why is no real title available?)
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 3733963 (Why is no real title available?)
• scientific article; zbMATH DE number 3046496 (Why is no real title available?)
• Some Theorems on Abstract Graphs

Cited in

(17)

• Factors of regular graphs
• Regular factors of simple regular graphs and factor-spectra
• Factorisations of 4-regular graphs and Petersen's theorem
• Regular factors in regular graphs
• On 2-factors with a bounded number of odd components
• Hamiltonian cycles and 1-factors in 5-regular graphs
• scientific article; zbMATH DE number 5130724 (Why is no real title available?)
• scientific article; zbMATH DE number 3896976 (Why is no real title available?)
• Factors in a class of regular digraphs
• scientific article; zbMATH DE number 4106904 (Why is no real title available?)
• Generalizations of Dirac's theorem in Hamiltonian graph theory -- a survey
• scientific article; zbMATH DE number 33169 (Why is no real title available?)
• The number of disjoint perfect matchings in semi-regular graphs
• scientific article; zbMATH DE number 3893248 (Why is no real title available?)
• On magic and consecutive antimagic factorizations of graphs
• On the number of disjoint perfect matchings of regular graphs with given edge connectivity
• Graph factors and factorization: 1985--2003: a survey

This page was built for publication: Factorizations of regular graphs

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