共查询到20条相似文献,搜索用时 234 毫秒
1.
Let K
m,nbe a complete bipartite graph with two partite sets having m and n vertices, respectively. A K
p,q-factorization of K
m,n is a set of edge-disjoint K
p,q-factors of K
m,n which partition the set of edges of K
m,n. When p = 1 and q is a prime number, Wang, in his paper “On K
1,k
-factorizations of a complete bipartite graph” (Discrete Math, 1994, 126: 359—364), investigated the K
1,q
-factorization of K
m,nand gave a sufficient condition for such a factorization to exist. In the paper “K
1,k
-factorizations of complete bipartite graphs” (Discrete Math, 2002, 259: 301—306), Du and Wang extended Wang’s result to the
case that q is any positive integer. In this paper, we give a sufficient condition for K
m,n to have a K
p,q-factorization. As a special case, it is shown that the Martin’s BAC conjecture is true when p : q = k : (k+ 1) for any positive integer k. 相似文献
2.
Let G and R each be a finite set of green and red points, respectively, such that |G|=n, |R|=n−k, G∩R=∅, and the points of G∪R are not all collinear. Let t be the total number of lines determined by G∪R. The number of equichromatic lines (a subset of bichromatic) is at least (t+2n+3−k(k+1))/4. A slightly weaker lower bound exists for bichromatic lines determined by points in ℂ2. For sufficiently large point sets, a proof of a conjecture by Kleitman and Pinchasi is provided. A lower bound of (2t+14n−k(3k+7))/14 is demonstrated for bichromatic lines passing through at most six points. Lower bounds are also established for equichromatic
lines passing through at most four, five, or six points. 相似文献
3.
Hong Wang 《Graphs and Combinatorics》2001,17(1):177-183
Let G=(V
1,V
2;E) be a bipartite graph with 2k≤m=|V
1|≤|V
2|=n, where k is a positive integer. We show that if the number of edges of G is at least (2k−1)(n−1)+m, then G contains k vertex-disjoint cycles, unless e(G)=(2k−1)(n−1)+m and G belongs to a known class of graphs.
Received: December 9, 1998 Final version received: June 2, 1999 相似文献
4.
Suppose thatA ⊂R
n
is a bounded set of diameter 1 and that:f:A →l
2 is a map satisfying the nearisometry condition |x−y|−ɛ≤|fx−fy|≤|x−y|+ɛ withɛ≤1. Then there is an isometryS:A →l
2 such that |Sx−fx|≤c
n √ɛ for allx inA. IfA satisfies a thickness condition and iff:A →R
n
, then there is an isometryS:R
n
→R
n
with |Sx−fx|≤c
nɛ/q, whereq is a thickness parameter. 相似文献
5.
A graph G of order p is k-factor-critical,where p and k are positive integers with the same parity, if the deletion of any set of k vertices results in a graph with a perfect matching. G is called maximal non-k-factor-critical if G is not k-factor-critical but G+e is k-factor-critical for every missing edge e∉E(G). A connected graph G with a perfect matching on 2n vertices is k-extendable, for 1?k?n-1, if for every matching M of size k in G there is a perfect matching in G containing all edges of M. G is called maximal non-k-extendable if G is not k-extendable but G+e is k-extendable for every missing edge e∉E(G) . A connected bipartite graph G with a bipartitioning set (X,Y) such that |X|=|Y|=n is maximal non-k-extendable bipartite if G is not k-extendable but G+xy is k-extendable for any edge xy∉E(G) with x∈X and y∈Y. A complete characterization of maximal non-k-factor-critical graphs, maximal non-k-extendable graphs and maximal non-k-extendable bipartite graphs is given. 相似文献
6.
Camino Balbuena Martín Cera Pedro García-Vázquez Juan Carlos Valenzuela 《数学学报(英文版)》2011,27(11):2085-2100
For a bipartite graph G on m and n vertices, respectively, in its vertices classes, and for integers s and t such that 2 ≤ s ≤ t, 0 ≤ m − s ≤ n − t, and m + n ≤ 2s + t − 1, we prove that if G has at least mn − (2(m − s) + n − t) edges then it contains a subdivision of the complete bipartite K
(s,t) with s vertices in the m-class and t vertices in the n-class. Furthermore, we characterize the corresponding extremal bipartite graphs with mn − (2(m − s) + n − t + 1) edges for this topological Turan type problem. 相似文献
7.
If a pointq ofS has the property that each neighborhood ofq contains pointsx andy such that the segmentxy is not contained byS, q is called a point of local nonconvexity ofS. LetQ denote the set of points of local nonconvexity ofS. Tietze’s well known theorem that a closed connected setS in a linear topological space is convex ifQ=φ is generalized in the result:If S is a closed set in a linear topological space such that S ∼ Q is connected and |Q|=n<∞,then S is the union of n+1or fewer closed convex sets. Letk be the minimal number of convex sets needed in a convex covering ofS. Bounds fork in terms ofm andn are obtained for sets having propertyP
m and |Q|=n. 相似文献
8.
Sergey V. Avgustinovich Olof Heden Faina I. Solov’eva 《Designs, Codes and Cryptography》2006,39(3):317-322
The main result is that to any even integer q in the interval 0 ≤ q ≤ 2n+1-2log(n+1), there are two perfect codes C1 and C2 of length n = 2m − 1, m ≥ 4, such that |C1 ∩ C2| = q. 相似文献
9.
In our earlier paper [9], generalizing the well known notion of graceful graphs, a (p, m, n)-signed graph S of order p, with m positive edges and n negative edges, is called graceful if there exists an injective function f that assigns to its p vertices integers 0, 1,...,q = m + n such that when to each edge uv of S one assigns the absolute difference |f(u)-f(v)| the set of integers received by the positive edges of S is {1,2,...,m} and the set of integers received by the negative edges of S is {1,2,...,n}. Considering the conjecture therein that all signed cycles Zk, of admissible length k 3 and signed structures, are graceful, we establish in this paper its truth for all possible signed cycles of lengths 0, 2 or 3 (mod 4) in which the set of negative edges forms a connected subsigraph. 相似文献
10.
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. 相似文献
11.
Swastik Kopparty Vsevolod F. Lev Shubhangi Saraf Madhu Sudan 《Journal of Algebraic Combinatorics》2011,34(3):337-355
For a finite vector space V and a nonnegative integer r≤dim V, we estimate the smallest possible size of a subset of V, containing a translate of every r-dimensional subspace. In particular, we show that if K⊆V is the smallest subset with this property, n denotes the dimension of V, and q is the size of the underlying field, then for r bounded and r<n≤rq
r−1, we have |V∖K|=Θ(nq
n−r+1); this improves the previously known bounds |V∖K|=Ω(q
n−r+1) and |V∖K|=O(n
2
q
n−r+1). 相似文献
12.
V. E. Maiorov 《Ukrainian Mathematical Journal》2010,62(3):452-466
We study the approximation of the classes of functions by the manifold R
n
formed by all possible linear combinations of n ridge functions of the form r(a · x)): It is proved that, for any 1 ≤ q ≤ p ≤ ∞, the deviation of the Sobolev class W
r
p
from the set R
n
of ridge functions in the space L
q
(B
d
) satisfies the sharp order n
-r/(d-1). 相似文献
13.
Claude Berge 《Combinatorica》1982,2(3):213-222
Gallai and Milgram have shown that the vertices of a directed graph, with stability number α(G), can be covered by exactly α(G) disjoint paths. However, the various proofs of this result do not imply the existence of a maximum stable setS and of a partition of the vertex-set into paths μ1, μ2, ..., μk such tht |μi ∩S|=1 for alli.
Later, Gallai proved that in a directed graph, the maximum number of vertices in a path is at least equal to the chromatic
number; here again, we do not know if there exists an optimal coloring (S
1,S
2, ...,S
k) and a path μ such that |μ ∩S
i|=1 for alli.
In this paper we show that many directed graphs, like the perfect graphs, have stronger properties: for every maximal stable
setS there exists a partition of the vertex set into paths which meet the stable set in only one point. Also: for every optimal
coloring there exists a path which meets each color class in only one point. This suggests several conjecties similar to the
perfect graph conjecture.
Dedicated to Tibor Gallai on his seventieth birthday 相似文献
14.
For any quasiordered set (`quoset') or topological space S, the set Sub
S of all nonempty subquosets or subspaces is quasiordered by embeddability. Given any cardinal number n, denote by p
n
and q
n
the smallest size of spaces S such that each poset, respectively, quoset with n points is embeddable in Sub
S. For finite n, we prove the inequalities n + 1 ≤p
n
≤q
n
≤p
n
+ l(n) + l(l(n)), where l(n) = min{k∈ℕ∣n≤2
k
}. For the smallest size b
n
of spaces S so that Sub
S contains a principal filter isomorphic to the power set ?(n), we show n + l(n) − 1 ≤b
n
≤n + l(n) + l(l(n))+2. Since p
n
≤b
n
, we thus improve recent results of McCluskey and McMaster who obtained p
n
≤n
2. For infinite n, we obtain the equation b
n
= p
n
= q
n
= n.
Received: April 19, 1999 Final version received: February 21, 2000 相似文献
15.
The well known “real-life examples” of small world graphs, including the graph of binary relation: “two persons on the earth
know each other” contains cliques, so they have cycles of order 3 and 4. Some problems of Computer Science require explicit
construction of regular algebraic graphs with small diameter but without small cycles. The well known examples here are generalised
polygons, which are small world algebraic graphs i.e. graphs with the diameter d≤clog
k−1(v), where v is order, k is the degree and c is the independent constant, semiplanes (regular bipartite graphs without cycles of order 4); graphs
that can be homomorphically mapped onto the ordinary polygons. The problem of the existence of regular graphs satisfying these
conditions with the degree ≥k and the diameter ≥d for each pair k≥3 and d≥3 is addressed in the paper. This problem is positively solved via the explicit construction. Generalised Schubert cells
are defined in the spirit of Gelfand-Macpherson theorem for the Grassmanian. Constructed graph, induced on the generalised
largest Schubert cells, is isomorphic to the well-known Wenger’s graph. We prove that the family of edge-transitive q-regular Wenger graphs of order 2q
n
, where integer n≥2 and q is prime power, q≥n, q>2 is a family of small world semiplanes. We observe the applications of some classes of small world graphs without small
cycles to Cryptography and Coding Theory. 相似文献
16.
A minimal blocker in a bipartite graph G is a minimal set of edges the removal of which leaves no perfect matching in G. We give an explicit characterization of the minimal blockers of a bipartite graph G. This result allows us to obtain a polynomial delay algorithm for finding all minimal blockers of a given bipartite graph. Equivalently, we obtain a polynomial delay algorithm for listing the anti‐vertices of the perfect matching polytope of G. We also provide generation algorithms for other related problems, including d‐factors in bipartite graphs, and perfect 2‐matchings in general graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 209–232, 2006 相似文献
17.
Some results on R
2-edge-connectivity of even regular graphs 总被引:1,自引:0,他引:1
XuJunming 《高校应用数学学报(英文版)》1999,14(3):366-370
Let G be a connected k(≥3)-regular graph with girth g. A set S of the edges in G is called an Rredge-cut if G-S is disconnected and comains neither an isolated vertex nor a one-degree vertex. The R2-edge-connectivity of G, denoted by λ^n(G), is the minimum cardinality over all R2-edge-cuts, which is an important measure for fault-tolerance of computer interconnection networks. In this paper, λ^n(G)=g(2k-2) for any 2k-regular connected graph G (≠K5) that is either edge-transitive or vertex-transitive and g≥5 is given. 相似文献
18.
Hüseyin Bor 《Proceedings Mathematical Sciences》1992,102(2):125-128
In this paper we have established a relation between |R,p
n
;δ|k and |R,q
n
;δ|k summability methods which generalizes the results of Bor [1] and Bosanquet [2]. 相似文献
19.
Hong Wang 《Journal of Graph Theory》1999,31(2):101-106
In this article, we consider the following problem: Given a bipartite graph G and a positive integer k, when does G have a 2‐factor with exactly k components? We will prove that if G = (V1, V2, E) is a bipartite graph with |V1| = |V2| = n ≥ 2k + 1 and δ (G) ≥ ⌈n/2⌉ + 1, then G contains a 2‐factor with exactly k components. We conjecture that if G = (V1, V2; E) is a bipartite graph such that |V1| = |V2| = n ≥ 2 and δ (G) ≥ ⌈n/2⌉ + 1, then, for any bipartite graph H = (U1, U2; F) with |U1| ≤ n, |U2| ≤ n and Δ (H) ≤ 2, G contains a subgraph isomorphic to H. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 101–106, 1999 相似文献
20.
A. D. Blinco S. I. El-Zanati G. F. Seelinger P. A. Sissokho L. E. Spence C. Vanden Eynden 《Designs, Codes and Cryptography》2008,48(1):69-77
Let V
n
(q) denote a vector space of dimension n over the field with q elements. A set of subspaces of V
n
(q) is a partition of V
n
(q) if every nonzero vector in V
n
(q) is contained in exactly one subspace in . A uniformly resolvable design is a pairwise balanced design whose blocks can be resolved in such a way that all blocks in a given parallel class have the
same size. A partition of V
n
(q) containing a
i
subspaces of dimension n
i
for 1 ≤ i ≤ k induces a uniformly resolvable design on q
n
points with a
i
parallel classes with block size , 1 ≤ i ≤ k, and also corresponds to a factorization of the complete graph into -factors, 1 ≤ i ≤ k. We present some sufficient and some necessary conditions for the existence of certain vector space partitions. For the partitions
that are shown to exist, we give the corresponding uniformly resolvable designs. We also show that there exist uniformly resolvable
designs on q
n
points where corresponding partitions of V
n
(q) do not exist.
A. D. Blinco—Part of this research was done while the author was visiting Illinois State University. 相似文献