共查询到20条相似文献,搜索用时 31 毫秒
1.
Sarmad Abbasi 《Graphs and Combinatorics》2000,16(2):129-137
The bipartite case of the Bollobás and Komlós conjecture states that for every j0, %>0 there is an !=!(j0, %) >0 such that the following statement holds: If G is any graph with minimum degree at least n$\displaystyle {n \over 2}+%n then G contains as subgraphs all n vertex bipartite graphs, H, satisfying¶H)hj0 \quad {\rm and} \quad b(H)h!n.$j (H)hj0 \quad {\rm and} \quad b(H)h!n.¶Here b(H), the bandwidth of H, is the smallest b such that the vertices of H can be ordered as v1,
, vn such that vi~Hvj implies |imj|hb.¶ This conjecture has been proved in [1]. Answering a question of E. Szemerédi [6] we show that this conjecture is tight in the sense that as %̂ then !̂. More precisely, we show that for any 0 such that that !(j0, %)Д %. 相似文献
2.
David S. Herscovici 《Journal of Graph Theory》2003,42(2):141-154
Chung defined a pebbling move on a graph G to be the removal of two pebbles from one vertex and the addition of one pebble to an adjacent vertex. The pebbling number of a connected graph is the smallest number f(G) such that any distribution of f(G) pebbles on G allows one pebble to be moved to any specified, but arbitrary vertex by a sequence of pebbling moves. Graham conjectured that for any connected graphs G and H, f(G×H)≤ f(G)f(H). We prove Graham's conjecture when G is a cycle for a variety of graphs H, including all cycles. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 141–154, 2003 相似文献
3.
Andreas Huck 《Graphs and Combinatorics》1999,15(1):29-77
We prove the following statement: Let G be a finite k-connected undirected planar graph and s be a vertex of G. Then there exist k spanning trees T1,
,Tk in G such that for each vertex xps of G, the k paths from x to s in T1,
,Tk are pairwise openly disjoint. 相似文献
4.
David S. Herscovici 《Discrete Mathematics》2008,308(24):6501-6512
A pebbling move on a connected graph G consists of removing two pebbles from some vertex and adding one pebble to an adjacent vertex. We define ft(G) as the smallest number such that whenever ft(G) pebbles are on G, we can move t pebbles to any specified, but arbitrary vertex. Graham conjectured that f1(G×H)≤f1(G)f1(H) for any connected G and H. We define the α-pebbling number α(G) and prove that α(Cpj×?×Cp2×Cp1×G)≤α(Cpj)?α(Cp2)α(Cp1)α(G) when none of the cycles is C5, and G satisfies one more criterion. We also apply this result with G=C5×C5 by showing that C5×C5 satisfies Chung’s two-pebbling property, and establishing bounds for ft(C5×C5). 相似文献
5.
The pebbling number of a graph G, f(G), is the least n such that, no matter how n pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of pebbling moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Let p1,p2,…,pn be positive integers and G be such a graph, V(G)=n. The thorn graph of the graph G, with parameters p1,p2,…,pn, is obtained by attaching pi new vertices of degree 1 to the vertex ui of the graph G, i=1,2,…,n. Graham conjectured that for any connected graphs G and H, f(G×H)≤f(G)f(H). We show that Graham’s conjecture holds true for a thorn graph of the complete graph with every by a graph with the two-pebbling property. As a corollary, Graham’s conjecture holds when G and H are the thorn graphs of the complete graphs with every . 相似文献
6.
Given a distribution of pebbles on the vertices of a connected graph G, a pebbling move on G consists of taking two pebbles off one vertex and placing one on an adjacent vertex. The pebbling number f(G) is the smallest number m such that for every distribution of m pebbles and every vertex v,a pebble can be moved to v. A graph G is said to have the 2-pebbling property if for any distribution with more than 2f(G) q pebbles, where q is the number of vertices with at least one pebble, it is possible,using pebbling moves, to get two pebbles to any vertex. Snevily conjectured that G(s,t) has the 2-pebbling property, where G(s, t) is a bipartite graph with partite sets of size s and t (s ≥ t). Similarly, the-pebbling number f (G) is the smallest number m such that for every distribution of m pebbles and every vertex v, pebbles can be moved to v. Herscovici et al. conjectured that f(G) ≤ 1.5n + 8-6 for the graph G with diameter 3, where n = |V (G)|. In this paper, we prove that if s ≥ 15 and G(s, t) has minimum degree at least (s+1)/ 2 , then f (G(s, t)) = s + t, G(s, t) has the 2-pebbling property and f (G(s, t)) ≤ s + t + 8(-1). In other words, we extend a result due to Czygrinow and Hurlbert, and show that the above Snevily conjecture and Herscovici et al. conjecture are true for G(s, t) with s ≥ 15 and minimum degree at least (s+1)/ 2 . 相似文献
7.
S. Haruki 《Aequationes Mathematicae》2002,63(3):201-209
Summary. Let (G, +) and (H, +) be abelian groups such that the equation 2u = v 2u = v is solvable in both G and H. It is shown that if f1, f2, f3, f4, : G ×G ? H f_1, f_2, f_3, f_4, : G \times G \longrightarrow H satisfy the functional equation f1(x + t, y + s) + f2(x - t, y - s) = f3(x + s, y - t) + f4(x - s, y + t) for all x, y, s, t ? G x, y, s, t \in G , then f1, f2, f3, and f4 are given by f1 = w + h, f2 = w - h, f3 = w + k, f4 = w - k where w : G ×G ? H w : G \times G \longrightarrow H is an arbitrary solution of f (x + t, y + s) + f (x - t, y - s) = f (x + s, y - t) + f (x - s, y + t) for all x, y, s, t ? G x, y, s, t \in G , and h, k : G ×G ? H h, k : G \times G \longrightarrow H are arbitrary solutions of Dy,t3g(x,y) = 0 \Delta_{y,t}^{3}g(x,y) = 0 and Dx,t3g(x,y) = 0 \Delta_{x,t}^{3}g(x,y) = 0 for all x, y, s, t ? G x, y, s, t \in G . 相似文献
8.
A. Thoma 《Archiv der Mathematik》2000,74(1):22-25
The binomial arithmetical rank of a binomial ideal I is the smallest integer s for which there exist binomials f1,..., fs in I such that rad (I) = rad (f1,..., fs). We completely determine the binomial arithmetical rank for the ideals of monomial curves in PKnP_K^n. In particular we prove that, if the characteristic of the field K is zero, then bar (I(C)) = n - 1 if C is complete intersection, otherwise bar (I(C)) = n. While it is known that if the characteristic of the field K is positive, then bar (I(C)) = n - 1 always. 相似文献
9.
R. Wolf 《Archiv der Mathematik》2001,76(4):308-313
Abstract. We prove the following result: Let X be a compact connected Hausdorff space and f be a continuous function on X x X. There exists some regular Borel probability measure m\mu on X such that the value of¶¶ ò\limit X f(x,y)dm(y)\int\limit _X f(x,y)d\mu (y) is independent of the choice of x in X if and only if the following assertion holds: For each positive integer n and for all (not necessarily distinct) x1,x2,...,xn,y1,y2,...,yn in X, there exists an x in X such that¶¶ ?i=1n f(xi,x)=?i=1n f(yi,x).\sum\limits _{i=1}^n f(x_i,x)=\sum\limits _{i=1}^n f(y_i,x). 相似文献
10.
I. Corovei 《Aequationes Mathematicae》2001,61(3):212-220
Summary. Consider Wilson's functional equation¶¶f(xy) + f(xy-1) = 2f(f)g(y) f(xy) + f(xy^{-1}) = 2f(f)g(y) , for f,g : G ? K f,g : G \to K ¶where G is a group and K a field with char K 1 2 {\rm char}\, K\ne 2 .¶Aczél, Chung and Ng in 1989 have solved Wilson's equation, assuming that the function g satisfies Kannappan's condition g(xyz) = g(xzy) and f(xy) = f(yx) for all x,y,z ? G x,y,z\in G .¶In the present paper we obtain the general solution of Wilson's equation when G is a P3-group and we show that there exist solutions different of those obtained by Aczél, Chung and Ng.¶A group G is said to be a P3-group if the commutator subgroup G' of G, generated by all commutators [x,y] := x-1y-1xy, has the order one or two. 相似文献
11.
Group Connectivity of 3-Edge-Connected Chordal Graphs 总被引:3,自引:0,他引:3
Hong-Jian Lai 《Graphs and Combinatorics》2000,16(2):165-176
Let A be a finite abelian group and G be a digraph. The boundary of a function f: E(G)ZA is a function f: V(G)ZA given by f(v)=~e leaving vf(e)m~e entering vf(e). The graph G is A-connected if for every b: V(G)ZA with ~v] V(G) b(v)=0, there is a function f: E(G)ZA{0} such that f=b. In [J. Combinatorial Theory, Ser. B 56 (1992) 165-182], Jaeger et al showed that every 3-edge-connected graph is A-connected, for every abelian group A with |A|̈́. It is conjectured that every 3-edge-connected graph is A-connected, for every abelian group A with |A|̓ and that every 5-edge-connected graph is A-connected, for every abelian group A with |A|́.¶ In this note, we investigate the group connectivity of 3-edge-connected chordal graphs and characterize 3-edge-connected chordal graphs that are A-connected for every finite abelian group A with |A|́. 相似文献
12.
Melody Chan 《Discrete Mathematics》2008,308(11):2301-2306
Consider a configuration of pebbles distributed on the vertices of a connected graph of order n. A pebbling step consists of removing two pebbles from a given vertex and placing one pebble on an adjacent vertex. A distribution of pebbles on a graph is called solvable if it is possible to place a pebble on any given vertex using a sequence of pebbling steps. The pebbling number of a graph, denoted f(G), is the minimal number of pebbles such that every configuration of f(G) pebbles on G is solvable. We derive several general upper bounds on the pebbling number, improving previous results. 相似文献
13.
Wolfgang M. Ruppert 《Archiv der Mathematik》1999,72(1):47-55
Let f=a0(x)+a1(x)y+a2(x)y2 ? \Bbb Z[x,y]f=a_0(x)+a_1(x)y+a_2(x)y^2\in {\Bbb Z}[x,y] be an absolutely irreducible polynomial of degree m in x. We show that the reduction f mod p will also be absolutely irreducible if p 3 cm·H(f)emp\ge c_m\cdot H(f)^{e_m} where H (f) is the height of f and e1 = 4,e2 = 6, e3 = 6 [2/3]{2}\over{3} and em = 2 m for m S 4. We also show that the exponents em are best possible for m 1 3m\ne 3 if a plausible number theoretic conjecture is true. 相似文献
14.
Johan Jonasson 《Random Structures and Algorithms》2000,16(2):131-142
Consider a simple random walk on a connected graph G=(V, E). Let C(u, v) be the expected time taken for the walk starting at vertex u to reach vertex v and then go back to u again, i.e., the commute time for u and v, and let C(G)=maxu, v∈VC(u, v). Further, let 𝒢(n, m) be the family of connected graphs on n vertices with m edges, , and let 𝒢(n)=∪m𝒢(n, m) be the family of all connected n‐vertex graphs. It is proved that if G∈(n, m) is such that C(G)=maxH∈𝒢(n, m)C(H) then G is either a lollipop graph or a so‐called double‐handled lollipop graph. It is further shown, using this result, that if C(G)=maxH∈𝒢(n)C(H) then G is the full lollipop graph or a full double‐handled lollipop graph with [(2n−1)/3] vertices in the clique unless n≤9 in which case G is the n‐path. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 131–142, 2000 相似文献
15.
If G and H are vertex-transitive graphs, then the framing number fr(G,H) of G and H is defined as the minimum order of a graph every vertex of which belongs to an induced G and an induced H. This paper investigates fr(C
m,C
n) for m<n. We show first that fr(C
m,C
n)≥n+2 and determine when equality occurs. Thereafter we establish general lower and upper bounds which show that fr(C
m,C
n) is approximately the minimum of and n+n/m.
Received: June 12, 1996 / Revised: June 2, 1997 相似文献
16.
Let X be a smooth algebraic surface, L ? Pic(X) L \in \textrm{Pic}(X) and H an ample divisor on X. Set MX,H(2; L, c2) the moduli space of rank 2, H-stable vector bundles F on X with det(F) = L and c2(F) = c2. In this paper, we show that the geometry of X and of MX,H(2; L, c2) are closely related. More precisely, we prove that for any ample divisor H on X and any L ? Pic(X) L \in \textrm{Pic}(X) , there exists
n0 ? \mathbbZ n_0 \in \mathbb{Z} such that for all
n0 \leqq c2 ? \mathbbZ n_0 \leqq c_2 \in \mathbb{Z} , MX,H(2; L, c2) is rational if and only if X is rational. 相似文献
17.
D. Lesnic 《Zeitschrift für Angewandte Mathematik und Physik (ZAMP)》2002,14(4):175-196
This paper considers the inverse determination of the positive unknown thermal properties K(T), C(T) and the unknown temperature T(x, t) in the nonlinear transient heat conduction equation. In addition to prescribed initial and/or boundary values, specified continuously differentiable temperature data T(x0, t) with non-zero derivative at a single sensor location x = x0 is given. When K(T) and C(T) obey a certain relationship which enables one to linearise exactly the nonlinear heat equation then their dependence upon T is obtained explicitly, whilst the unknown temperature T(x, t) is obtained implicitly and is then calculated numerically. Results are presented and discussed for infinite, semi-infinite and finite slabs. 相似文献
18.
R. D. Blyth 《Archiv der Mathematik》2002,78(5):337-344
Let n be an integer greater than 1, and let G be a group. A subset {x1, x2, ..., xn} of n elements of G is said to be rewritable if there are distinct permutations p \pi and s \sigma of {1, 2, ..., n} such that¶¶xp(1)xp(2) ?xp(n) = xs(1)xs(2) ?xs(n). x_{\pi(1)}x_{\pi(2)} \ldots x_{\pi(n)} = x_{\sigma(1)}x_{\sigma(2)} \ldots x_{\sigma(n)}. ¶¶A group is said to have the rewriting property Qn if every subset of n elements of the group is rewritable. In this paper we prove that a finite group of odd order has the property Q3 if and only if its derived subgroup has order not exceeding 5. 相似文献
19.
M. Zayed 《Archiv der Mathematik》2001,77(2):163-169
Let R be a right near-ring with identity and Mn(R) be the near-ring of n 2 n matrices over R in the sense of Meldrum and Van der Walt. In this paper, Mn(R) is said to be s\sigma-generated if every n 2 n matrix A over R can be expressed as a sum of elements of Xn(R), where
Xn(R)={fijr | 1\leqq i, j\leqq n, r ? R}X_n(R)=\{f_{ij}^r\,|\,1\leqq i, j\leqq n, r\in R\}, is the generating set of Mn(R). We say that R is s\sigma-generated if Mn(R) is s\sigma-generated for every natural number n. The class of s\sigma-generated near-rings contains distributively generated and abstract affine near-rings. It is shown that this class admits homomorphic images. For abelian near-rings R, we prove that the zerosymmetric part of R is a ring, so the class of zerosymmetric abelian s\sigma-generated near-rings coincides with the class of rings. Further, for every n, there is a bijection between the two-sided subgroups of R and those of Mn(R). 相似文献
20.
Let m and n be nonnegative integers. Denote by P(m,n) the set of all triangle-free graphs G such that for any independent m-subset M and any n-subset N of V(G) with M ∩ N = Ø, there exists a unique vertex of G that is adjacent to each vertex in M and nonadjacent to any vertex in N. We prove that if m ? 2 and n ? 1, then P(m,n) = Ø whenever m ? n, and P(m,n) = {Km,n+1} whenever m > n. We also have P(1,1) = {C5} and P(1,n) = Ø for n ? 2. In the degenerate cases, the class P(0,n) is completely determined, whereas the class P(m,0), which is most interesting, being rich in graphs, is partially determined. 相似文献