\((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
    0 references
    0 references
    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
    0 references
    0 references
    0 references
    0 references