共查询到20条相似文献,搜索用时 93 毫秒
1.
Guizhen LIU 《Frontiers of Mathematics in China》2009,4(2):311-323
Let G be a digraph with vertex set V(G) and arc set E(G) and let g = (g
−, g
+) and ƒ = (ƒ
−, ƒ
+) be pairs of positive integer-valued functions defined on V(G) such that g
−(x) ⩽ ƒ
−(x) and g
+(x) ⩽ ƒ
+(x) for each x ∈ V(G). A (g, ƒ)-factor of G is a spanning subdigraph H of G such that g
−(x) ⩽ id
H
(x) ⩽ ƒ
−(x) and g
+(x) ⩽ od
H
(x) ⩽ ƒ
+(x) for each x ∈ V(H); a (g, ƒ)-factorization of G is a partition of E(G) into arc-disjoint (g, ƒ)-factors. Let
= {F
1, F
2,…, F
m} and H be a factorization and a subdigraph of G, respectively.
is called k-orthogonal to H if each F
i
, 1 ⩽ i ⩽ m, has exactly k arcs in common with H. In this paper it is proved that every (mg+m−1,mƒ−m+1)-digraph has a (g, f)-factorization k-orthogonal to any given subdigraph with km arcs if k ⩽ min{g
−(x), g
+(x)} for any x ∈ V(G) and that every (mg, mf)-digraph has a (g, f)-factorization orthogonal to any given directed m-star if 0 ⩽ g(x) ⩽ f(x) for any x ∈ V(G). The results in this paper are in some sense best possible.
相似文献
2.
LetG be a graph with vertex setV (G) and edge setE (G), and letg andf be two integer-valued functions defined on V(G) such thatg(x)⩽(x) for every vertexx ofV(G). It was conjectured that ifG is an (mg +m - 1,mf -m+1)-graph andH a subgraph ofG withm edges, thenG has a (g,f)-factorization orthogonal toH. This conjecture is proved affirmatively.
Project supported by the National Natural Science Foundation of China. 相似文献
3.
Let G be a graph with vertex set V(G) and edge set E(G) and let g and f be two integer-valuated 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
H
(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
1, F
2, ..., F
m
} be a factorization of G and H be a subgraph of G with mr edges. If F
i
, 1 ≤i≤m, has exactly r edges in common with H, then
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.
This research is supported by the National Natural Science Foundation of China (19831080) and RSDP of China 相似文献
4.
A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that a′(G) ⩽ Δ(G) + 2 for any graphs. For planar graphs G with girth g(G), we prove that a′(G) ⩽ max{2Δ(G) − 2, Δ(G) + 22} if g(G) ⩾ 3, a′(G) ⩽ Δ(G) + 2 if g(G) ⩾ 5, a′(G) ⩽ Δ(G) + 1 if g(G) ⩾ 7, and a′(G) = Δ(G) if g(G) ⩾ 16 and Δ(G) ⩾ 3. For series-parallel graphs G, we have a′(G) ⩽ Δ(G) + 1.
This work was supported by National Natural Science Foundation of China (Grant No. 10871119) and Natural Science Foundation
of Shandong Province (Grant No. Y2008A20). 相似文献
5.
Let G be a graph and W a subset of V(G). Let g,f:V(G)→Z be two integer-valued functions such that g(x)≤f(x) for all x∈V(G) and g(y)≡f(y) (mod 2) for all y∈W. Then a spanning subgraph F of G is called a partial parity (g,f)-factor with respect to W if g(x)≤deg
F
(x)≤f(x) for all x∈V(G) and deg
F
(y)≡f(y) (mod 2) for all y∈W. We obtain a criterion for a graph G to have a partial parity (g,f)-factor with respect to W. Furthermore, by making use of this criterion, we give some necessary and sufficient conditions for a graph G to have a subgraph which covers W and has a certain given property.
Received: June 14, 1999?Final version received: August 21, 2000 相似文献
6.
For any vertex u∈V(G), let T_N(U)={u}∪{uv|uv∈E(G), v∈v(G)}∪{v∈v(G)|uv∈E(G)}and let f be a total k-coloring of G. The total-color neighbor of a vertex u of G is the color set C_f(u)={f(x)|x∈TN(U)}. For any two adjacent vertices x and y of V(G)such that C_f(x)≠C_f(y), we refer to f as a k-avsdt-coloring of G("avsdt"is the abbreviation of"adjacent-vertex-strongly- distinguishing total"). The avsdt-coloring number of G, denoted by X_(ast)(G), is the minimal number of colors required for a avsdt-coloring of G. In this paper, the avsdt-coloring numbers on some familiar graphs are studied, such as paths, cycles, complete graphs, complete bipartite graphs and so on. We proveΔ(G) 1≤X_(ast)(G)≤Δ(G) 2 for any tree or unique cycle graph G. 相似文献
7.
HaoZHAO GuiZhenLIU XiaoXiaYAN 《数学学报(英文版)》2005,21(2):413-422
Let G be a graph with vertex set V(G) and edge set E(G) and let g and f be two integervalued 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 1)-graph G has (g, f)-factorizations randomly k-orthogonal to H under some special conditions. 相似文献
8.
In this paper, we obtain the following result: Let k, n
1 and n
2 be three positive integers, and let G = (V
1,V
2;E) be a bipartite graph with |V1| = n
1 and |V
2| = n
2 such that n
1 ⩾ 2k + 1, n
2 ⩾ 2k + 1 and |n
1 − n
2| ⩽ 1. If d(x) + d(y) ⩾ 2k + 2 for every x ∈ V
1 and y ∈ V
2 with xy
$
\notin
$
\notin
E(G), then G contains k independent cycles. This result is a response to Enomoto’s problems on independent cycles in a bipartite graph. 相似文献
9.
Pravin M. Vaidya 《Discrete and Computational Geometry》1991,6(1):369-381
A setV ofn points ink-dimensional space induces a complete weighted undirected graph as follows. The points are the vertices of this graph and
the weight of an edge between any two points is the distance between the points under someL
p metric. Let ε≤1 be an error parameter and letk be fixed. We show how to extract inO(n logn+ε
−k
log(1/ε)n) time a sparse subgraphG=(V, E) of the complete graph onV such that: (a) for any two pointsx, y inV, the length of the shortest path inG betweenx andy is at most (1+∈) times the distance betweenx andy, and (b)|E|=O(ε−k
n). 相似文献
10.
A. Yu. Volovikov 《Journal of Mathematical Sciences》2009,159(6):790-793
Let G be a finite group and X be a G-space. For a map f: X → ℝ
m
, the partial coincidence set A(f, k), k ≤ |G|, is the set of points x ∈ X such that there exist k elements g
1,…, g
k
of the group G, for which f(g
1
x) = ⋅⋅⋅ = f(g
k
x) holds. We prove that the partial coincidence set is nonempty for G = ℤ
p
n
under some additional assumptions.
Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 13, No. 8, pp. 61–67, 2007. 相似文献
11.
On Group Chromatic Number of Graphs 总被引:2,自引:0,他引:2
Let G be a graph and A an Abelian group. Denote by F(G, A) the set of all functions from E(G) to A. Denote by D an orientation of E(G). For f ∈ F(G,A), an (A,f)-coloring of G under the orientation D is a function c : V(G)↦A such that for every directed edge uv from u to v, c(u)−c(v) ≠ f(uv). G is A-colorable under the orientation D if for any function f ∈ F(G, A), G has an (A, f)-coloring. It is known that A-colorability is independent of the choice of the orientation. The group chromatic number of a graph G is defined to be the least positive integer m for which G is A-colorable for any Abelian group A of order ≥m, and is denoted by χg(G). In this note we will prove the following results. (1) Let H1 and H2 be two subgraphs of G such that V(H1)∩V(H2)=∅ and V(H1)∪V(H2)=V(G). Then χg(G)≤min{max{χg(H1), maxv∈V(H2)deg(v,G)+1},max{χg(H2), maxu∈V(H1) deg (u, G) + 1}}. We also show that this bound is best possible. (2) If G is a simple graph without a K3,3-minor, then χg(G)≤5. 相似文献
12.
LetG be a graph and letf be a function defined on V(G) such that f(x) is a positive odd integer for everyx ? V(G). A spanning subgraphF ofG is called a [l,f]-odd factor of G if dF(x) ? {1,3,2026, f(x)} for every x ?V(G), whered F (x) denotes the degree of x inF. We discuss several conditions for a graphG to have a [1,f]-odd factor. 相似文献
13.
Wei Cao 《Czechoslovak Mathematical Journal》2007,57(1):253-268
A set S={x
1,...,x
n
} of n distinct positive integers is said to be gcd-closed if (x
i
, x
j
) ∈ S for all 1 ⩽ i, j ⩽ n. Shaofang Hong conjectured in 2002 that for a given positive integer t there is a positive integer k(t) depending only on t, such that if n ⩽ k(t), then the power LCM matrix ([x
i
, x
j
]
t
) defined on any gcd-closed set S={x
1,...,x
n
} is nonsingular, but for n ⩾ k(t) + 1, there exists a gcd-closed set S={x
1,...,x
n
} such that the power LCM matrix ([x
i
, x
j
]
t
) on S is singular. In 1996, Hong proved k(1) = 7 and noted k(t) ⩾ 7 for all t ⩾ 2. This paper develops Hong’s method and provides a new idea to calculate the determinant of the LCM matrix on a gcd-closed
set and proves that k(t) ⩾ 8 for all t ⩾ 2. We further prove that k(t) ⩾ 9 iff a special Diophantine equation, which we call the LCM equation, has no t-th power solution and conjecture that k(t) = 8 for all t ⩾ 2, namely, the LCM equation has t-th power solution for all t ⩾ 2. 相似文献
14.
Gordan Savin 《Israel Journal of Mathematics》1992,80(1-2):195-205
LetG andH ⊂G be two real semisimple groups defined overQ. Assume thatH is the group of points fixed by an involution ofG. Letπ ⊂L
2(H\G) be an irreducible representation ofG and letf επ be aK-finite function. Let Γ be an arithmetic subgroup ofG. The Poincaré seriesP
f(g)=ΣH∩ΓΓ
f(γ{}itg) is an automorphic form on Γ\G. We show thatP
f is cuspidal in some cases, whenH ∩Γ\H is compact.
Partially supported by NSF Grant # DMS 9103608. 相似文献
15.
Harald Niederreiter 《Monatshefte für Mathematik》1987,103(4):269-288
For a rational functionf/g=f(x)/g(x) over a fieldF with ged (f,g)=1 and deg (g)1 letK(f/g) be the maximum degree of the partial quotients in the continued fraction expansion off/. ForfF[x] with deg (f)=k1 andf(O)O putL(f)=K(f(x)/x
k
). It is shown by an explicit construction that for every integerb with 1bk there exists anf withL(f)=b. IfF=F
2, the binary field, then for everyk there is exactly onefF
2[x] with deg (f)=k,f(O)O, andL(f)=1. IfF
q
is the finite field withq elements andgF
q
[x] is monic of degreek1, then there exists a monic irreduciblefF
q
[x] with deg (f)=k, gcd (f,g)=1, andK(f/g)<2+2 (logk)/logq, where the caseq=k=2 andg(x)=x
2+x+1 is excluded. An analogous existence theorem is also shown for primitive polynomials over finite fields. These results have applications to pseudorandom number generation. 相似文献
16.
Y. Lacroix 《Israel Journal of Mathematics》2002,132(1):253-263
LetG denote the set of decreasingG: ℝ→ℝ withGэ1 on ]−∞,0], and ƒ
0
∞
G(t)dt⩽1. LetX be a compact metric space, andT: X→X a continuous map. Let μ denone aT-invariant ergodic probability measure onX, and assume (X, T, μ) to be aperiodic. LetU⊂X be such that μ(U)>0. Let τ
U
(x)=inf{k⩾1:T
k
xεU}, and defineG
U
(t)=1/u(U)u({xεU:u(U)τU(x)>t),tεℝ We prove that for μ-a.e.x∈X, there exists a sequence (U
n
)
n≥1
of neighbourhoods ofx such that {x}=∩
n
U
n
, and for anyG ∈G, there exists a subsequence (n
k
)
k≥1
withG
U
n
k
↑U weakly.
We also construct a uniquely ergodic Toeplitz flowO(x
∞,S, μ), the orbit closure of a Toeplitz sequencex
∞, such that the above conclusion still holds, with moreover the requirement that eachU
n
be a cylinder set.
In memory of Anzelm Iwanik 相似文献
17.
Aregression is a functiong from a partially ordered set to itself such thatg(x)≦x for allz. Amonotone k-chain is a chain ofk elementsx
1<x
2 <...<x
k
such thatg(x
1)≦g(x
2)≦...≦g(x
k
). If a partial order has sufficiently many elements compared to the size of its largest antichain, every regression on it
will have a monotone (k + 1)-chain. Fixingw, letf(w, k) be the smallest number such that every regression on every partial order with size leastf(w, k) but no antichain larger thanw has a monotone (k + 1)-chain. We show thatf(w, k)=(w+1)
k
.
Dedicated to Paul Erdős on his seventieth birthday
Research supported in part by the National Science Foundation under ISP-80-11451. 相似文献
18.
Guiying Yan 《Graphs and Combinatorics》1999,15(3):365-371
Let G be a simple graph. Let g(x) and f(x) be integer-valued functions defined on V(G) with g(x)≥2 and f(x)≥5 for all x∈V(G). It is proved that if G is an (mg+m−1, mf−m+1)-graph and H is a subgraph of G with m edges, then there exists a (g,f)-factorization of G orthogonal to H.
Received: January 19, 1996 Revised: November 11, 1996 相似文献
19.
Jipu Ma 《Frontiers of Mathematics in China》2008,3(2):305-316
Let E and F be Banach spaces, f: U ⊂ E → F be a map of C
r
(r ⩾ 1), x
0 ∈ U, and ft (x
0) denote the FréLechet differential of f at x
0. Suppose that f′(x
0) is double split, Rank(f′(x
0)) = ∞, dimN(f′(x
0)) > 0 and codimR(f′(x
0)) s> 0. The rank theorem in advanced calculus asks to answer what properties of f ensure that f(x) is conjugate to f′(x
0) near x
0. We have proved that the conclusion of the theorem is equivalent to one kind of singularities for bounded linear operators,
i.e., x
0 is a locally fine point for f′(x) or generalized regular point of f(x); so, a complete rank theorem in advanced calculus is established, i.e., a sufficient and necessary condition such that the
conclusion of the theorem to be held is given.
相似文献
20.
Let G be a multigraph, g and f be integer-valued functions defined on V(G). Then a graph G is called a (g, f)-graph if g(x)≤deg
G(x)≤f(x) for each x∈V(G), and a (g, f)-factor is a spanning (g, f)-subgraph. If the edges of graph G can be decomposed into (g, f)-factors, then we say that G is (g, f)-factorable. In this paper, we obtained some sufficient conditions for a graph to be (g, f)-factorable. One of them is the following: Let m be a positive integer, l be an integer with l=m (mod 4) and 0≤l≤3. If G is an -graph, then G is (g, f)-factorable. Our results imply several previous (g, f)-factorization results.
Revised: June 11, 1998 相似文献