共查询到20条相似文献,搜索用时 15 毫秒
1.
Andreas Klein 《Discrete Mathematics》2007,307(22):2695-2703
We prove for a large class of parameters t and r that a multiset of at most tθd-k+rθd-k-2 points in PG(d,q) that blocks every k-dimensional subspace at least t times must contain a sum of t subspaces of codimension k.We use our results to identify a class of parameters for linear codes for which the Griesmer bound is not sharp. Our theorem generalizes the non-existence results from Maruta [On the achievement of the Griesmer bound, Des. Codes Cryptogr. 12 (1997) 83-87] and Klein [On codes meeting the Griesmer bound, Discrete Math. 274 (2004) 289-297]. 相似文献
2.
D. F. Holt 《Journal of Graph Theory》1981,5(2):201-204
A graph having 27 vertices is described, whose automorphism group is transitive on vertices and undirected edges, but not on directed edges. 相似文献
3.
There exists a path-connected subspace of the plane for which graph embeddability is undecidable. 相似文献
4.
5.
6.
Juhani Nieminen 《manuscripta mathematica》1972,7(4):331-340
Let G be a finite, connected, undirected graph without loops and multiple edges. The note modifies slightly the concept of I–1 (Tt), the inverse interchange graph of the local graph G(Tt) defined by a reference tree t G, and considers the properties of the graph G, when I–1(Tt) is a tree. 相似文献
7.
Nathan Linial 《Discrete Mathematics》1976,15(3):297-300
Let G=(V, E) be a block of order n, different from Kn. Let m=min {d(x)+d(y): [x, y]?E}. We show that if m?n then G contains a cycle of length at least m. 相似文献
8.
《European Journal of Operational Research》1996,92(1):211-213
We consider the completion time variance problem. Our main result is a tight lower bound for the mean completion time of an optimal sequence. This result can be applied to reduce the time required to solve the problem. 相似文献
9.
We study the degrees of unsolvability of sets which are cohesive (or have weaker recursion-theoretic “smallness” properties). We answer a question raised by the first author in 1972 by showing that there is a cohesive set A whose degree a satisfies a' = 0″ and hence is not high. We characterize the jumps of the degrees of r-cohesive sets, and we show that the degrees of r-cohesive sets coincide with those of the cohesive sets. We obtain analogous results for strongly hyperimmune and strongly hyperhyperimmune sets in place of r-cohesive and cohesive sets, respectively. We show that every strongly hyperimmune set whose degree contains either a Boolean combination of ∑2 sets or a 1-generic set is of high degree. We also study primitive recursive analogues of these notions and in this case we characterize the corresponding degrees exactly. MSC: 03D30, 03D55. 相似文献
10.
Nicholas Krier 《Archiv der Mathematik》1977,28(1):323-324
11.
Roberto D. Galvão 《European Journal of Operational Research》1981,6(2):162-165
The p-median problem is a minisium network location problem that seeks to find the optimal location of p centres in a network. In the present paper a graph-theoretical bound is developed for the problem. This bound is based on shortest spanning trees and arborescences and other graphical properties of the problem. It is shown that the graph-theoretical bound dominates a bound based on shortest distances. 相似文献
12.
Christoph Maas 《Journal of Computational and Applied Mathematics》1984,10(1):65-69
The interval number i(G) of a graph G with n vertices is the lowest integer m such that G is the intersection graph of some family of sets I1,…,In with every Ii being the union of at most m real intervals. In this article a lower bound for i(G) is proved followed by some considerations about the construction of graphs that are critical with respect to the interval number. 相似文献
13.
14.
James H. Schmerl 《Archive for Mathematical Logic》1993,32(6):463-468
Summary For each completion of Peano Arithmetic there is a weakly definable type which is not definable. 相似文献
15.
J.L. Alperin 《代数通讯》2013,41(2):131-136
16.
Wieslaw Kubis Vladimir Uspenskij 《Proceedings of the American Mathematical Society》2005,133(8):2483-2487
A compact space is Valdivia compact if it can be embedded in a Tikhonov cube in such a way that the intersection is dense in , where is the sigma-product ( the set of points with countably many non-zero coordinates). We show that there exists a compact connected Abelian group of weight which is not Valdivia compact, and deduce that Valdivia compact spaces are not preserved by open maps.
17.
A. Ivanov 《Siberian Advances in Mathematics》2010,20(2):75-82
We give an example of a countably categorical theory which is not G-compact. The countable model of this theory does not have AZ-enumerations. 相似文献
18.
Michael O Albertson 《Journal of Combinatorial Theory, Series B》1976,20(1):84-93
A subset of the vertices of a graph is independent if no two vertices in the subset are adjacent. The independence number α(G) is the maximum number of vertices in an independent set. We prove that if G is a planar graph on N vertices then . 相似文献
19.
20.
Paul A. Catlin 《Discrete Mathematics》1978,22(1):81-83
We give an upper bound on the chromatic number of a graph in terms of its maximum degree and the size of the largest complete subgraph. Our results extends a theorem due to Brooks. 相似文献