首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
Recent work of Gowers [T. Gowers, A new proof of Szemerédi's theorem, Geom. Funct. Anal. 11 (2001) 465-588] and Nagle, Rödl, Schacht, and Skokan [B. Nagle, V. Rödl, M. Schacht, The counting lemma for regular k-uniform hypergraphs, Random Structures Algorithms, in press; V. Rödl, J. Skokan, Regularity lemma for k-uniform hypergraphs, Random Structures Algorithms, in press; V. Rödl, J. Skokan, Applications of the regularity lemma for uniform hypergraphs, preprint] has established a hypergraph removal lemma, which in turn implies some results of Szemerédi [E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arith. 27 (1975) 299-345], and Furstenberg and Katznelson [H. Furstenberg, Y. Katznelson, An ergodic Szemerédi theorem for commuting transformations, J. Anal. Math. 34 (1978) 275-291] concerning one-dimensional and multidimensional arithmetic progressions, respectively. In this paper we shall give a self-contained proof of this hypergraph removal lemma. In fact we prove a slight strengthening of the result, which we will use in a subsequent paper [T. Tao, The Gaussian primes contain arbitrarily shaped constellations, preprint] to establish (among other things) infinitely many constellations of a prescribed shape in the Gaussian primes.  相似文献   

2.
A graph G is induced matching extendable (shortly, IM-extendable), if every induced matching of G is included in a perfect matching of G. A graph G is claw-free, if G does not contain any induced subgraph isomorphic to K1,3. The kth power of a graph G, denoted by Gk, is the graph with vertex set V(G) in which two vertices are adjacent if and only if the distance between them in G is at most k. In this paper, the 4-regular claw-free IM-extendable graphs are characterized. It is shown that the only 4-regular claw-free connected IM-extendable graphs are , and Tr, r?2, where Tr is the graph with 4r vertices ui,vi,xi,yi, 1?i?r, such that for each i with 1?i?r, {ui,vi,xi,yi} is a clique of Tr and . We also show that a 4-regular strongly IM-extendable graph must be claw-free. As a consequence, the only 4-regular strongly IM-extendable graphs are K4×K2, and .  相似文献   

3.
Let k be a positive integer and G be a connected graph. This paper considers the relations among four graph theoretical parameters: the k-domination number γk(G), the connected k-domination number ; the k-independent domination number and the k-irredundance number irk(G). The authors prove that if an irk-set X is a k-independent set of G, then , and that for k?2, if irk(G)=1, if irk(G) is odd, and if irk(G) is even, which generalize some known results.  相似文献   

4.
Szemerédi's regularity lemma is a fundamental tool in extremal combinatorics. However, the original version is only helpful in studying dense graphs. In the 1990s, Kohayakawa and Rödl proved an analogue of Szemerédi's regularity lemma for sparse graphs as part of a general program toward extending extremal results to sparse graphs. Many of the key applications of Szemerédi's regularity lemma use an associated counting lemma. In order to prove extensions of these results which also apply to sparse graphs, it remained a well-known open problem to prove a counting lemma in sparse graphs.  相似文献   

5.
In this paper, we continue the study of total restrained domination in graphs, a concept introduced by Telle and Proskurowksi (Algorithms for vertex partitioning problems on partial k-trees, SIAM J. Discrete Math. 10 (1997) 529-550) as a vertex partitioning problem. A set S of vertices in a graph G=(V,E) is a total restrained dominating set of G 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 minimum cardinality of a total restrained dominating set of G is the total restrained domination number of G, denoted by γtr(G). Let G be a connected graph of order n with minimum degree at least 2 and with maximum degree Δ where Δ?n-2. We prove that if n?4, then and this bound is sharp. If we restrict G to a bipartite graph with Δ?3, then we improve this bound by showing that and that this bound is sharp.  相似文献   

6.
In this paper, we study a generalization of the paired domination number. Let G=(V,E) be a graph without an isolated vertex. A set DV(G) is a k-distance paired dominating set of G if D is a k-distance dominating set of G and the induced subgraph 〈D〉 has a perfect matching. The k-distance paired domination number is the cardinality of a smallest k-distance paired dominating set of G. We investigate properties of the k-distance paired domination number of a graph. We also give an upper bound and a lower bound on the k-distance paired domination number of a non-trivial tree T in terms of the size of T and the number of leaves in T and we also characterize the extremal trees.  相似文献   

7.
We present a unified approach to proving Ramsey-type theorems for graphs with a forbidden induced subgraph which can be used to extend and improve the earlier results of Rödl, Erd?s-Hajnal, Prömel-Rödl, Nikiforov, Chung-Graham, and ?uczak-Rödl. The proofs are based on a simple lemma (generalizing one by Graham, Rödl, and Ruciński) that can be used as a replacement for Szemerédi's regularity lemma, thereby giving much better bounds. The same approach can be also used to show that pseudo-random graphs have strong induced Ramsey properties. This leads to explicit constructions for upper bounds on various induced Ramsey numbers.  相似文献   

8.
For a simple graph G, the energy E(G) is defined as the sum of the absolute values of all the eigenvalues of its adjacency matrix A(G). Let n,m, respectively, be the number of vertices and edges of G. One well-known inequality is that , where λ1 is the spectral radius. If G is k-regular, we have . Denote . Balakrishnan [R. Balakrishnan, The energy of a graph, Linear Algebra Appl. 387 (2004) 287-295] proved that for each ?>0, there exist infinitely many n for each of which there exists a k-regular graph G of order n with k<n-1 and , and proposed an open problem that, given a positive integer n?3, and ?>0, does there exist a k-regular graph G of order n such that . In this paper, we show that for each ?>0, there exist infinitely many such n that . Moreover, we construct another class of simpler graphs which also supports the first assertion that .  相似文献   

9.
In this paper, we show that, for every locally compact abelian group G, the following statements are equivalent:
(i)
G contains no sequence such that {0}∪{±xnnN} is infinite and quasi-convex in G, and xn?0;
(ii)
one of the subgroups {gG∣2g=0} or {gG∣3g=0} is open in G;
(iii)
G contains an open compact subgroup of the form or for some cardinal κ.
  相似文献   

10.
A graph G of order n and size m is edge-magic if there is a bijection l:V(G)∪E(G)→[n+m] such that all sums l(a)+l(b)+l(ab), abE(G), are the same. We present new lower and upper bounds on M(n), the maximum size of an edge-magic graph of order n, being the first to show an upper bound of the form . Concrete estimates for ε can be obtained by knowing s(k,n), the maximum number of distinct pairwise sums that a k-subset of [n] can have.So, we also study s(k,n), motivated by the above connections to edge-magic graphs and by the fact that a few known functions from additive number theory can be expressed via s(k,n). For example, our estimate
  相似文献   

11.
The Estrada index of a graph G is defined as , where λ1,λ2,…,λn are the eigenvalues of G. The Laplacian Estrada index of a graph G is defined as , where μ1,μ2,…,μn are the Laplacian eigenvalues of G. An edge grafting operation on a graph moves a pendent edge between two pendent paths. We study the change of Estrada index of graph under edge grafting operation between two pendent paths at two adjacent vertices. As the application, we give the result on the change of Laplacian Estrada index of bipartite graph under edge grafting operation between two pendent paths at the same vertex. We also determine the unique tree with minimum Laplacian Estrada index among the set of trees with given maximum degree, and the unique trees with maximum Laplacian Estrada indices among the set of trees with given diameter, number of pendent vertices, matching number, independence number and domination number, respectively.  相似文献   

12.
This paper investigates the asymmetric marking games on line graphs. Suppose G is a graph with maximum degree Δ and G has an orientation with maximum outdegree k, we show that the (a,1)-game coloring number of the line graph of G is at most . When a=1, this improves some known results of the game coloring number of the line graphs.  相似文献   

13.
The rainbowness, rb(G), of a connected plane graph G is the minimum number k such that any colouring of vertices of the graph G using at least k colours involves a face all vertices of which receive distinct colours. For a connected cubic plane graph G we prove that
  相似文献   

14.
A function f:V(G)→{+1,0,-1} defined on the vertices of a graph G is a minus total dominating function if the sum of its function values over any open neighborhood is at least 1. The minus total domination number of G is the minimum weight of a minus total dominating function on G. By simply changing “{+1,0,-1}” in the above definition to “{+1,-1}”, we can define the signed total dominating function and the signed total domination number of G. In this paper we present a sharp lower bound on the signed total domination number for a k-partite graph, which results in a short proof of a result due to Kang et al. on the minus total domination number for a k-partite graph. We also give sharp lower bounds on and for triangle-free graphs and characterize the extremal graphs achieving these bounds.  相似文献   

15.
Let G=(V(G),E(G)) be a unicyclic simple undirected graph with largest vertex degree Δ. Let Cr be the unique cycle of G. The graph G-E(Cr) is a forest of r rooted trees T1,T2,…,Tr with root vertices v1,v2,…,vr, respectively. Let
  相似文献   

16.
A graph G is said to be hamiltonian path saturated (HPS for short), if G has no hamiltonian path but any addition of a new edge in G creates a hamiltonian path in G. It is known that an HPS graph of order n has size at most and, for n?6, the only HPS graph of order n and size is Kn-1K1. Denote by sat(n,HP) the minimum size of an HPS graph of order n. We prove that sat(n,HP)?⌊(3n-1)/2⌋-2. Using some properties of Isaacs’ snarks we give, for every n?54, an HPS graph Gn of order n and size ⌊(3n-1)/2⌋. This proves sat(n,HP)?⌊(3n-1)/2⌋ for n?54. We also consider m-path cover saturated graphs and Pm-saturated graphs with small size.  相似文献   

17.
Let G=(V,E) be a connected graph. For a symmetric, integer-valued function δ on V×V, where K is an integer constant, N0 is the set of nonnegative integers, and Z is the set of integers, we define a C-mapping by F(u,v,m)=δ(u,v)+mK. A coloring c of G is an F-coloring if F(u,v,|c(u)−c(v)|)?0 for every two distinct vertices u and v of G. The maximum color assigned by c to a vertex of G is the value of c, and the F-chromatic number F(G) is the minimum value among all F-colorings of G. For an ordering of the vertices of G, a greedy F-coloring c of s is defined by (1) c(v1)=1 and (2) for each i with 1?i<n, c(vi+1) is the smallest positive integer p such that F(vj,vi+1,|c(vj)−p|)?0, for each j with 1?j?i. The greedy F-chromatic number gF(s) of s is the maximum color assigned by c to a vertex of G. The greedy F-chromatic number of G is gF(G)=min{gF(s)} over all orderings s of V. The Grundy F-chromatic number is GF(G)=max{gF(s)} over all orderings s of V. It is shown that gF(G)=F(G) for every graph G and every F-coloring defined on G. The parameters gF(G) and GF(G) are studied and compared for a special case of the C-mapping F on a connected graph G, where δ(u,v) is the distance between u and v and .  相似文献   

18.
A set S of vertices of a graph G=(V,E) with no isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination numberγt(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision numbersdγt(G) is the minimum number of edges that must be subdivided in order to increase the total domination number. We consider graphs of order n?4, minimum degree δ and maximum degree Δ. We prove that if each component of G and has order at least 3 and , then and if each component of G and has order at least 2 and at least one component of G and has order at least 3, then . We also give a result on stronger than a conjecture by Harary and Haynes.  相似文献   

19.
Let G be a graph of order n and rank(G) denotes the rank of its adjacency matrix. Clearly, . In this paper we characterize all graphs G such that or n + 2. Also for every integer n ? 5 and any k, 0 ? k ? n, we construct a graph G of order n, such that .  相似文献   

20.
Let G be a graph on n vertices, and let λ1,λ2,…,λn be its eigenvalues. The Estrada index of G is a recently introduced graph invariant, defined as . We establish lower and upper bounds for EE in terms of the number of vertices and number of edges. Also some inequalities between EE and the energy of G are obtained.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号