\((g, f)\)-factorizations randomly orthogonal to a subgraph in graphs (Q2581162)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | \((g, f)\)-factorizations randomly orthogonal to a subgraph in graphs |
scientific article |
Statements
\((g, f)\)-factorizations randomly orthogonal to a subgraph in graphs (English)
0 references
9 January 2006
0 references
A \((g,f)\)-factor of a graph \(G\) is a spanning subgraph \(F\) of \(G\) with \(g(x)\leq d_F(x)\leq f(x)\) for all \(x\in V(G)\). A \((f,g)\)-factorization \(\mathcal F=\{ F_1,F_2,\dots,F_m\}\) of \(G\) is a partition of \(E(G)\) into edge-disjoint \((g,f)\)-factors \(F_1,F_2,\dots,F_m\). Let \(H\) be a subgraph of \(G\). Then \(G\) has factorizations randomly \(k\)-orthogonal to \(H\) if for any partition \(\{A_1,A_2,\dots,A_k\}\) of \(E(H)\) with \(| A_i| =k\) there is an \((g,f)\)-factorization \(\mathcal F=\{F_1,F_2,\dots,F_m\}\) of \(G\) such that \(A_i\subseteq E(F_i)\). Let \(2k-2\leq g(x)\leq f(x)\) for all \(x\in V(G)\), and let \(H\) be a subgraph of \(G\) with \(mk\) edges. It is proved that if \(G\) is an \((mg+m-1,mf-m+1)\)-graph then it has a \((g,f)\)-factorization randomly \(k\)-orthogonal to \(H\) under some special conditions.
0 references