首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 421 毫秒
1.
Associated to any simplicial complex Δ on n vertices is a square-free monomial ideal IΔ in the polynomial ring A = k[x1, …, xn], and its quotient k[Δ] = A/IΔ known as the Stanley-Reisner ring. This note considers a simplicial complex Δ* which is in a sense a canonical Alexander dual to Δ, previously considered in [1, 5]. Using Alexander duality and a result of Hochster computing the Betti numbers dimk ToriA (k[Δ],k), it is shown (Proposition 1) that these Betti numbers are computable from the homology of links of faces in Δ*. As corollaries, we prove that IΔ has a linear resolution as A-module if and only if Δ* is Cohen-Macaulay over k, and show how to compute the Betti numbers dimk ToriA (k[Δ],k) in some cases where Δ* is wellbehaved (shellable, Cohen-Macaulay, or Buchsbaum). Some other applications of the notion of shellability are also discussed.  相似文献   

2.
It is shown in this paper that the weighted domination problem and its three variants, the weighted connected domination, total domination, and dominating clique problems are NP-complete on cobipartite graphs when arbitrary integer vertex weights are allowed and all of them can be solved in polynomial time on cocomparability graphs if vertex weights are integers and less than or equal to a constant c. The results are interesting because cocomparability graphs properly contain cobipartite graphs and the cardinality cases of the above problems are trivial on cobipartite graphs. On the other hand, an O(¦V¦2) algorithm is given for the weighted independent perfect domination problem of a cocomparability graph G = (V.E).  相似文献   

3.
A graph G with n vertices is said to be embeddable (in its complement) if there is an automorphism φ of Kn such that E(G) ∩ E(φ(G))=. It is known that all trees T with n (≥2) vertices and T K1,n−1 are embeddable. We say that G is 1-embeddable if, for every edge e, there is an automorphism φ of Kn such that E(G) ∩ E(φ(G))={e};and that it is 2-embeddable if,for every pair e1, e2 of edges, there is an automorphism φ of Kn such that E(G) ∩ E(φ(G))={e1, e2}. We prove here that all trees with n (3) vertices are 1-embeddable; and that all trees T with n (4) vertices and T K1,n−1 are 2-embeddable. In a certain sense, this result is sharp.  相似文献   

4.
The ℓ2-invariants of the fundamental group G of a graph of groups acting on a CW-complex X are related to the ℓ2-invariants of the edge and vertex groups of G acting on X. Various consequences are derived.  相似文献   

5.
A standard model for radio channel assignment involves a set V of sites, the set {0,1,2,…} of channels, and a constraint matrix (w(u, v)) specifying minimum channel separations. An assignment f:V→{0,1,2,…} is feasible if the distance f(u) − f(v)w(u, v) for each pair of sites u and v. The aim is to find the least k such that there is a feasible assignment using only the k channels 0, 1, …, k − 1, and to find a corresponding optimal assignment.

We consider here a related problem involving also two cycles. There is a given cyclic order τ on the sites, and feasible assignments f must also satisfy fv) f(v) for all except one site v. Further, the channels are taken to be evenly spaced around a circle, so that if the k channels 0, 1, …, k − 1 are available then the distance between channels i and j is the minimum of ¦ij¦ and k − ¦ij¦. We show how to find a corresponding optimal channel assignment in O(¦V¦3) steps.  相似文献   


6.
Harary's conjectures on integral sum graphs   总被引:6,自引:0,他引:6  
Zhibo Chen 《Discrete Mathematics》1996,160(1-3):241-244
Let N denote the set of positive integers and Z denote all integers. The (integral) sum graph of a finite subset S N(Z) is the graph (S, E) with uv ε E if and only if u + v ε S. A graph G is said to be an (integral) sum graph if it is isomorphic to the (integral) sum graph of some S N(Z). The (integral) sum number of a given graph G is the smallest number of isolated nodes which when added to G result in an (integral) sum graph.

