Let G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two positive integer-valued functions defined on V(G) such that g(x) ≤ f(x) for every vertex x of V(G). Then a (g, f)-factor of G ...Let G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two positive integer-valued functions defined on V(G) such that g(x) ≤ f(x) for every vertex x of V(G). Then a (g, f)-factor of G is a spanning subgraph H of G such that g(x) ≤ dH(x) 5 f(x) for each x ∈ V(H). A (g, f)-factorization of G is a partition of E(G) into edge-disjoint (g, f)-factors. Let F = {F1, F2,…… ， Fm } and H be a factorization and a subgraph of G, respectively. If F, 1 ≤ i ≤ m， has exactly one edge in common with H, then it is said that ■ is orthogonal to H. It is proved that every bipartite (mg + m - 1, mf - m + 1 )-graph G has a (g, f)-factorization orthogonal to k vertex disjoint m-subgraphs of G if 2-k ≤ g(x) for all x ∈ V(G). Furthermore, it is showed that the results in this paper are best possible.展开更多
Let G be a graph with vertex set V（G） and edge set E（G）, and let g and f be two integer- valued functions defined on V（G） such that g（x）≤f（x） for all x ∈ V（G）. Then a （g, f）-factor of G is a spanning s...Let G be a graph with vertex set V（G） and edge set E（G）, and let g and f be two integer- valued functions defined on V（G） such that g（x）≤f（x） for all x ∈ V（G）. Then a （g, f）-factor of G is a spanning subgraph H of G such that g（x）≤d<sub>H</sub>（x）≤f（x） for all x ∈ V（G）. A （g, f）-factorization of G is a partition of E（G） into edge-disjoint （g,f）-factors. Let F={F<sub>1</sub>, F<sub>2</sub>...., F<sub>m</sub>} be a factorization of G, and H be a subgraph of G with mr edges. If F<sub>i</sub>. 1≤i≤m, has exactly r edges in common with H. then F is said to be r-orthogonal to H. In this paper it is proved that every （mg+kr, mf-kr）-graph. where m, k and r are positive integers with k【m and g≥r, contains a subgraph R such that R has a （g, f）-factorization which is r-orthogonal to a given subgraph H with kr edges.展开更多
In this paper it is shown that every connected claw-free graph G contains connected [a, max{a + 2, b}]-factors if it has [a, b]-factors, where a, b are integers and b ≥ a ≥ 1.
Let G be a graph with vertex set V(G) and edge set E(G) and let g and f betwo integer-valued functions defined on V(G) such that 2k - 2 ≤ g(x) ≤ f(x) for all x ∈ V(G).Let H be a subgraph of G with mk edges. In this...Let G be a graph with vertex set V(G) and edge set E(G) and let g and f betwo integer-valued functions defined on V(G) such that 2k - 2 ≤ g(x) ≤ f(x) for all x ∈ V(G).Let H be a subgraph of G with mk edges. In this paper, it is proved that every (mg + m - 1, mf - m +l)-graph G has (g, f)-factorizations randomly k-orthogonal to H under some special conditions.展开更多
Let G be a graph with vertex set V(G) and edge set E(G) and let g and f be two integer-valued functions defined on V(G) such that 2k-1≤g(x) ≤ f(x) for all x ∈ V(G). Let H be a subgraph of G with mk edges . In this ...Let G be a graph with vertex set V(G) and edge set E(G) and let g and f be two integer-valued functions defined on V(G) such that 2k-1≤g(x) ≤ f(x) for all x ∈ V(G). Let H be a subgraph of G with mk edges . In this paper it is proved that every (mg + m - 1,mf- m + 1)-graph G has (g, f)-factorizations randomly κ-orthogonal to H and shown that the result is best possible.展开更多
基金This work was supported by NNSF. RFDP and NNSF of shandong province(Z2000A02 ).
文摘Let G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two positive integer-valued functions defined on V(G) such that g(x) ≤ f(x) for every vertex x of V(G). Then a (g, f)-factor of G is a spanning subgraph H of G such that g(x) ≤ dH(x) 5 f(x) for each x ∈ V(H). A (g, f)-factorization of G is a partition of E(G) into edge-disjoint (g, f)-factors. Let F = {F1, F2,…… ， Fm } and H be a factorization and a subgraph of G, respectively. If F, 1 ≤ i ≤ m， has exactly one edge in common with H, then it is said that ■ is orthogonal to H. It is proved that every bipartite (mg + m - 1, mf - m + 1 )-graph G has a (g, f)-factorization orthogonal to k vertex disjoint m-subgraphs of G if 2-k ≤ g(x) for all x ∈ V(G). Furthermore, it is showed that the results in this paper are best possible.
基金This research is supported by the National Natural Science Foundation of China (19831080) and RSDP of China
文摘Let G be a graph with vertex set V（G） and edge set E（G）, and let g and f be two integer- valued functions defined on V（G） such that g（x）≤f（x） for all x ∈ V（G）. Then a （g, f）-factor of G is a spanning subgraph H of G such that g（x）≤d<sub>H</sub>（x）≤f（x） for all x ∈ V（G）. A （g, f）-factorization of G is a partition of E（G） into edge-disjoint （g,f）-factors. Let F={F<sub>1</sub>, F<sub>2</sub>...., F<sub>m</sub>} be a factorization of G, and H be a subgraph of G with mr edges. If F<sub>i</sub>. 1≤i≤m, has exactly r edges in common with H. then F is said to be r-orthogonal to H. In this paper it is proved that every （mg+kr, mf-kr）-graph. where m, k and r are positive integers with k【m and g≥r, contains a subgraph R such that R has a （g, f）-factorization which is r-orthogonal to a given subgraph H with kr edges.
基金the National Natural Science Foundation of China.
文摘In this paper it is shown that every connected claw-free graph G contains connected [a, max{a + 2, b}]-factors if it has [a, b]-factors, where a, b are integers and b ≥ a ≥ 1.
基金The work is partially supported by NNSF of China(10471078)RSDP of China
文摘Let G be a graph with vertex set V(G) and edge set E(G) and let g and f betwo integer-valued functions defined on V(G) such that 2k - 2 ≤ g(x) ≤ f(x) for all x ∈ V(G).Let H be a subgraph of G with mk edges. In this paper, it is proved that every (mg + m - 1, mf - m +l)-graph G has (g, f)-factorizations randomly k-orthogonal to H under some special conditions.
基金the National Natural Science Foundation of China (No.60172003,19831080) by NSF of Shandong Province.
文摘Let G be a graph with vertex set V(G) and edge set E(G) and let g and f be two integer-valued functions defined on V(G) such that 2k-1≤g(x) ≤ f(x) for all x ∈ V(G). Let H be a subgraph of G with mk edges . In this paper it is proved that every (mg + m - 1,mf- m + 1)-graph G has (g, f)-factorizations randomly κ-orthogonal to H and shown that the result is best possible.
