共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
《Discrete Mathematics》2023,346(1):113151
The Plurality problem - introduced by Aigner - has many variants. In this article we deal with the following version: suppose we are given n balls, each of them colored by one of three colors. A plurality ball is one such that its color class is strictly larger than any other color class. Questioner asks a triplet (or a k-set in general), and Adversary as an answer gives the partition of the triplet (or the k-set) into color classes. Questioner wants to find a plurality ball as soon as possible or show that there is no such ball, while Adversary wants to postpone this.We denote by the largest number of queries needed to ask in the worst case if both play optimally. We provide an almost precise result in the case of even n by proving that for even we have and for odd we haveWe also prove some bounds on the number of queries needed to ask in the case . 相似文献
3.
《Discrete Mathematics》2022,345(12):113082
Let G be a graph of order n with an edge-coloring c, and let denote the minimum color-degree of G. A subgraph F of G is called rainbow if all edges of F have pairwise distinct colors. There have been a lot of results on rainbow cycles of edge-colored graphs. In this paper, we show that (i) if , then every vertex of G is contained in a rainbow triangle; (ii) if and , then every vertex of G is contained in a rainbow ; (iii) if G is complete, and , then G contains a rainbow cycle of length at least k, where . 相似文献
4.
《Discrete Mathematics》2022,345(8):112902
For a simple graph G, denote by n, , and its order, maximum degree, and chromatic index, respectively. A graph G is edge-chromatic critical if and for every proper subgraph H of G. Let G be an n-vertex connected regular class 1 graph, and let be obtained from G by splitting one vertex of G into two vertices. Hilton and Zhao in 1997 conjectured that must be edge-chromatic critical if , and they verified this when . In this paper, we prove it for . 相似文献
5.
6.
《Discrete Mathematics》2022,345(4):112784
A set S of vertices in a graph G is a dominating set if every vertex not in S is adjacent to a vertex in S. If, in addition, every vertex in S is adjacent to some other vertex in S, then S is a total dominating set. The domination number of G is the minimum cardinality of a dominating set in G, while the total domination number of G is the minimum cardinality of total dominating set in G. A claw-free graph is a graph that does not contain as an induced subgraph. Let G be a connected, claw-free, cubic graph of order n. We show that if we exclude two graphs, then , and this bound is best possible. In order to prove this result, we prove that if we exclude four graphs, then , and this bound is best possible. These bounds improve previously best known results due to Favaron and Henning (2008) [7], Southey and Henning (2010) [19]. 相似文献
7.
8.
9.
10.
11.
12.
《Discrete Mathematics》2022,345(3):112731
Let be the matching number of a graph G. A characterization of the graphs with given maximum odd degree and smallest possible matching number is given by Henning and Shozi (2021) [13]. In this paper we complete our study by giving a characterization of the graphs with given maximum even degree and smallest possible matching number. In 2018 Henning and Yeo [10] proved that if G is a connected graph of order n, size m and maximum degree k where is even, then , unless G is k-regular and . In this paper, we give a complete characterization of the graphs that achieve equality in this bound when the maximum degree k is even, thereby completing our study of graphs with given maximum degree and smallest possible matching number. 相似文献
13.
14.
15.
16.
17.
18.
Compactness of sign-changing solutions to scalar curvature-type equations with bounded negative part
We consider the equation in a closed Riemannian manifold , where , and , . We obtain a sharp compactness result on the sets of sign-changing solutions whose negative part is a priori bounded. We obtain this result under the conditions that and in M, where is the Scalar curvature of the manifold. We show that these conditions are optimal by constructing examples of blowing-up solutions, with arbitrarily large energy, in the case of the round sphere with a constant potential function h. 相似文献
19.
20.
Let M be a random rank-r matrix over the binary field , and let be its Hamming weight, that is, the number of nonzero entries of M.We prove that, as with r fixed and tending to a constant, we have that converges in distribution to a standard normal random variable. 相似文献