共查询到20条相似文献,搜索用时 609 毫秒
1.
Kreweras conjectured that every perfect matching of a hypercube for can be extended to a hamiltonian cycle of . Fink confirmed the conjecture to be true. It is more general to ask whether every perfect matching of for can be extended to two or more hamiltonian cycles of . In this paper, we prove that every perfect matching of for can be extended to at least different hamiltonian cycles of . 相似文献
2.
Qichun Wang 《Discrete Mathematics》2019,342(12):111625
It was proved by J. Schatz that the covering radius of the second order Reed–Muller code is 18 (Schatz (1981)). However, the covering radius of has been an open problem for many years. In this paper, we prove that the covering radius of is 40, which is the same as the covering radius of in . As a corollary, we also find new upper bounds for the covering radius of , . 相似文献
3.
We give exact growth rates for the number of bipartite graceful permutations of the symbols that start with for (equivalently, -labelings of paths with vertices that have as a pendant label). In particular, when the growth is asymptotically like for . The number of graceful permutations of length grows at least this fast, improving on the best existing asymptotic lower bound of . Combined with existing theory, this improves the known lower bounds on the number of Hamiltonian decompositions of the complete graph and on the number of cyclic oriented triangular embeddings of and . We also give the first exponential lower bound on the number of R-sequencings of . 相似文献
4.
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. 相似文献
5.
A matching in a 3-uniform hypergraph is a set of pairwise disjoint edges. We use to denote the 3-uniform hypergraph whose vertex set can be partitioned into two vertex classes and of size and , respectively, and whose edge set consists of all the triples containing at least two vertices of . Let be a 3-uniform hypergraph of order with no isolated vertex and for any two adjacent vertices . In this paper, we show that contains a matching of size if and only if is not a subgraph of . This result improves our previous one in Zhang and Lu (2018). 相似文献
6.
7.
Natalie C. Behague 《Discrete Mathematics》2019,342(6):1696-1702
8.
9.
10.
《Discrete Mathematics》2019,342(5):1275-1292
A discrete function of variables is a mapping , where , and are arbitrary finite sets. Function is called separable if there exist functions for , such that for every input the function takes one of the values . Given a discrete function , it is an interesting problem to ask whether is separable or not. Although this seems to be a very basic problem concerning discrete functions, the complexity of recognition of separable discrete functions of variables is known only for . In this paper we will show that a slightly more general recognition problem, when is not fully but only partially defined, is NP-complete for . We will then use this result to show that the recognition of fully defined separable discrete functions is NP-complete for .The general recognition problem contains the above mentioned special case for . This case is well-studied in the context of game theory, where (separable) discrete functions of variables are referred to as (assignable) -person game forms. There is a known sufficient condition for assignability (separability) of two-person game forms (discrete functions of two variables) called (weak) total tightness of a game form. This property can be tested in polynomial time, and can be easily generalized both to higher dimension and to partially defined functions. We will prove in this paper that weak total tightness implies separability for (partially defined) discrete functions of variables for any , thus generalizing the above result known for . Our proof is constructive. Using a graph-based discrete algorithm we show how for a given weakly totally tight (partially defined) discrete function of variables one can construct separating functions in polynomial time with respect to the size of the input function. 相似文献
11.
The distinguishing number of a group acting on a finite set , denoted by , is the least such that there is a -coloring of which is preserved only by elements of fixing all points in . For a map , also called a cellular graph embedding or ribbon graph, the action of on the vertex set gives the distinguishing number . It is known that whenever . The action of on the edge set gives the distinguishing index , which has not been studied before. It is shown that the only maps with are the following: the tetrahedron; the maps in the sphere with underlying graphs , or for ; a map in the projective plane with underlying graph ; two one-vertex maps with 4 or 5 edges; one two-vertex map with 4 edges; or any map obtained from these maps using duality or Petrie duality. There are 39 maps in all. 相似文献
12.
We show that every -tight set of a Hermitian polar spaces , , is the union of disjoint generators of the polar space provided that . This was known before only when . This result is a contribution to the conjecture that the smallest -tight set of that is not a union of disjoint generators occurs for and is for sufficiently large an embedded subgeometry. 相似文献
13.
《Discrete Mathematics》2019,342(5):1351-1360
We study functions defined on the vertices of the Hamming graphs . The adjacency matrix of has distinct eigenvalues with corresponding eigenspaces for . In this work, we consider the problem of finding the minimum possible support (the number of nonzeros) of functions belonging to a direct sum for . For the case and we find the minimum cardinality of the support of such functions and obtain a characterization of functions with the minimum cardinality of the support. In the case and we also find the minimum cardinality of the support of functions, and obtain a characterization of functions with the minimum cardinality of the support for , and . In particular, we characterize eigenfunctions from the eigenspace with the minimum cardinality of the support for cases , and , . 相似文献
14.
In the papers (Benoumhani 1996;1997), Benoumhani defined two polynomials and . Then, he defined and to be the polynomials satisfying and . In this paper, we give a combinatorial interpretation of the coefficients of and prove a symmetry of the coefficients, i.e., . We give a combinatorial interpretation of and prove that is a polynomial in with non-negative integer coefficients. We also prove that if then all coefficients of except the coefficient of are non-negative integers. For all , the coefficient of in is , and when some other coefficients of are also negative. 相似文献
15.
Julia Semikina 《Journal of Pure and Applied Algebra》2019,223(10):4509-4523
I. Hambleton, L. Taylor and B. Williams conjectured a general formula in the spirit of H. Lenstra for the decomposition of for any finite group G and noetherian ring R. The conjectured decomposition was shown to hold for some large classes of finite groups. D. Webb and D. Yao discovered that the conjecture failed for the symmetric group , but remarked that it still might be reasonable to expect the HTW-decomposition for solvable groups. In this paper we show that the solvable group is also a counterexample to the conjectured HTW-decomposition. Nevertheless, we prove that for any finite group G the rank of does not exceed the rank of the expression in the HTW-decomposition. We also show that the HTW-decomposition predicts correct torsion for for any finite group G. Furthermore, we prove that for any degree other than the conjecture gives a correct prediction for the rank of . 相似文献
16.
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. 相似文献
17.
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. 相似文献
18.
In 1996, Cox and Rodger [Cycle systems of the line graph of the complete graph, J. Graph Theory 21 (1996) 173–182] raised the following question: For what values of and does there exist an -cycle decomposition of In this paper, the above question is answered for In fact, it is shown that the -fold line graph of the complete graph has a -decomposition if and only if and 相似文献
19.
Brualdi and Hollingsworth conjectured in Brualdi and Hollingsworth (1996) that in any complete graph , , which is properly colored with colors, the edge set can be partitioned into edge disjoint rainbow spanning trees (where a graph is said to be rainbow if its edges have distinct colors). Constantine (2002) strengthened this conjecture asking the rainbow spanning trees to be pairwise isomorphic. He also showed an example satisfying his conjecture for every . Caughmann, Krussel and Mahoney (2017) recently showed a first infinite family of edge colorings for which the conjecture of Brualdi and Hollingsworth can be verified. In the present paper, we extend this result to all edge-colorings arising from cyclic 1-factorizations of constructed by Hartman and Rosa (1985). Finally, we remark that our constructions permit to extend Constatine’s result also to all . 相似文献
20.
《Discrete Mathematics》2020,343(10):111996
A Gallai coloring of a complete graph is an edge coloring without triangles colored with three different colors. A sequence of positive integers is an -sequence if . An -sequence is a G-sequence if there is a Gallai coloring of with colors such that there are edges of color for all . Gyárfás, Pálvölgyi, Patkós and Wales proved that for any integer there exists an integer such that every -sequence is a G-sequence if and only if . They showed that and .We show that and give almost matching lower and upper bounds for by showing that with suitable constants , for all sufficiently large . 相似文献