共查询到20条相似文献,搜索用时 62 毫秒
1.
In this paper we study three-color Ramsey numbers. Let K
i,j
denote a complete i by j bipartite graph. We shall show that (i) for any connected graphs G
1, G
2 and G
3, if r(G
1, G
2)≥s(G
3), then r(G
1, G
2, G
3)≥(r(G
1, G
2)−1)(χ(G
3)−1)+s(G
3), where s(G
3) is the chromatic surplus of G
3; (ii) (k+m−2)(n−1)+1≤r(K
1,k
, K
1,m
, K
n
)≤ (k+m−1)(n−1)+1, and if k or m is odd, the second inequality becomes an equality; (iii) for any fixed m≥k≥2, there is a constant c such that r(K
k,m
, K
k,m
, K
n
)≤c(n/logn), and r(C
2m
, C
2m
, K
n
)≤c(n/logn)
m/(m−1)
for sufficiently large n.
Received: July 25, 2000 Final version received: July 30, 2002
RID="*"
ID="*" Partially supported by RGC, Hong Kong; FRG, Hong Kong Baptist University; and by NSFC, the scientific foundations of
education ministry of China, and the foundations of Jiangsu Province
Acknowledgments. The authors are grateful to the referee for his valuable comments.
AMS 2000 MSC: 05C55 相似文献
2.
Dr. Matthias Kriesell 《Combinatorica》2006,26(3):277-314
A non-complete graph G is called an (n,k)-graph if it is n-connected but G—X is not (n−|X|+1)-connected for any X ⊂V (G) with |X|≤k. Mader conjectured that for k≥3 the graph K2k+2−(1−factor) is the unique (2k,k)-graph(up to isomorphism).
Here we prove this conjecture. 相似文献
3.
For a graph G, we define σ2(G) := min{d(u) + d(v)|u, v ≠ ∈ E(G), u ≠ v}. Let k ≥ 1 be an integer and G be a graph of order n ≥ 3k. We prove if σ2(G) ≥ n + k − 1, then for any set of k independent vertices v
1,...,v
k
, G has k vertex-disjoint cycles C
1,..., C
k
of length at most four such that v
i
∈ V(C
i
) for all 1 ≤ i ≤ k. And show if σ2(G) ≥ n + k − 1, then for any set of k independent vertices v
1,...,v
k
, G has k vertex-disjoint cycles C
1,..., C
k
such that v
i
∈ V(C
i
) for all 1 ≤ i ≤ k, V(C
1) ∪...∪ V(C
k
) = V(G), and |C
i
| ≤ 4 for all 1 ≤ i ≤ k − 1.
The condition of degree sum σ2(G) ≥ n + k − 1 is sharp.
Received: December 20, 2006. Final version received: December 12, 2007. 相似文献
4.
Mark Pankov 《Journal of Algebraic Combinatorics》2011,33(4):555-570
Let V be an n-dimensional vector space (4≤n<∞) and let Gk(V){\mathcal{G}}_{k}(V) be the Grassmannian formed by all k-dimensional subspaces of V. The corresponding Grassmann graph will be denoted by Γ
k
(V). We describe all isometric embeddings of Johnson graphs J(l,m), 1<m<l−1 in Γ
k
(V), 1<k<n−1 (Theorem 4). As a consequence, we get the following: the image of every isometric embedding of J(n,k) in Γ
k
(V) is an apartment of Gk(V){\mathcal{G}}_{k}(V) if and only if n=2k. Our second result (Theorem 5) is a classification of rigid isometric embeddings of Johnson graphs in Γ
k
(V), 1<k<n−1. 相似文献
5.
Hong Lin Xiao-feng Guo 《应用数学学报(英文版)》2007,23(1):155-160
Let φ(G),κ(G),α(G),χ(G),cl(G),diam(G)denote the number of perfect matchings,connectivity,independence number,chromatic number,clique number and diameter of a graph G,respectively.In this note,by constructing some extremal graphs,the following extremal problems are solved:1.max{φ(G):|V(G)|=2n,κ(G)≤k}=k[(2n-3)!!],2.max{φ(G):|V(G)|=2n,α(G)≥k}=[multiply from i=0 to k-1(2n-k-i)[(2n-2k-1)!!],3.max{φ(G):|V(G)|=2n,χ(G)≤k}=φ(T_(k,2n))T_(k,2n)is the Turán graph,that is a complete k-partite graphon 2n vertices in which all parts are as equal in size as possible,4.max{φ(G):|V(G)|=2n,cl(G)=2}=n1,5.max{φ(G):|V(G)|=2n,diam(G)≥2}=(2n-2)(2n-3)[(2n-5)!!],max{φ(G):|V(G)|=2n,diam(G)≥3}=(n-1)~2[(2n-5)!!]. 相似文献
6.
Jian Wang 《高校应用数学学报(英文版)》2008,23(3):345-350
A K1,k-factorization of λKm,n is a set of edge-disjoint K1,k-factors of λKm,n, which partition the set of edges of λKm,n. In this paper, it is proved that a sufficient condition for the existence of K1,k-factorization of λKm,n, whenever k is any positive integer, is that (1) m ≤ kn, (2) n ≤ km, (3) km-n = kn-m ≡ 0 (mod (k^2- 1)) and (4) λ(km-n)(kn-m) ≡ 0 (mod k(k- 1)(k^2 - 1)(m + n)). 相似文献
7.
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 相似文献
8.
A k-tree of a graph is a spanning tree with maximum degree at most k. We give sufficient conditions for a graph G to have a k-tree with specified leaves: Let k,s, and n be integers such that k≥2, 0≤s≤k, and n≥s+1. Suppose that (1) G is (s+1)-connected and the degree sum of any k independent vertices of G is at least |G|+(k−1)s−1, or (2) G is n-connected and the independence number of G is at most (n−s)(k−1)+1. Then for any s specified vertices of G, G has a k-tree containing them as leaves. We also discuss the sharpness of the results.
This research was partially supported by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Encouragement
of Young Scientists, 15740077, 2005
This research was partially supported by the Japan Society for the Promotion of Science for Young Scientists. 相似文献
9.
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. 相似文献
10.
Let Gn,k denote the oriented grassmann manifold of orientedk-planes in ℝn. It is shown that for any continuous mapf: Gn,k → Gn,k, dim Gn,k = dim Gm,l = l(m −l), the Brouwer’s degree is zero, providedl > 1,n ≠ m. Similar results for continuous mapsg: ℂGm,l → ℂGn,k,h: ℍGm,l → ℍGn,k, 1 ≤ l < k ≤ n/2, k(n — k) = l(m — l) are also obtained. 相似文献
11.
A set A⊆V of the vertices of a graph G=(V,E) is an asteroidal set if for each vertex a∈A, the set A\{a} is contained in one component of G−N[a]. The maximum cardinality of an asteroidal set of G, denoted by an (G), is said to be the asteroidal number of G. We investigate structural properties of graphs of bounded asteroidal number. For every k≥1, an (G)≤k if and only if an (H)≤k for every minimal triangulation H of G. A dominating target is a set D of vertices such that D∪S is a dominating set of G for every set S such that G[D∪S] is connected. We show that every graph G has a dominating target with at most an (G) vertices. Finally, a connected graph G has a spanning tree T such that d
T
(x,y)−d
G
(x,y)≤3·|D|−1 for every pair x,y of vertices and every dominating target D of G.
Received: July 3, 1998 Final version received: August 10, 1999 相似文献
12.
A tree is called a k-tree if the maximum degree is at most k. We prove the following theorem, by which a closure concept for spanning k-trees of n-connected graphs can be defined. Let k ≥ 2 and n ≥ 1 be integers, and let u and v be a pair of nonadjacent vertices of an n-connected graph G such that deg
G
(u) + deg
G
(v) ≥ |G| − 1 − (k − 2)n, where |G| denotes the order of G. Then G has a spanning k-tree if and only if G + uv has a spanning k-tree. 相似文献
13.
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 相似文献
14.
Large Vertex-Disjoint Cycles in a Bipartite Graph 总被引:4,自引:0,他引:4
Hong Wang 《Graphs and Combinatorics》2000,16(3):359-366
Let s≥2 and k be two positive integers. Let G=(V
1,V
2;E) be a bipartite graph with |V
1|=|V
2|=n≥s
k and the minimum degree at least (s−1)k+1. When s=2 and n >2k, it is proved in [5] that G contains k vertex-disjoint cycles. In this paper, we show that if s≥3, then G contains k vertex-disjoint cycles of length at least 2s.
Received: March 2, 1998 Revised: October 26, 1998 相似文献
15.
Let G = (V, E) be a graph. A set S í V{S \subseteq V} is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex of V − S is adjacent to a vertex in V − S. The total restrained domination number of G, denoted by γ
tr
(G), is the smallest cardinality of a total restrained dominating set of G. We show that if δ ≥ 3, then γ
tr
(G) ≤ n − δ − 2 provided G is not one of several forbidden graphs. Furthermore, we show that if G is r − regular, where 4 ≤ r ≤ n − 3, then γ
tr
(G) ≤ n − diam(G) − r + 1. 相似文献
16.
For two vertices u and v of a connected graph G, the set I[u,v] consists of all those vertices lying on a u−v shortest path in G, while for a set S of vertices of G, the set I[S] is the union of all sets I[u,v] for u,v∈S. A set S is convex if I[S]=S. The convexity number con(G) of G is the maximum cardinality of a proper convex set of G. The clique number ω(G) is the maximum cardinality of a clique in G. If G is a connected graph of order n that is not complete, then n≥3 and 2≤ω(G)≤con(G)≤n−1. It is shown that for every triple l,k,n of integers with n≥3 and 2≤l≤k≤n−1, there exists a noncomplete connected graph G of order n with ω(G)=l and con(G)=k. Other results on convex numbers are also presented.
Received: August 19, 1998 Final version received: May 17, 2000 相似文献
17.
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. 相似文献
18.
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. 相似文献
19.
Haruko Okamura 《Graphs and Combinatorics》2005,21(4):503-514
Let k≥2 be an integer and G = (V(G), E(G)) be a k-edge-connected graph. For X⊆V(G), e(X) denotes the number of edges between X and V(G) − X. Let {si, ti}⊆Xi⊆V(G) (i=1,2) and X1∩X2=∅. We here prove that if k is even and e(Xi)≤2k−1 (i=1,2), then there exist paths P1 and P2 such that Pi joins si and ti, V(Pi)⊆Xi (i=1,2) and G − E(P1∪P2) is (k−2)-edge-connected (for odd k, if e(X1)≤2k−2 and e(X2)≤2k−1, then the same result holds [10]), and we give a generalization of this result and some other results about paths not containing
given edges. 相似文献
20.
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). 相似文献