共查询到20条相似文献，搜索用时 15 毫秒
1.
A subset A of a group G is sum-free if a + b does not belong to A for any a, b ∈ A. Asymptotics of the number of sum-free sets in groups of prime order are proved. 相似文献
2.
Galvin showed that for all fixed δ and sufficiently large n, the n‐vertex graph with minimum degree δ that admits the most independent sets is the complete bipartite graph . He conjectured that except perhaps for some small values of t, the same graph yields the maximum count of independent sets of size t for each possible t. Evidence for this conjecture was recently provided by Alexander, Cutler, and Mink, who showed that for all triples with , no n‐vertex bipartite graph with minimum degree δ admits more independent sets of size t than . Here, we make further progress. We show that for all triples with and , no n‐vertex graph with minimum degree δ admits more independent sets of size t than , and we obtain the same conclusion for and . Our proofs lead us naturally to the study of an interesting family of critical graphs, namely those of minimum degree δ whose minimum degree drops on deletion of an edge or a vertex. 相似文献
3.
Fred Galvin 《Journal of Graph Theory》2000,35(3):173-175
Entringer, Goddard, and Henning studied graphs in which every vertex belongs to both an (m + 1)‐clique and an independent (n + 1)‐set; they proved that there is such a graph of order p if and only if . We give an alternative and slightly easier proof of this fact, relating it to combinatorial matrix theory. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 173–175, 2000 相似文献
4.
Let Circ( r, n) be a circular graph. It is well known that its independence number α(Circ(r, n)) = r. In this paper we prove that α(Circ(r, n) × H ) = max{r|H |, nα(H )} for every vertex transitive graph H, and describe the structure of maximum independent sets in Circ(r, n) × H. As consequences, we prove α(G × H ) = max{α(G)|V (H )|, α(H )|V (G)|} for G being Kneser graphs, and the graphs defined by permutations and partial permutations, respectively. The structure of maximum independent sets in these direct products is also described. 相似文献
6.
7.
We construct measures with independent support whose Fourier coefficients decrease as fast as possible.
8.
1000多年前, 英国著名学者Alcuin曾提出过一个古老的渡河问题, 即狼、羊和卷心菜的渡河问题. 最近, Prisner和Csorba等考虑了一般``冲突图\"上的渡河问题. 将这一问题推广到超图$H=(V,mathcal{E})$,上, 考虑一类情况更一般的运输计划问题. 现在监管者 欲运输超图中的所有点,(代表``items\"),渡河, 这里$V$的点子 形成超边 当且仅当这些点代表的``items\"在无人监管的情况下不能留在一起. 超图$H$的Alcuin数是指超图$H$具有可行运输方案,(即把$V$的点代表的``items\" 全部运到河对岸),时船的最小容量. 给出了 $r$-一致完全二部超图和它的伴随超图, 以及$r$-一致超图的Alcuin数, 同时证明了判断$r$-一致超图是否为小船图是NP 困难的. 相似文献
9.
Attainable estimates of the number of independent sets in graphs with a given size of the maximal independent set are obtained. Three graph classes—trees, forests, and the class of all graphs—are considered. Extremal graphs are described. 相似文献
10.
Carlos A. Coelho 《Journal of multivariate analysis》1999,69(2):281
A brief remark on the paper “The Generalized Integer Gamma Distribution— A Basis for Distributions in Multivariate Statistics,” (1998,J. Multivariate Anal.64, 86–102) and an additional result concerning the distribution of the product of some particular independent beta random variables, which broadens the scope of the results in that paper, are presented. 相似文献
11.
指出了软代数现行表示的非自然性;通过引入新的集对F格与伪幂集格,获得了两个自然的软代数表示定理,并证明了它们在某种意义上不可能再改进. 相似文献
12.
Kazuhide Hirohata 《Journal of Graph Theory》1998,29(3):177-184
For a graph G and an integer k ≥ 1, let ςk(G) = dG(vi): {v1, …, vk} is an independent set of vertices in G}. Enomoto proved the following theorem. Let s ≥ 1 and let G be a (s + 2)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, ς2(G) − s} passing through any path of length s. We generalize this result as follows. Let k ≥ 3 and s ≥ 1 and let G be a (k + s − 1)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, − s} passing through any path of length s. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 177–184, 1998 相似文献
13.
Angsuman Das 《Linear and Multilinear Algebra》2017,65(6):1276-1287
In this paper, we introduce a graph structure, called non-zero component union graph on finite-dimensional vector spaces. We show that the graph is connected and find its domination number, clique number and chromatic number. It is shown that two non-zero component union graphs are isomorphic if and only if the base vector spaces are isomorphic. In case of finite fields, we study the edge-connectivity and condition under which the graph is Eulerian. Moreover, we provide a lower bound for the independence number of the graph. Finally, we come up with a structural characterization of non-zero component union graph. 相似文献
14.
Vadim V. Lozin 《Discrete Mathematics》2006,306(22):2901-2908
We study two central problems of algorithmic graph theory: finding maximum and minimum maximal independent sets. Both problems are known to be NP-hard in general. Moreover, they remain NP-hard in many special classes of graphs. For instance, the problem of finding minimum maximal independent sets has been recently proven to be NP-hard in the class of so-called (1,2)-polar graphs. On the other hand, both problems can be solved in polynomial time for (1,1)-polar, also known as split graphs. In this paper, we address the question of distinguishing new classes of graphs admitting polynomial-time solutions for the two problems in question. To this end, we extend the hierarchy of (α,β)-polar graphs and study the computational complexity of the problems on polar graphs of special types. 相似文献
15.
16.
17.
A method that utilizes the polynomially solvable critical independent set problem for solving the maximum independent set problem on graphs with a nonempty critical independent set is developed. The effectiveness of the proposed approach on large graphs with large independence number is demonstrated through extensive numerical experiments. 相似文献
18.
六角系统是理论化学中苯碳氢化合物的自然图表示．六角链是一个六角系统满足任意一个顶点至多属于两个六角形,并且每个六角形至多与两个六角形相邻．Gutman提出了两个猜想：1）含有相同六角形个数、具有点独立集总数（Hosoya指数）最小的六角链是唯一的,且为锯齿链;2）含有相同六角形个数、具有边独立集总数（Merrifield－Simmons指数）最大的六角链是唯一的且为锯齿链．本文证实了这两个猜想 相似文献
19.
Hisao Kato 《Proceedings of the American Mathematical Society》1998,126(7):2151-2157
The measure of scrambled sets of interval self-maps was studied by many authors, including Smítal, Misiurewicz, Bruckner and Hu, and Xiong and Yang. In this note, first we introduce the notion of ``-chaos" which is related to chaos in the sense of Li-Yorke, and we prove a general theorem which is an improvement of a theorem of Kuratowski on independent sets. Second, we apply the result to scrambled sets of higher dimensional cases. In particular, we show that if a map of the unit -cube is -chaotic on , then for any there is a map such that and are topologically conjugate, and has a scrambled set which has Lebesgue measure 1, and hence if , then there is a homeomorphism with a scrambled set satisfying that is an -set in and has Lebesgue measure 1.
20.