Simple graphs are considered. Let G be a graph andg(x) andf(x) integer-valued functions defined on V(G) withg(x)?f(x) for everyx?V(G). For a subgraphH ofG and a factorizationF=|F 1,F 2,?,F 1| ofG, if |E(H)∩E(F 1)|=1,...Simple graphs are considered. Let G be a graph andg(x) andf(x) integer-valued functions defined on V(G) withg(x)?f(x) for everyx?V(G). For a subgraphH ofG and a factorizationF=|F 1,F 2,?,F 1| ofG, if |E(H)∩E(F 1)|=1,1?i?j, then we say thatF orthogonal toH. It is proved that for an (mg(x)+k,mf(x) -k)-graphG, there exists a subgraphR ofG such that for any subgraphH ofG with |E(H)|=k,R has a (g,f)-factorization orthogonal toH, where 1?k<m andg(x)?1 orf(x)?5 for everyx?V(G).展开更多
Let G be a graph, and F={F1, F2,…,Fm} and H be a factorization and a subgraph of G, respectively. If H has exactly one edge in common with Fi for all i, 1≤i≤m, then we say that F is orthogonal to H. Let g and f be ...Let G be a graph, and F={F1, F2,…,Fm} and H be a factorization and a subgraph of G, respectively. If H has exactly one edge in common with Fi for all i, 1≤i≤m, then we say that F is orthogonal to H. Let g and f be two integer-valued functions defined on V(G) such that 0≤g(x)≤f(x) for every x∈V(G). In this paper, it is proved that for any given star with m edges of an (mg+m-1, mf-m + 1)-graph G, there exists a (g,f)-factorization of G orthogonal to it.展开更多
In this paper, it is shown that a sufficient condition for the existence of a K 1,p k factorization of K m,n , whenever p is a prime number and k is a positive integer, is (1) m≤p kn,(2...In this paper, it is shown that a sufficient condition for the existence of a K 1,p k factorization of K m,n , whenever p is a prime number and k is a positive integer, is (1) m≤p kn,(2) n≤p km,(3)p kn-m≡p km-n ≡0(mod( p 2k -1 )) and (4) (p kn-m)(p km-n) ≡0(mod( p k -1)p k×(p 2k -1)(m+n)) .展开更多
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.展开更多
Let G be a graph and f an integer-valued function defined on V(G). It is proved that every (0,mf - m+1)-graph G has a (0,f)-factorization orthogonal to any given subgraph with m edges.
Let G be a graph, k(1), ... , k(m) be positive integers. If the edges of graph G can be decomposed into some edge disjoint [0, k(1)]-factor F-1, ..., [0, k(m)]-factor F-m, then we can say (F) over bar = {F-1, ..., F-m...Let G be a graph, k(1), ... , k(m) be positive integers. If the edges of graph G can be decomposed into some edge disjoint [0, k(1)]-factor F-1, ..., [0, k(m)]-factor F-m, then we can say (F) over bar = {F-1, ..., F-m}, is a [0, k(i)](1)(m) -factorization of G. If H is a subgraph with m edges in graph G and / E (H) boolean AND E(F-i) / = 1 for all 1 less than or equal to i less than or equal to m, then we can call that (F) over bar is orthogonal to H. It is proved that if G is a [0, k(1) + ... + k(m) - m + 1]-graph, H is a subgraph with m edges in G, then graph G has a [0, k(i)](1)(m)-factorization orthogonal to H.展开更多
Let G be a graph and g, f be two nonnegative integer-valued functions defined on the vertices set V(G) of G and g less than or equal to f. A (g, f)-factor of a graph G is a spanning subgraph F of G such that g(x)less ...Let G be a graph and g, f be two nonnegative integer-valued functions defined on the vertices set V(G) of G and g less than or equal to f. A (g, f)-factor of a graph G is a spanning subgraph F of G such that g(x)less than or equal to d(F)(x)less than or equal to f(x) for all x is an element of V(G). If G itself is a (g, f)-factor, then it is said that G is a (g, f)-graph. If the edges of G can be decomposed into some edge disjoint (g, f)-factors, then it is called that G is (g, f)-factorable. In this paper, one sufficient condition for a graph to be (g, f)-factorable is given.展开更多
LetλKm,n be a bipartite multigraph with two partite sets having m and n vertices, respectively. A Pν-factorization ofλKm,n is a set of edge-disjoint Pν-factors ofλKm,n which partition the set of edges ofλKm,n. W...LetλKm,n be a bipartite multigraph with two partite sets having m and n vertices, respectively. A Pν-factorization ofλKm,n is a set of edge-disjoint Pν-factors ofλKm,n which partition the set of edges ofλKm,n. Whenνis an even number, Ushio, Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a Pν-factorization ofλKm,n. When v is an odd number, we proposed a conjecture. However, up to now we only know that the conjecture is true forν= 3. In this paper we will show that the conjecture is true whenν= 4k-1. That is, we shall prove that a necessary and sufficient condition for the existence of a P4k-1-factorization ofλKm,n is (1) (2k-1)m≤2kn, (2) (2k-1)n≤2km, (3)m + n = 0 (mod 4k-1), (4)λ(4k-1)mn/[2(2k-1)(m + n)] is an integer.展开更多
文摘Simple graphs are considered. Let G be a graph andg(x) andf(x) integer-valued functions defined on V(G) withg(x)?f(x) for everyx?V(G). For a subgraphH ofG and a factorizationF=|F 1,F 2,?,F 1| ofG, if |E(H)∩E(F 1)|=1,1?i?j, then we say thatF orthogonal toH. It is proved that for an (mg(x)+k,mf(x) -k)-graphG, there exists a subgraphR ofG such that for any subgraphH ofG with |E(H)|=k,R has a (g,f)-factorization orthogonal toH, where 1?k<m andg(x)?1 orf(x)?5 for everyx?V(G).
基金the Mathematics Tianyuan Foundation and Doctoral Discipline Foundation
文摘Let G be a graph, and F={F1, F2,…,Fm} and H be a factorization and a subgraph of G, respectively. If H has exactly one edge in common with Fi for all i, 1≤i≤m, then we say that F is orthogonal to H. Let g and f be two integer-valued functions defined on V(G) such that 0≤g(x)≤f(x) for every x∈V(G). In this paper, it is proved that for any given star with m edges of an (mg+m-1, mf-m + 1)-graph G, there exists a (g,f)-factorization of G orthogonal to it.
文摘In this paper, it is shown that a sufficient condition for the existence of a K 1,p k factorization of K m,n , whenever p is a prime number and k is a positive integer, is (1) m≤p kn,(2) n≤p km,(3)p kn-m≡p km-n ≡0(mod( p 2k -1 )) and (4) (p kn-m)(p km-n) ≡0(mod( p k -1)p k×(p 2k -1)(m+n)) .
基金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.
文摘Let G be a graph and f an integer-valued function defined on V(G). It is proved that every (0,mf - m+1)-graph G has a (0,f)-factorization orthogonal to any given subgraph with m edges.
文摘Let G be a graph, k(1), ... , k(m) be positive integers. If the edges of graph G can be decomposed into some edge disjoint [0, k(1)]-factor F-1, ..., [0, k(m)]-factor F-m, then we can say (F) over bar = {F-1, ..., F-m}, is a [0, k(i)](1)(m) -factorization of G. If H is a subgraph with m edges in graph G and / E (H) boolean AND E(F-i) / = 1 for all 1 less than or equal to i less than or equal to m, then we can call that (F) over bar is orthogonal to H. It is proved that if G is a [0, k(1) + ... + k(m) - m + 1]-graph, H is a subgraph with m edges in G, then graph G has a [0, k(i)](1)(m)-factorization orthogonal to H.
文摘Let G be a graph and g, f be two nonnegative integer-valued functions defined on the vertices set V(G) of G and g less than or equal to f. A (g, f)-factor of a graph G is a spanning subgraph F of G such that g(x)less than or equal to d(F)(x)less than or equal to f(x) for all x is an element of V(G). If G itself is a (g, f)-factor, then it is said that G is a (g, f)-graph. If the edges of G can be decomposed into some edge disjoint (g, f)-factors, then it is called that G is (g, f)-factorable. In this paper, one sufficient condition for a graph to be (g, f)-factorable is given.
基金This work was supported by the National Natural Science Foundation of China (Grant No. 10571133).
文摘LetλKm,n be a bipartite multigraph with two partite sets having m and n vertices, respectively. A Pν-factorization ofλKm,n is a set of edge-disjoint Pν-factors ofλKm,n which partition the set of edges ofλKm,n. Whenνis an even number, Ushio, Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a Pν-factorization ofλKm,n. When v is an odd number, we proposed a conjecture. However, up to now we only know that the conjecture is true forν= 3. In this paper we will show that the conjecture is true whenν= 4k-1. That is, we shall prove that a necessary and sufficient condition for the existence of a P4k-1-factorization ofλKm,n is (1) (2k-1)m≤2kn, (2) (2k-1)n≤2km, (3)m + n = 0 (mod 4k-1), (4)λ(4k-1)mn/[2(2k-1)(m + n)] is an integer.
