On \((n,k)\)-orthogonal factorizations in subgraphs of graphs
type: Item
instance of: scholarly article
zbMATH Open document ID: 0998.05054
author: Jianxiang Li
publication date: 2002-11-24T00:00:00Z
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1719412
zbMATH Keywords: orthogonal factorizations
zbMATH Keywords: decomposition
zbMATH Keywords: \((g,f)\)-factorization
MaRDI profile type: Publication
title: On \((n,k)\)-orthogonal factorizations in subgraphs of graphs
published in: Journal of Mathematical Study
review text: Let \(f\) and \(g\) be two integer-valued functions defined on the set of vertices \(V(G)\) of a graph \(G\). A spanning subgraph \(F\) of \(G\) is called a \((g,f)\)-factor of \(G\) if for all vertices \(x\in V(G)\), \(g(x)\leq \deg_F(x)\leq f(x)\), where \(\deg_F(x)\) denotes the degree of the vertex \(x\) in \(F\). By a \((g,f)\)-factorization of a graph \(G\) we mean a partition \(\{F_1,\dots, F_n\}\) of the edge set \(E(G)\) of \(G\) into \((g,f)\)-factors \(F_1,\dots, F_n\). Let \(n\), \(m\), \(k\) be integers such that \(1\leq n< m\leq 2k\) and \(f\) and \(g\) integer-valued functions defined on \(V(G)\) such that \(g(x)\geq 2k-1\), for every \(x\in V(G)\). Moreover, let \(G\) be a graph whose degrees of vertices are between \(mg+n\) and \(mf- n\) and let \(H\) be a subgraph of \(G\) with \(nk\) edges. Under these assumptions the author proves that the graph \(G\) has a subgraph \(G'\) which admits a \((g,f)\)-factorization \(F_1,\dots, F_n\) such that each graph \(F_i\), \(i= 1,\dots, n\), has precisely \(k\) common edges with \(H\).
reviewed by: Zbigniew Lonc
description: scientific article; zbMATH DE number 1719412