共查询到20条相似文献,搜索用时 31 毫秒
1.
George T. Diderrich 《Israel Journal of Mathematics》1973,14(1):14-22
LetG be an Abelian group written additively,B a finite subset ofG, and lett be a positive integer. Fort≦|B|, letB
t denote the set of sums oft distinct elements overB. Furthermore, letK be a subgroup ofG and let σ denote the canonical homomorphism σ:G→G/K. WriteB
t (modB
t) forB
tσ and writeB
t (modK) forBσ. The following addition theorem in groups is proved. LetG be an Abelian group with no 2-torsion and letB a be finite subset ofG. Ift is a positive integer such thatt<|B| then |B
t (modK)|≧|B (modK)| for any finite subgroupK ofG. 相似文献
2.
Haruhide Matsuda 《Graphs and Combinatorics》2002,18(4):763-768
Let a, b, m, and t be integers such that 1≤a<b and 1≤t≤⌉(b−m+1)/a⌉. Suppose that G is a graph of order |G| and H is any subgraph of G with the size |E(H)|=m. Then we prove that G has an [a,b]-factor containing all the edges of H if the minimum degree is at least a, |G|>((a+b)(t(a+b−1)−1)+2m)/b, and |N
G
(x
1)∪⋯ ∪N
G
(x
t
)|≥(a|G|+2m)/(a+b) for every independent set {x
1,…,x
t
}⊆V(G). This result is best possible in some sense and it is an extension of the result of H. Matsuda (A neighborhood condition
for graphs to have [a,b]-factors, Discrete Mathematics 224 (2000) 289–292).
Received: October, 2001 Final version received: September 17, 2002
RID="*"
ID="*" This research was partially supported by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Encouragement
of Young Scientists, 13740084, 2001 相似文献
3.
Let G = (V, E) be a graph without isolated vertices. A set S lohtain in V is a domination set of G if every vertex in V - S is adjacent to a vertex in S, that is N[S] = V. The domination number of G, denoted by γ(G), is the minimum cardinality of a domination set of G. A set S lohtain in V is a paired-domination set of G if S is a domination set of G and the induced subgraph G[S] has a perfect matching. The paired-domination number, denoted by γpr(G), is defined to be the minimum cardinality of a paired-domination set S in G. A subset S lohtain in V is a power domination set of G if all vertices of V can be observed recursively by the following rules: (i) all vertices in N[S] are observed initially, and (ii) if an observed vertex u has all neighbors observed except one neighbor v, then v is observed (by u). The power domination number, denoted by γp(G), is the minimum cardinality of a power domination set of G. In this paper, the constructive characterizations for trees with γp=γ and γpr = γp are provided respectively. 相似文献
4.
Alfred Geroldinger David J. Grynkiewicz Wolfgang A. Schmid 《Acta Mathematica Hungarica》2011,131(4):323-345
For a finite abelian group G and a positive integer d, let s
dℕ(G) denote the smallest integer ℓ∈ℕ0 such that every sequence S over G of length |S|≧ℓ has a nonempty zero-sum subsequence T of length |T|≡0 mod d. We determine s
dℕ(G) for all d≧1 when G has rank at most two and, under mild conditions on d, also obtain precise values in the case of p-groups. In the same spirit, we obtain new upper bounds for the Erdős–Ginzburg–Ziv constant provided that, for the p-subgroups G
p
of G, the Davenport constant D(G
p
) is bounded above by 2exp (G
p
)−1. This generalizes former results for groups of rank two. 相似文献
5.
Let G be a permutation group on a set Ω with no fixed points in,and m be a positive integer.Then the movement of G is defined as move(G):=sup Γ {|Γg\Γ| | g ∈ G}.It was shown by Praeger that if move(G) = m,then |Ω| 3m + t-1,where t is the number of G-orbits on.In this paper,all intransitive permutation groups with degree 3m+t-1 which have maximum bound are classified.Indeed,a positive answer to her question that whether the upper bound |Ω| = 3m + t-1 for |Ω| is sharp for every t > 1 is given. 相似文献
6.
We prove that there exists an absolute constant c > 0 such that for any finite set A ⊆ ℤ with |A| ≥ 2 and any positive integer m < c|A|/ ln |A| there are at most m integers b > 0 satisfying |(A + b) \ A| ≤ m; equivalently, there are at most m positive integers possessing |A| −m (or more) representations as a difference of two elements of A. 相似文献
7.
XuXinping 《高校应用数学学报(英文版)》2005,20(1):121-126
Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u. For any U V(G) ,let N(U)=Uu,∈UN(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgraph isomorphic to K1.3. One of the fundamental results concerning cycles in claw-free graphs is due to Tian Feng,et al. : Let G be a 2-connected claw-free graph of order n,and d(u) d(v) d(w)≥n-2 for every independent vertex set {u,v,w} of G, then G is Hamiltonian. It is proved that, for any three positive integers s ,t and w,such that if G is a (s t w-1)connected claw-free graph of order n,and d(S) d(T) d(W)>n-(s t w) for every three disjoint independent vertex sets S,T,W with |S |=s, |T|=t, |W|=w,and S∪T∪W is also independent ,then G is Hamiltonian. Other related results are obtained too. 相似文献
8.
LetG be a finite group, andS a subset ofG \ |1| withS =S
−1. We useX = Cay(G,S) to denote the Cayley graph ofG with respect toS. We callS a Cl-subset ofG, if for any isomorphism Cay(G,S) ≈ Cay(G,T) there is an α∈ Aut(G) such thatS
α =T. Assume that m is a positive integer.G is called anm-Cl-group if every subsetS ofG withS =S
−1 and | S | ≤m is Cl. In this paper we prove that the alternating groupA
5 is a 4-Cl-group, which was a conjecture posed by Li and Praeger. 相似文献
9.
A. V. Karzanov 《Combinatorica》1985,5(4):325-335
A family ℱ of cuts of an undirected graphG=(V, E) is known to have the weak MFMC-property if (i) ℱ is the set ofT-cuts for someT⊆V with |T| even, or (ii) ℱ is the set of two-commodity cuts ofG, i.e. cuts separating any two distinguished pairs of vertices ofG, or (iii) ℱ is the set of cuts induced (in a sense) by a ring of subsets of a setT⊆V. In the present work we consider a large class of families of cuts of complete graphs and prove that a family from this class
has the MFMC-property if and only if it is one of (i), (ii), (iii). 相似文献
10.
Let G be an abelian
group of order n. The
critical number c(G) of G is the smallest
s such that the subset sums
set (S) covers all G for eachs ubset
SG\{0} of cardinality |S|s. It has been recently proved that, if
p is the smallest prime
dividing n and
n/p is composite, then
c(G)=|G|/p+p–2, thus establishing a conjecture of
Diderrich.We characterize the critical sets with |S|=|G|/p+p–3 and (S)=G, where p3 is the smallest prime dividing
n, n/p is composite and
n7p2+3p.We also extend a result of Diderrichan d Mann by proving
that, for n67, |S|n/3+2 and S=G
imply (S)=G. Sets of cardinality
for which
(S) =G are also characterized when
n183, the smallest prime
p dividing
n is odd and
n/p is composite. Finally we
obtain a necessary and sufficient condition for the equality
(G)=G
to hold when |S|n/(p+2)+p, where p5, n/p is composite and
n15p2.* Work partially supported by the Spanish Research
Council under grant TIC2000-1017 Work partially supported by the Catalan Research
Council under grant 2000SGR00079 相似文献
11.
Edward A. Bertram 《Israel Journal of Mathematics》1984,47(4):335-344
In 1955 R. Brauer and K. A. Fowler showed that ifG is a group of even order >2, and the order |Z(G)| of the center ofG is odd, then there exists a strongly real) elementx∈G−Z whose centralizer satisfies|C
G(x)|>|G|1/3. In Theorem 1 we show that every non-abeliansolvable groupG contains an elementx∈G−Z such that|C
G(x)|>[G:G′∩Z]1/2 (and thus|C
G(x)|>|G|1/3). We also note that if non-abelianG is either metabelian, nilpotent or (more generally) supersolvable, or anA-group, or any Frobenius group, then|C
G(x)|>|G|1/2 for somex∈G−Z. In Theorem 2 we prove that every non-abelian groupG of orderp
mqn (p, q primes) contains a proper centralizer of order >|G|1/2. Finally, in Theorem 3 we show that theaverage
|C(x)|, x∈G, is ≧c|G|
1/3 for metabelian groups, wherec is constant and the exponent 1/3 is best possible. 相似文献
12.
Let k ≥ 2 be an integer. We show that if G is a (k + 1)-connected graph and each pair of nonadjacent vertices in G has degree sum at least |G| + 1, then for each subset S of V(G) with |S| = k, G has a spanning tree such that S is the set of endvertices. This result generalizes Ore’s theorem which guarantees the existence of a Hamilton path connecting
any two vertices.
Dedicated to Professor Hikoe Enomoto on his 60th birthday. 相似文献
13.
Expanders obtained from affine transformations 总被引:1,自引:0,他引:1
A bipartite graphG=(U, V, E) is an (n, k, δ, α) expander if |U|=|V|=n, |E|≦kn, and for anyX⊆U with |X|≦αn, |Γ
G
(X)|≧(1+δ(1−|X|/n)) |X|, whereΓ
G
(X) is the set of nodes inV connected to nodes inX with edges inE. We show, using relatively elementary analysis in linear algebra, that the problem of estimating the coefficientδ of a bipartite graph is reduced to that of estimating the second largest eigenvalue of a matrix related to the graph. In
particular, we consider the case where the bipartite graphs are defined from affine transformations, and obtain some general
results on estimating the eigenvalues of the matrix by using the discrete Fourier transform. These results are then used to
estimate the expanding coefficients of bipartite graphs obtained from two-dimensional affine transformations and those obtained
from one-dimensional ones. 相似文献
14.
Paul Wollan 《Combinatorica》2011,31(1):95-126
We prove that for all positive integers k, there exists an integer N =N(k) such that the following holds. Let G be a graph and let Γ an abelian group with no element of order two. Let γ: E(G)→Γ be a function from the edges of G to the elements of Γ. A non-zero cycle is a cycle C such that Σ
e∈E(C)
γ(e) ≠ 0 where 0 is the identity element of Γ. Then G either contains k vertex disjoint non-zero cycles or there exists a set X ⊆ V (G) with |X| ≤N(k) such that G−X contains no non-zero cycle. 相似文献
15.
Katarzyna Jesse-Józefczyk 《Central European Journal of Mathematics》2012,10(3):1113-1124
Let G = (V, E) be a graph. A global secure set SD ⊆ V is a dominating set which satisfies the condition: for all X ⊆ SD, |N[X] ∩ SD| ≥ | N[X] − SD|. A global defensive alliance is a set of vertices A that is dominating and satisfies a weakened condition: for all x ∈ A, |N[x] ∩ A| ≥ |N[x] − A|. We give an upper bound on the cardinality of minimum global secure sets in cactus trees. We also present some results for
trees, and we relate them to the known bounds on the minimum cardinality of global defensive alliances. 相似文献
16.
LetA={a
1, …,a
k} and {b
1, …,b
k} be two subsets of an abelian groupG, k≤|G|. Snevily conjectured that, when |G| is odd, there is a numbering of the elements ofB such thata
i+b
i,1≤i≤k are pairwise distinct. By using a polynomial method, Alon affirmed this conjecture for |G| prime, even whenA is a sequence ofk<|G| elements. With a new application of the polynomial method, Dasgupta, Károlyi, Serra and Szegedy extended Alon’s result to
the groupsZ
p
r
andZ
p
rin the casek<p and verified Snevily’s conjecture for every cyclic group. In this paper, by employing group rings as a tool, we prove that
Alon’s result is true for any finite abelianp-group withk<√2p, and verify Snevily’s conjecture for every abelian group of odd order in the casek<√p, wherep is the smallest prime divisor of |G|.
This work has been supported partly by NSFC grant number 19971058 and 10271080. 相似文献
17.
LetA, B, S be finite subsets of an abelian groupG. Suppose that the restricted sumsetC={α+b: α ∈A, b ∈B, and α − b ∉S} is nonempty and somec∈C can be written asa+b witha∈A andb∈B in at mostm ways. We show that ifG is torsion-free or elementary abelian, then |C|≥|A|+|B|−|S|−m. We also prove that |C|≥|A|+|B|−2|S|−m if the torsion subgroup ofG is cyclic. In the caseS={0} this provides an advance on a conjecture of Lev.
This author is responsible for communications, and supported by the National Science Fund for Distinguished Young Scholars
(No. 10425103) and the Key Program of NSF (No. 10331020) in China. 相似文献
18.
Let G be a finite group with derived subgroup of rank r. We prove that |G: Z
2(G)| ≤ |G′|2r
. Motivated by the results of I. M. Isaacs in [5] we show that if G is capable then |G: Z(G)| ≤ |G′|4r
. This answers a question of L. Pyber. We prove that if G is a capable p-group then the rank of G/Z(G) is bounded above in terms of the rank of G′. 相似文献
19.
A subset S of vertices of a graph G is a secure set if |N [X] ∩ S| ≥ |N [X] ? S| holds for any subset X of S, where N [X] denotes the closed neighborhood of X. The minimum cardinality s(G) of a secure set in G is called the security number of G. We investigate the security number of lexicographic product graphs by defining a new concept of tightly-securable graphs. In particular we derive several exact results for different families of graphs which yield some general results. 相似文献
20.
Walter Bergweiler 《Journal d'Analyse Mathématique》1994,63(1):121-129
Let (zj) be a sequence of complex numbers satisfying |zj|→ ∞ asj → ∞ and denote by n(r) the number of zj satisfying |zj|≤ r. Suppose that lim infr → ⇈ log n(r)/ logr > 0. Let ϕ be a positive, non-decreasing function satisfying ∫∞ (ϕ(t)t logt)−1
dt < ∞. It is proved that there exists an entire functionf whose zeros are the zj such that log log M(r,f) = o((log n(r))2ϕ(log n(r))) asr → ∞ outside some exceptional set of finite logarithmic measure, and that the integral condition on ϕ is best possible here.
These results answer a question by A. A. Gol’dberg. 相似文献