首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 171 毫秒
1.
Let G be an infinite graph embedded in a closed 2-manifold, such that each open face of the embedding is homeomorphic to an open disk and is bounded by finite number of edges. For each vertex x of G, define the combinatorial curvature
as that of [8], where d(x) is the degree of x, F(x) is the multiset of all open faces σ in the embedding such that the closure contains x (the multiplicity of σ is the number of times that x is visited along ∂σ), and |σ| is the number of sides of edges bounding the face σ. In this paper, we first show that if the absolute total curvature ∑ xV(G) G (x)| is finite, then G has only finite number of vertices of non-vanishing curvature. Next we present a Gauss-Bonnet formula for embedded infinite graphs with finite number of accumulation points. At last, for a finite simple graph G with 3 ≤ d G (x) < ∞ and Φ G (x) > 0 for every xV(G), we have (i) if G is embedded in a projective plane and #(V(G)) = n ≥ 1722, then G is isomorphic to the projective wheel P n ; (ii) if G is embedded in a sphere and #(V(G)) = n ≥ 3444, then G is isomorphic to the sphere annulus either A n or B n ; and (iii) if d G (x) = 5 for all xV(G), then there are only 49 possible embedded plane graphs and 16 possible embedded projective plane graphs. Guantao Chen: The second author was partially supported by NSF DMS-0070514 and NSA-H98230-04-1-0300.  相似文献   

2.
In this paper, we show the equivalence of somequasi-random properties for sparse graphs, that is, graphsG with edge densityp=|E(G)|/( 2 n )=o(1), whereo(1)→0 asn=|V(G)|→∞. Our main result (Theorem 16) is the following embedding result. For a graphJ, writeN J(x) for the neighborhood of the vertexx inJ, and letδ(J) andΔ(J) be the minimum and the maximum degree inJ. LetH be atriangle-free graph and setd H=max{δ(J):JH}. Moreover, putD H=min{2d H,Δ(H)}. LetC>1 be a fixed constant and supposep=p(n)≫n −1 D H. We show that ifG is such that
(i)  deg G (x)≤C pn for allxV(G),
(ii)  for all 2≤rD H and for all distinct verticesx 1, ...,x rV(G),
,
(iii)  for all but at mosto(n 2) pairs {x 1,x 2} ⊆V(G),
, then the number of labeled copies ofH inG is
.
Moreover, we discuss a setting under which an arbitrary graphH (not necessarily triangle-free) can be embedded inG. We also present an embedding result for directed graphs. Research supported by a CNPq/NSF cooperative grant. Partially supported by MCT/CNPq through ProNEx Programme (Proc. CNPq 664107/1997-4) and by CNPq (Proc. 300334/93-1 and 468516/2000-0). Partially supported by NSF Grant 0071261. Supported by NSF grant CCR-9820931.  相似文献   

3.
We prove that the identity
holds for all directed graphs G and H. Similar bounds for the usual chromatic number seem to be much harder to obtain: It is still not known whether there exists a number n such that χ(G×H) ≥ 4 for all directed graphs G, H with χ(G) ≥ χ(H) ≥ n. In fact, we prove that for every integer n ≥ 4, there exist directed graphs Gn, Hn such that χ(Gn) = n, χ(Hn) = 4 and χ(Gn×Hn) = 3.  相似文献   

4.
Let H be any graph. We determine up to an additive constant the minimum degree of a graph G which ensures that G has a perfect H-packing (also called an H-factor). More precisely, let δ(H,n) denote the smallest integer k such that every graph G whose order n is divisible by |H| and with δ(G)≥k contains a perfect H-packing. We show that
. The value of χ*(H) depends on the relative sizes of the colour classes in the optimal colourings of H and satisfies χ(H)−1<χ*(H)≤χ(H).  相似文献   