We show that the integral sum number of a complete graph with n 4 nodes equals 2n − 3, which proves a conjecture of Harary. And we disprove another conjecture of Harary by showing that there are infinitely many trees which are not caterpillars but are integral sum graphs.  相似文献   


7.
Given graph G=(V,E) on n vertices, the profile minimization problem is to find a one-to-one function f:V→{1,2,…,n} such that ∑vV(G){f(v)−minxN[v] f(x)} is as small as possible, where N[v]={v}{x: x is adjacent to v} is the closed neighborhood of v in G. The trangulated triangle Tl is the graph whose vertices are the triples of non-negative integers summing to l, with an edge connecting two triples if they agree in one coordinate and differ by 1 in the other two coordinates. This paper provides a polynomial time algorithm to solve the profile minimization problem for trangulated triangles Tl with side-length l.  相似文献   

8.
We consider a generalized version of the Steiner problem in graphs, motivated by the wire routing phase in physical VLSI design: given a connected, undirected distance graph with required classes of vertices and Steiner vertices, find a shortest connected subgraph containing at least one vertex of each required class. We show that this problem is NP-hard, even if there are no Steiner vertices and the graph is a tree. Moreover, the same complexity result holds if the input class Steiner graph additionally is embedded in a unit grid, if each vertex has degree at most three, and each class consists of no more than three vertices. For similar restricted versions, we prove MAX SNP-hardness and we show that there exists no polynomial-time approximation algorithm with a constant bound on the relative error, unless P = NP. We propose two efficient heuristics computing different approximate solutions in time OE¦+¦V¦log¦V¦) and in time O(cE¦+¦V¦log¦V¦)), respectively, where E is the set of edges in the given graph, V is the set of vertices, and c is the number of classes. We present some promising implementation results. kw]Steiner Tree; Heuristic; Approximation complexity; MAX-SNP-hardness  相似文献   

9.
Let q*(G) denote the minimum integer t for which E(G) can be partitioned into t induced matchings of G. Faudree et al. conjectured that q*(G)d2, if G is a bipartite graph and d is the maximum degree of G. In this note, we give an affirmative answer for d=3, the first nontrivial case of this conjecture.  相似文献   

10.
Let q be a nonnegative real number, and λ and σ be positive constants. This article studies the following impulsive problem: for n = 1, 2, 3,…,
. The number λ* is called the critical value if the problem has a unique global solution u for λ < λ*, and the solution blows up in a finite time for λ > λ*. For σ < 1, existence of a unique λ* is established, and a criterion for the solution to decay to zero is studied. For σ > 1, existence of a unique λ* and three criteria for the blow-up of the solution in a finite time are given respectively. It is also shown that there exists a unique T* such that u exists globally for T> T*, and u blows up in a finite time for T < T*.  相似文献   

11.
12.
Jianxiang Li   《Discrete Mathematics》2003,260(1-3):217-221
Let G be a graph of order n, and let a and b be integers such that 1a<b. Let δ(G) be the minimum degree of G. Then we prove that if δ(G)(k−1)a, n(a+b)(k(a+b)−2)/b, and |NG(x1)NG(x2)NG(xk)|an/(a+b) for any independent subset {x1,x2,…,xk} of V(G), where k2, then G has an [a,b]-factor. This result is best possible in some sense.  相似文献   

13.
In this paper, we provide a solution of the quadrature sum problem of R. Askey for a class of Freud weights. Let r> 0, b (− ∞, 2]. We establish a full quadrature sum estimate
1 p < ∞, for every polynomial P of degree at most n + rn1/3, where W2 is a Freud weight such as exp(−¦x¦), > 1, λjn are the Christoffel numbers, xjn are the zeros of the orthonormal polynomials for the weight W2, and C is independent of n and P. We also prove a generalisation, and that such an estimate is not possible for polynomials P of degree M = m(n) if m(n) = n + ξnn1/3, where ξn → ∞ as n → ∞. Previous estimates could sum only over those xjn with ¦xjn¦ σx1n, some fixed 0 < σ < 1.  相似文献   

