共查询到20条相似文献,搜索用时 31 毫秒
1.
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 相似文献
2.
Let G = (V, E) be a simple graph. A subset S ⊆ V is a dominating set of G, if for any vertex u ∈ V-S, there exists a vertex v ∈ S such that uv ∈ E. The domination number, denoted by γ(G), is the minimum cardinality of a dominating set. In this paper we will prove that if G is a 5-regular graph, then γ(G) ⩽ 5/14n. 相似文献
3.
Baruch Solel 《Israel Journal of Mathematics》1988,62(1):63-89
LetM be a σ-finite von Neumann algebra andα be an action ofR onM. LetH
∞(α) be the associated analytic subalgebra; i.e.H
∞(α)={X ∈M: sp∞(X) [0, ∞]}. We prove that every σ-weakly closed subalgebra ofM that containsH
∞(α) isH
∞(γ) for some actionγ ofR onM. Also we show that (assumingZ(M)∩M
α = Ci)H
∞(α) is a maximal σ-weakly closed subalgebra ofM if and only if eitherH
∞(α)={A ∈M: (I−F)xF=0} for some projectionF ∈M, or sp(α)=Γ(α). 相似文献
4.
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. 相似文献
5.
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.
相似文献
6.
Bounds on the Distance Two-Domination Number of a Graph 总被引:1,自引:0,他引:1
For a graph G = (V, E), a subset D⊆V(G) is said to be distance two-dominating set in G if for each vertex u∈V−D, there exists a vertex v∈D such that d(u,v)≤2. The minimum cardinality of a distance two-dominating set in G is called a distance two-domination number and is denoted by γ2(G). In this note we obtain various upper bounds for γ2(G) and characterize the classes of graphs attaining these bounds.
Received: May 31, 1999 Final version received: July 13, 2000 相似文献
7.
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 相似文献
8.
A. H. Lachlan 《Israel Journal of Mathematics》1984,49(1-3):69-153
LetL be a finite relational language andH(L) denote the class of all countable structures which are stable and homogeneous forL in the sense of Fraissé. By convention countable includes finite and any finite structure is stable. A rank functionr :H(L) →ω is introduced and also a notion of dimension for structures inH(L). A canonical way of shrinking structures is defined which reduces their dimensions. The main result of the paper is that
anyM ∈H(L) can be shrunk toM′ ∈H(L),M′ ⊆M, such that |M′| is bounded in terms ofr(M), and the isomorphism type ofM overM′ is uniquely determined by the dimensions ofM. Forr<ω we deduce thatH(L, r), the class of allM ∈H(L) withr(M)≦r, is the union of a finite number of classes within each of which the isomorphism type of a structure is completely determined
by its dimensions.
Dedicated to the memory of Abraham Robinson on the tenth anniversary of his death 相似文献
9.
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. 相似文献
10.
Li WANG 《Frontiers of Mathematics in China》2012,7(1):125-144
Let Ω be a finite set, and let G be a permutation group on Ω. A subset H of G is called intersecting if for any σ, π ∈ H, they agree on at least one point. We show that a maximal intersecting subset of an irreducible imprimitive reflection group
G(m, p, n) is a coset of the stabilizer of a point in {1, …, n} provided n is sufficiently large. 相似文献
11.
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 相似文献
12.
Michel Weber 《Analysis Mathematica》2005,31(4):291-300
Summary We study the class of convergence E∪L1of a family of moving averages which does not satisfy the cone condition. We show that if E0is a finite subset of Ewhich is (E)-stable for the multiplication operation: f,g∈E0 →f·g∈E, then the supremum sup { f, f∈E0} is dominated by sup{ g, g∈G0}where G0is a Gaussian family with same covariance function. This is used to derive a maximal inequality for families Fsuch that each finite subset is E-stable and Fis a GB set. 相似文献
13.
Daniel T. Wise 《Inventiones Mathematicae》2002,149(3):579-617
A subgroup M⊂G is almost malnormal provided that for each g∈G−M, the intersection M
g
∩M is finite. It is proven that the free product of two virtually free groups amalgamating a finitely generated almost malnormal
subgroup, is residually finite. A consequence of a generalization of this result is that an acute-angled n-gon of finite groups is residually finite if n≥4. Another consequence is that if G acts properly discontinuously and cocompactly on a 2-dimensional hyperbolic building whose chambers have acute angles and
at least 4 sides, then G is residually finite.
Oblatum 17-VII-2000 & 13-II-2002?Published online: 29 April 2002 相似文献
14.
V. B. Lender 《Semigroup Forum》1993,47(1):373-380
If a semigroup varietyV contains the variety of commutative three-nilpotent semigroups, or if it is a variety of bands containing all semilattices,
then, for anyA∈V and any left cancellative monoidM, there is a semigroupS∈V such thatA is a retract ofS andM is isomorphic to the monoid of all injective endomorphisms ofS. 相似文献
15.
A three-valued function f: V → {−1, 0, 1} defined on the vertices of a graph G= (V, E) is a minus total dominating function (MTDF) if the sum of its function values over any open neighborhood is at least one.
That is, for every υ ∈ V, f(N(υ)) ⩾ 1, where N(υ) consists of every vertex adjacent to υ. The weight of an MTDF is f(V) = Σf(υ), over all vertices υ ∈ V. The minus total domination number of a graph G, denoted γ
t
−(G), equals the minimum weight of an MTDF of G. In this paper, we discuss some properties of minus total domination on a graph G and obtain a few lower bounds for γ
t
−(G). 相似文献
16.
A. N. Starkov 《Mathematical Notes》1999,66(2):233-239
Consider a connected Lie groupG, a lattice Γ inG, a connected subgroupH ofG, and the adjoint representation Ad ofG on its Lie algebra g. Suppose that Ad(H) splits into a semidirect product of a reductive subgroup and the unipotent radical. We prove that the minimality of the
leftH-action onG/Γ then implies its unique ergodicity. Simultaneously, we suggest a reduction of the study of finite ergodic measures for
an arbitrary action (G/Γ,H), where the subgroupH∈G is connected and Γ∈G is discrete, to the case of an Abelian subgroupH.
Translated fromMatematicheskie Zametki, Vol. 66, No. 2, pp. 293–301, August, 1999. 相似文献
17.
A subgroupX of the locally finite groupG is said to beconfined, if there exists a finite subgroupF≤G such thatX
g∩F≠1 for allg∈G. Since there seems to be a certain correspondence between proper confined subgroups inG and non-trivial ideals in the complex group algebra ℂG, we determine the confined subgroups of periodic simple finitary linear groups in this paper.
Dedicated to the memory of our friend and collaborator Richard E. Phillips 相似文献
18.
Nathan S. Feldman 《Integral Equations and Operator Theory》2007,58(2):153-173
A pair of commuting operators, (A,B), on a Hilbert space
is said to be hypercyclic if there exists a vector
such that {A
n
B
k
x : n, k ≥ 0} is dense in
. If f, g ∈H
∞(G) where G is an open set with finitely many components in the complex plane, then we show that the pair (M
*
f
, M
*
g
) of adjoints of multiplcation operators on a Hilbert space of analytic functions on G is hypercyclic if and only if the semigroup they generate contains a hypercyclic operator. However, if G has infinitely many components, then we show that there exists f, g ∈H
∞(G) such that the pair (M
*
f
, M
*
g
) is hypercyclic but the semigroup they generate does not contain a hypercyclic operator. We also consider hypercyclic n-tuples. 相似文献
19.
Shi Rong Li 《数学学报(英文版)》2008,24(4):647-654
Let F be a saturated formation containing the class of supersolvable groups and let G be a finite group. The following theorems are shown: (1) G ∈ F if and only if there is a normal subgroup H such that G/H ∈ F and every maximal subgroup of all Sylow subgroups of H is either c-normal or s-quasinormally embedded in G; (2) G ∈F if and only if there is a soluble normal subgroup H such that G/H∈F and every maximal subgroup of all Sylow subgroups of F(H), the Fitting subgroup of H, is either e-normally or s-quasinormally embedded in G. 相似文献
20.
Raffaele Mosca 《Graphs and Combinatorics》2001,17(3):517-528
Let G be a graph with n vertices, and denote as γ(G) (as θ(G)) the cardinality of a minimum edge cover (of a minimum clique cover) of G. Let E (let C) be the edge-vertex (the clique-vertex) incidence matrix of G; write then P(E)={x∈ℜ
n
:Ex≤1,x≥0}, P(C)={x∈ℜ
n
:Cx≤1,x≥0}, α
E
(G)=max{1
T
x subject to x∈P(E)}, and α
C
(G)= max{1
T
x subject to x∈P(C)}. In this paper we prove that if α
E
(G)=α
C
(G), then γ(G)=θ(G).
Received: May 20, 1998?Final version received: April 12, 1999 相似文献