5.
All graphs considered are finite, undirected, with no loops, no multiple edges and no isolated vertices. For a graphH=〈V(H),E(H)〉 and forSV(H) defineN(S)={xV(H):xyE(H) for someyS}. Define alsoδ(H)= max {|S| − |N(S)|:SV(H)},γ(H)=1/2(|V(H)|+δ(H)). For two graphsG, H letN(G, H) denote the number of subgraphs ofG isomorphic toH. Define also forl>0,N(l, H)=maxN(G, H), where the maximum is taken over all graphsG withl edges. We investigate the asymptotic behaviour ofN(l, H) for fixedH asl tends to infinity. The main results are:Theorem A. For every graph H there are positive constants c 1, c2 such that {fx116-1}. Theorem B. If δ(H)=0then {fx116-2},where |AutH|is the number of automorphisms of H. (It turns out thatδ(H)=0 iffH has a spanning subgraph which is a disjoint union of cycles and isolated edges.) This paper forms part of an M.Sc. Thesis written by the author under the supervision of Prof. M. A. Perles from the Hebrew University of Jerusalem.  相似文献   

6.
7.
We present results on total domination in a partitioned graph G = (V, E). Let γ t (G) denote the total dominating number of G. For a partition , k ≥ 2, of V, let γ t (G; V i ) be the cardinality of a smallest subset of V such that every vertex of V i has a neighbour in it and define the following
We summarize known bounds on γ t (G) and for graphs with all degrees at least δ we derive the following bounds for f t (G; k) and g t (G; k).
(i)  For δ ≥ 2 and k ≥ 3 we prove f t (G; k) ≤ 11|V|/7 and this inequality is best possible.
(ii)  for δ ≥ 3 we prove that f t (G; 2) ≤ (5/4 − 1/372)|V|. That inequality may not be best possible, but we conjecture that f t (G; 2) ≤ 7|V|/6 is.
(iii)  for δ ≥ 3 we prove f t (G; k) ≤  3|V|/2 and this inequality is best possible.
(iv)  for δ ≥ 3 the inequality g t (G; k) ≤ 3|V|/4 holds and is best possible.
  相似文献   

8.
Let G be a finite and connected graph, we will note by l(G) the maximum length of an injective path in G. We will show (by two dictinct proofs, one using sub-trees of G and the other based on multiflows of paths) that sup (P,μ)∈?(G) I(P, μ)/λ(P, μ) = l(G), where the supremum is taken over all Markovian kernels P reversible with respect to a probability μ and whose allowed transitions are given by the edges of G, and where I(P, μ) (respectively λ(P, μ)) is the isoperimetric constant (resp. the spectral gap) associated to the couple (P, μ). Then we will study more precisely the same supremum, but where the probability μ is also fixed. These results give optimal minorations of the spectral gap which are linear with respect to the isoperimetric constant (and not quadratic, as in the Cheeger inequality), and we will give several examples on infinite graphs. Re?u: 12 ao?t 1997 / Version révisée: 9 novembre 1998  相似文献   

9.
LetH be any complex inner product space with inner product <·,·>. We say thatf: ℂ→ℂ is Hermitian positive definite onH if the matrix
(1)
is Hermitian positive definite for all choice ofz 1,…,z n inH for alln. It is strictly Hermitian positive definite if the matrix (*) is also non-singular for any choice of distinctz 1,…,z n inH. In this article, we prove that if dimH≥3, thenf is Hermitian positive definite onH if and only if
(1)
whereb k,l ≥0 for allk, l in ℤ, and the series converges for allz in ℂ. We also prove thatf of the form (**) is strictly Hermitian positive definite on anyH if and only if the setJ={(k,l):b k,l >0} is such that (0,0)∈J, and every arithmetic sequence in ℤ intersects the values {kl: (k, l)∈J} an infinite number of times.  相似文献   

10.
All graphs considered are finite, undirected, with no loops, no multiple edges and no isolated vertices. For two graphsG, H, letN(G, H) denote the number of subgraphs ofG isomorphic toH. Define also, forl≧0,N(l, H)=maxN(G, H), where the maximum is taken over all graphsG withl edges. We determineN(l, H) precisely for alll≧0 whenH is a disjoint union of two stars, and also whenH is a disjoint union ofr≧3 stars, each of sizes ors+1, wheresr. We also determineN(l, H) for sufficiently largel whenH is a disjoint union ofr stars, of sizess 1s 2≧…≧s r>r, provided (s 1s r)2<s 1+s r−2r. We further show that ifH is a graph withk edges, then the ratioN(l, H)/l k tends to a finite limit asl→∞. This limit is non-zero iffH is a disjoint union of stars.  相似文献   

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

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