14.
In a recent paper, D.J. Kleitman and M.E. Saks gave a proof of Huang's conjecture on alphabetic binary trees.

Given a set E = {ei}, I = 0, 1, 2, …, m and assigned positive weights to its elements and supposing the elements are indexed such that w(e0) ≤ w(e1) ≤ … ≤w (em), where w(ei) is the weight of ei, we call the following sequence E* a ‘saw-tooth’ sequence

E*=(e0,em,e1,…,ej,emj,…).

Huang's conjecture is: E* is the most expensive sequence for alphabetic binary trees. This paper shows that this property is true for the L-restricted alphabetic binary trees, where L is the maximum length of the leaves and log2(m + 1) ≤Lm.  相似文献   


15.
The chromatic difference sequence cds(G) of a graph G with chromatic number n is defined by cds(G) = (a(1), a(2),…, a(n)) if the sum of a(1), a(2),…, a(t) is the maximum number of vertices in an induced t-colorable subgraph of G for t = 1, 2,…, n. The Cartesian product of two graphs G and H, denoted by GH, has the vertex set V(GH = V(G) x V(H) and its edge set is given by (x1, y1)(x2, y2) ε E(GH) if either x1 = x2 and y1 y2 ε E(H) or y1 = y2 and x1x2 ε E(G).

We obtained four main results: the cds of the product of bipartite graphs, the cds of the product of graphs with cds being nondrop flat and first-drop flat, the non-increasing theorem for powers of graphs and cds of powers of circulant graphs.  相似文献   


16.
C-normality and solvability of groups   总被引:6,自引:0,他引:6  
A subgroup H is called c-normal in group G if there exists a normal subgroup N and G such that HN = G and HNHG where HG =: Core(H) = gG Hg is the maximal normal subgroup of G which is contained in H. We obtain some results about the c-normal subgroups and the solvability of groups.  相似文献   

17.
Xuding Zhu 《Discrete Mathematics》1998,190(1-3):215-222
Suppose G is a graph. The chromatic Ramsey number rc(G) of G is the least integer m such that there exists a graph F of chromatic number m for which the following is true: for any 2-colouring of the edges of F there is a monochromatic subgraph isomorphic to G. Let Mn = min[rc(G): χ(G) = n]. It was conjectured by Burr et al. (1976) that Mn = (n − 1)2 + 1. This conjecture has been confirmed previously for n 4. In this paper, we shall prove that the conjecture is true for n = 5. We shall also improve the upper bounds for M6 and M7.  相似文献   

18.
Let H be a graph with κ1 components and κ2 blocks, and let G be a minor-minimal 2-connected graph having H as a minor. This paper proves that |E(G)|−|E(H)|(κ1−1)+β(κ2−1) for all (,β) such that +β5,2+5β20, and β3. Moreover, if one of the last three inequalities fails, then there are graphs G and H for which the first inequality fails.  相似文献   

19.
Given a graph G = (V,E) and R, we write w(G)=∑xyεEdG(x)dG(y), and study the function w(m) = max {w(G): e(G) = m}. Answering a question from Bollobás and Erdös (Graphs of external weights, to appear), we determine wi(m) for every m, and we also give bounds for the case ≠ 1.  相似文献   

20.
Every graph can be represented as the intersection graph on a family of closed unit cubes in Euclidean space En. Cube vertices have integer coordinates. The coordinate matrix, A(G)={vnk} of a graph G is defined by the set of cube coordinates. The imbedded dimension of a graph, Bp(G), is a number of columns in matrix A(G) such that each of them has at least two distinct elements vnkvpk. We show that Bp(G)=cub(G) for some graphs, and Bp(G)n−2 for any graph G on n vertices. The coordinate matrix uses to obtain the graph U of radius 1 with 3n−2 vertices that contains as an induced subgraph a copy of any graph on n vertices.  相似文献   

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

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