\((g,f)\)-factorization orthogonal to a star in graphs (Q1902277)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | \((g,f)\)-factorization orthogonal to a star in graphs |
scientific article |
Statements
\((g,f)\)-factorization orthogonal to a star in graphs (English)
0 references
14 July 1996
0 references
The author proves the existence of a factorization of a graph into factors which are orthogonal to a special subgraph of \(G\). Let \(G= (V, E)\) be a graph, \(H\) a spanning subgraph of \(G\), \(g(v)\) and \(f(v)\) integer functions defined on \(V\) with the property that \(g(v)\leq \deg_H(v)\leq f(v)\) for every vertex \(v\). Then \(H\) is called a \((g, f)\)-factor of \(G\). A factorization of \(G\) is a decomposition \(F= (F_1, F_2,\dots, F_m)\) of \(G\) into factors. A factorization \(F\) is orthogonal to a subgraph \(H\) of \(G\), if \(|E(H)\cap E(F_i)|= 1\) for all \(i\). Let \(G\) be an \((mg+ m- 1, mf- m+ 1)\)-graph. The main result of the paper establishes the existence of an \((f, g)\)-factorization \(F\) orthogonal to a given \(m\)-star \(H\) of \(G\). This result is the best possible with respect to the boundaries of the degree \(\deg(v)\) in \(G\).
0 references
star
0 references
factorization
0 references
factors
0 references