(g,f)-factorizations of graphs orthogonal to [1,2]-subgraphs

DOI10.1007/BF02009545MaRDI QIDQ1375339zbMATH OpenWikidataFDO

Authors Gunying Yan

Publication date 30 March 1998

Published in Acta Mathematicae Applicatae Sinica. English Series (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02009545

zbMATH Keywords

\((g,f)\)-factorization \((g,f)\)-graph orthogonal factor

Mathematics Subject Classification ID

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

Review text

A graph \(G\) is called a \((g,f)\)-graph if for every vertex \(v\) of \(G\), \(g(v)\leq d_G(v)\leq f(v)\), where \(g\) and \(f\) are integer-valued functions defined on the vertex set of \(G\), \(d_G(v)\) denotes the degree of the vertex \(v\) in \(G\), and \(g(v)\leq f(v)\) for all \(v\) in \(G\). A \((g,f)\)-factorization \({\mathcal F}=\{F_1,F_2,\ldots, F_t\}\) of \(G\) is a partition of the edge set of \(G\) into spanning \((g,f)\)-subgraphs. A subgraph \(H\) of \(G\) is orthogonal to \({\mathcal F}\) if \(|E(H)\cap E(F_i)|=1\) for \(1\leq i\leq t\). Let \(m\) be a positive integer, and let \(g(v)\leq f(v)\) be integer-valued functions defined on the vertex set of \(G\). The author proves that if \(G\) is a \((mg+m-1,mf-m+1)\)-graph and \(H\) is a \([1,2]\)-subgraph with \(m\) edges, then there exists a \((g,f)\)-factorization of \(G\) orthogonal to \(H\).

Recommendations

Cites work

Cited in

(21)

This page was built for publication: \((g,f)\)-factorizations of graphs orthogonal to \([1,2]\)-subgraphs

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