共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
Houmem Belkhechine 《Discrete Mathematics》2017,340(12):2986-2994
Given a tournament , a module of is a subset of such that for and , if and only if . The trivial modules of are ,
and . The tournament is indecomposable if all its modules are trivial; otherwise it is decomposable. The decomposability index of , denoted by , is the smallest number of arcs of that must be reversed to make indecomposable. For , let be the maximum of over the tournaments with vertices. We prove that and that the lower bound is reached by the transitive tournaments. 相似文献
3.
4.
In this paper, is a finite chain ring with residue field and is a unit in By assuming that the multiplicative order of is coprime to we give the trace-representation of any simple-root -constacyclic code over of length and on the other hand show that any cyclic code over of length is a direct sum of trace-representable cyclic codes. Finally, we characterize the simple-root, contractable and cyclic codes over of length into -constacyclic codes of length 相似文献
5.
6.
A -coloring of a graph with colors is a proper coloring of using colors in which each color class contains a color dominating vertex, that is, a vertex which has a neighbor in each of the other color classes. The largest positive integer for which has a -coloring using colors is the -chromatic number of . The -spectrum of a graph is the set of positive integers , for which has a -coloring using colors. A graph is -continuous if = the closed interval . In this paper, we obtain an upper bound for the -chromatic number of some families of Kneser graphs. In addition we establish that for the Kneser graph whenever . We also establish the -continuity of some families of regular graphs which include the family of odd graphs. 相似文献
7.
8.
9.
A -way Latin trade of volume is a collection of partial Latin squares , containing exactly the same filled cells, such that, if cell is filled, it contains a different entry in each of the partial Latin squares, and such that row in each of the partial Latin squares contains, set-wise, the same symbols, and column likewise. It is called a -way-homogeneous Latin trade if, in each row and each column, , for , contains exactly elements, and each element appears in exactly times. It is also denoted as a Latin trade, where is the size of the partial Latin squares.We introduce some general constructions for -way -homogeneous Latin trades, and specifically show that, for all , , and , and for all , (except for four specific values), a -way -homogeneous Latin trade of volume exists. We also show that there is no Latin trade and there is no Latin trade. Finally, we present general results on the existence of -way -homogeneous Latin trades for some modulo classes of . 相似文献
10.
11.
12.
13.
14.
Vladimir N. Potapov 《Discrete Mathematics》2012,312(6):1269-1272
A coloring of a -ary -dimensional cube (hypercube) is called perfect if, for every -tuple , the collection of the colors of the neighbors of depends only on the color of . A Boolean-valued function is called correlation-immune of degree if it takes value the same number of times for each -dimensional face of the hypercube. Let be a characteristic function of a subset of hypercube. In the present paper we prove the inequality , where is the maximum degree of the correlation immunity of , is the average number of neighbors in the set for -tuples in the complement of a set , and is the density of the set . Moreover, the function is a perfect coloring if and only if we have an equality in the formula above. Also, we find a new lower bound for the cardinality of components of a perfect coloring and a 1-perfect code in the case . 相似文献
15.
The decycling number of a graph is the smallest number of vertices which can be removed from so that the resultant graph contains no cycle. A decycling set containing exactly vertices of is called a -set. For any decycling set of a -regular graph , we show that , where is the cycle rank of , is the margin number of , and are, respectively, the number of components of and the number of edges in . In particular, for any -set of a 3-regular graph , we prove that , where is the Betti deficiency of . This implies that the decycling number of a 3-regular graph is . Hence for a 3-regular upper-embeddable graph , which concludes the results in [Gao et al., 2015, Wei and Li, 2013] and solves two open problems posed by Bau and Beineke (2002). Considering an algorithm by Furst et al., (1988), there exists a polynomial time algorithm to compute , the cardinality of a maximum nonseparating independent set in a -regular graph , which solves an open problem raised by Speckenmeyer (1988). As for a 4-regular graph , we show that for any -set of , there exists a spanning tree of such that the elements of are simply the leaves of with at most two exceptions providing . On the other hand, if is a loopless graph on vertices with maximum degree at most , then The above two upper bounds are tight, and this makes an extension of a result due to Punnim (2006). 相似文献
16.
17.
18.
Denis S. Krotov 《Discrete Mathematics》2017,340(12):2723-2731
A subspace bitrade of type is a pair of two disjoint nonempty collections of -dimensional subspaces of a -dimensional space over the finite field of order such that every -dimensional subspace of is covered by the same number of subspaces from and . In a previous paper, the minimum cardinality of a subspace bitrade was established. We generalize that result by showing that for admissible , , and , the minimum cardinality of a subspace bitrade does not depend on . An example of a minimum bitrade is represented using generator matrices in the reduced echelon form. For , the uniqueness of a minimum bitrade is proved. 相似文献
19.