k-factors in regular graphs and edge-connectivity

MaRDI QIDQ950664zbMATH OpenFDO

Authors Kenji Kimura, R. E. L. Aldred

Publication date 3 November 2008

Published in AKCE International Journal of Graphs and Combinatorics (Search for Journal in Brave)

zbMATH Keywords

edge-connectivityregular factorregular graph

Mathematics Subject Classification ID

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

Review text

Let \(\ell, r,m,n\) be integers such that \(r\geq 4\), \(2 \leq \ell \leq r\), \(0 \leq m, n\) and \(G\) be an \(r\)-regular \(\ell\)-edge-connected graph. \(G\) is an \((m,n;k)\)-factor graph if \(m \leq k \leq \frac{r}{2}\) and for each disjoint pair \(E_1,E_2 \subseteq E(G)\) with \(|E_1|=m\), \(|E_2|=n\), \(G\) has a \(k\)-factor \(F\) such that \(E_1 \subseteq E(F)\) and \(E_2 \cap E(F) = \emptyset\). It is shown that each of the following conditions: {\parindent=8mm \begin{itemize}\item[(i)]\(m=0\) and \(n\leq\lceil\frac{\ell+r}{2}\rceil -k\), \item[(ii)]\(1\leq m\leq\frac{k}{2}\) and \(m+n\leq\lceil\frac{\ell}{2}\rceil\), \item[(iii)]\(\frac{k}{2}< m\leq{k}\) and \(m+n\leq k+\lceil\frac{\ell-r}{2}\rceil\) \end{itemize}} is sufficient for an \(r\)-regular \(\ell\)-edge-connected graph to be either an \((m,n;k)\)-factor or nearly bipartite. This generalizes previous similar result by \textit{Y. Egawa} and \textit{K. Kotani} [``\(k\)-factors containing and avoiding specified sets of edges, AKCE Int. J. Graphs Comb. 4, No. 1, 11--19 (2007; Zbl 1142.05066)] on \(r\)-regular \(r\)-edge-connected graphs.

Recommendations

• \(k\) -factors in regular graphs
• Regular factors of regular graphs
• \(k\)-factors containing and avoiding specified sets of edges
• Regular factors in regular graphs
• \([a,b]\)-factors containing a given \(k\)-regular subgraph
• scientific article; zbMATH DE number 4055663
• Regular factors in vertex-deleted subgraphs of regular graphs
• scientific article; zbMATH DE number 1051287
• scientific article; zbMATH DE number 29671
• Pan-factorial property in regular graphs

Cited in

(22)

• k-regular factors and semi-k-regular factors in bipartite graphs
• \(k\)-regular factors and semi-\(k\)-regular factors in graphs
• Regular graph and some vertex-deleted subgraph
• Equitable factorizations of edge-connected graphs
• Factorizing regular graphs
• \(k\)-factors containing and avoiding specified sets of edges
• Cut-edges and regular factors in regular graphs of odd degree
• Two-edge-connected \([2,k]\)-factors in graphs
• scientific article; zbMATH DE number 3867381 (Why is no real title available?)
• scientific article; zbMATH DE number 3968625 (Why is no real title available?)
• scientific article; zbMATH DE number 4025480 (Why is no real title available?)
• Regular factors in K_1,n free graphs
• scientific article; zbMATH DE number 91036 (Why is no real title available?)
• scientific article; zbMATH DE number 2094762 (Why is no real title available?)
• r-Regular, r-connected decompositions of complete graphs
• Highly edge-connected factors using given lists on degrees
• scientific article; zbMATH DE number 2192197 (Why is no real title available?)
• scientific article; zbMATH DE number 2197948 (Why is no real title available?)
• Highly edge‐connected regular graphs without large factorizable subgraphs
• \(\{k,r-k\}\)-factors of \(r\)-regular graphs
• Factorizations of regular graphs
• \(k\) -factors in regular graphs

This page was built for publication: \(k\)-factors in regular graphs and edge-connectivity

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