共查询到20条相似文献,搜索用时 15 毫秒
1.
The k-subset sum problem over finite fields is a classical NP-complete problem. Motivated by coding theory applications, a more complex problem is the higher m-th moment k-subset sum problem over finite fields. We show that there is a deterministic polynomial time algorithm for the m-th moment k-subset sum problem over finite fields for each fixed m when the evaluation set is the image set of a monomial or Dickson polynomial of any degree n. In the classical case , this recovers previous results of Nguyen-Wang (the case ) [22] and the results of Choe-Choe (the case ) [3]. 相似文献
2.
Let and be positive integers. We determine the maximum size of digraphs of order that avoid distinct walks of length with the same endpoints. We also characterize the extremal digraphs attaining this maximum number when . 相似文献
3.
4.
In 2009, Kyaw proved that every -vertex connected -free graph with contains a spanning tree with at most 3 leaves. In this paper, we prove an analogue of Kyaw’s result for connected -free graphs. We show that every -vertex connected -free graph with contains a spanning tree with at most 4 leaves. Moreover, the degree sum condition “” is best possible. 相似文献
5.
《Discrete Mathematics》2022,345(8):112904
Let be the minimum integer such that every plane graph with girth g at least , minimum degree and no -paths consisting of vertices of degree 2, where , has a 3-vertex with at least t neighbors of degree 2, where .In 2015, Jendrol' and Maceková proved . Later on, Hudák et al. established , Jendrol', Maceková, Montassier, and Soták proved , and , and we recently proved that and .Thus is already known for and all t. In this paper, we prove that , , and whenever . 相似文献
6.
We characterize all finite metabelian 2-groups G whose abelianizations are of type , with , and for which their commutator subgroups have . This is given in terms of the order of the abelianizations of the maximal subgroups and the structure of the abelianizations of those normal subgroups of index 4 in G. We then translate these group theoretic properties to give a characterization of number fields k with 2-class group , , such that the rank of where is the Hilbert 2-class field of k. In particular, we apply all this to real quadratic number fields whose discriminants are a sum of two squares. 相似文献
7.
8.
9.
《Discrete Mathematics》2022,345(11):113029
Let G be a k-connected graph on n vertices. Hippchen's Conjecture (2008) states that two longest paths in G share at least k vertices. Gutiérrez (2020) recently proved the conjecture when or . We improve upon both results; namely, we show that two longest paths in G share at least k vertices when or . This completely resolves two conjectures by Gutiérrez in the affirmative. 相似文献
10.
11.
12.
13.
15.
16.
17.
18.
Hiroshi Nozaki 《Discrete Mathematics》2019,342(7):2134-2138
We deal with connected -regular multigraphs of order that has only three distinct eigenvalues. In this paper, we study the largest possible number of vertices of such a graph for given . For , the Moore graphs are largest. For , we show an upper bound , with equality if and only if there exists a finite projective plane of order that admits a polarity. 相似文献
19.
We construct orthogonal arrays (of strength two) having a row that is repeated times, where is as large as possible. In particular, we consider OAs where the ratio is as large as possible; these OAs are termed optimal. We provide constructions of optimal OAs for any , albeit with large . We also study basic OAs; these are optimal OAs in which . We construct a basic OA with and , provided that a Hadamard matrix of order exists. This completely solves the problem of constructing basic OAs with , modulo the Hadamard matrix conjecture. 相似文献
20.
In this paper, based on the structure of embedded fields, we investigate explicit construction of systematic mMDS sliding window codes with memory . First, over GF() with and , we propose an algorithm to construct mMDS codes with memory 2, which are optimal in the sense that is the maximum possible value of k for a sliding window code with memory 2 over GF() to be mMDS. When , every constructed code has the extra property that it contains a mMDS sliding window code with memory 2 as a subcode over the subfield GF(). Next, over GF() with and , we introduce a method to construct mMDS codes memory 3, and a few new codes have been obtained consequently. When , every code constructed by the new approach also has the property that it contains an mMDS subcode over the subfield GF(). The embedding subfield-subcode property enhances the flexibility and efficiency of the designed codes. 相似文献