A new result on Alspach's problem (Q1808723)

From MaRDI portal
scientific article
Language Label Description Also known as
English
A new result on Alspach's problem
scientific article

    Statements

    A new result on Alspach's problem (English)
    0 references
    0 references
    16 February 2000
    0 references
    A graph \(G=(V,E)\) is called a \((g,f)\)-graph if there are integer-valued functions \(f,g\) defined on \(V\) such that \(g(v)\leq \text{deg}(v) \leq f(v)\) for each \(v\in V\), where \(\text{deg}(v)\) is the degree of \(v\). A \((g,f)\)-factor of \(G\) is a spanning \((g,f)\)-subgraph of \(G\). A \((g,f)\)-factorization \({\mathcal{F}}=\{F_1, F_2, \dots, F_t\}\) of \(G\) is a partition of \(E\) into edge-disjoint \((g,f)\)-factors. A subgraph \(H\) of \(G\) is orthogonal to \({\mathcal{F}}\) if \(|E(H)\cap E(F_i)|=1\) for each \(i\in \{1, 2, \dots, t\}\). The author proves the following result: \(G=(V,E)\) be a graph, \(m>0\) be an integer, \(H\) be a subgraph of \(G\) with \(m\) edges, \(f(v)\geq 2\) and \( g(v)\geq 5\) be integer-valued functions on \(V\). If \(G\) is an \((mg +m -1, mf - m +1)\)-graph then there exists a \((g,f)\)-factorization of \(G\) orthogonal to \(H\).
    0 references
    0 references
    factorization
    0 references
    0 references
    0 references