共查询到20条相似文献,搜索用时 9 毫秒
1.
2.
3.
Summary To date very few families of critical sets for latin squares are known. In this paper a new family of critical sets for back circulant latin squares is identified. The proof that each element of the critical set is an essential part of the reconstruction process relies on the proof of the existence of a large number of latin interchanges. 相似文献
4.
Rahul Mukerjee 《Discrete Mathematics》2008,308(20):4635-4642
A nested orthogonal array is an OA(N,k,s,g) which contains an OA(M,k,r,g) as a subarray. Here r<s and M<N. Necessary conditions for the existence of such arrays are obtained in the form of upper bounds on k, given N, M, s, r and g. Examples are given to show that these bounds are quite powerful in proving nonexistence. The link with incomplete orthogonal arrays is also indicated. 相似文献
5.
We (1) determine the number of Latin rectangles with 11 columns and each possible number of rows, including the Latin squares
of order 11, (2) answer some questions of Alter by showing that the number of reduced Latin squares of order n is divisible by f! where f is a particular integer close to
(3) provide a formula for the number of Latin squares in terms of permanents of (+1, −1)-matrices, (4) find the extremal
values for the number of 1-factorisations of k-regular bipartite graphs on 2n vertices whenever 1 ≤ k ≤ n ≤ 11, (5) show that the proportion of Latin squares with a non-trivial symmetry group tends quickly to zero as the order
increases.
Received September 3, 2004 相似文献
6.
A Room square of even side cannot exist. We study arrays of even side which very closely resemble Room squares. The spectrum is determined: the desired arrays exist for all even sides exceeding 4. These arrays are useful in a construction for Room squares containing subsquares. It is shown that, for alln4, and all oddr7 (exceptr=11), there is a Room square of sidenr +n – 1 which contains subsquares of sidesr and 2n – 1. 相似文献
7.
《Quaestiones Mathematicae》2013,36(7):953-975
AbstractEvery partial colouring of a Hamming graph is uniquely related to a partial Latin hyper-rectangle. In this paper we introduce the Θ-stabilized (a, b)-colouring game for Hamming graphs, a variant of the (a, b)-colouring game so that each move must respect a given autotopism Θ of the resulting partial Latin hyperrectangle. We examine the complexity of this variant by means of its chromatic number. We focus in particular on the bi-dimensional case, for which the game is played on the Cartesian product of two complete graphs, and also on the hypercube case. 相似文献
8.
Justin Z. Schroeder 《组合设计杂志》2019,27(1):42-52
We provide two new constructions for pairs of mutually orthogonal symmetric hamiltonian double Latin squares. The first is a tripling construction, and the second is derived from known constructions of hamilton cycle decompositions of when is prime. 相似文献
9.
10.
F.E. Bennett 《Discrete Mathematics》1981,36(2):117-137
Let L1 denote the set of integers n such that there exists an idempotent Latin square of order n with all of its conjugates distinct and pairwise orthogonal. It is known that L1 contains all sufficiently large integers. That is, there is a smallest integer no such that L1 contains all integers greater than no. However, no upper bound for no has been given and the term “sufficiently large” is unspecified. The main purpose of this paper is to establish a concrete upper bound for no. In particular it is shown that L1 contain all integers n>5594, with the possible exception of n=6810. 相似文献
11.
Mohammad Masjed-Jamei 《Journal of Computational and Applied Mathematics》2010,234(1):283-296
In a previous paper, we introduced a basic class of symmetric orthogonal functions (BCSOF) by an extended theorem for Sturm-Liouville problems with symmetric solutions. We showed that the foresaid class satisfies the differential equation
12.
Sven Hartmann 《Discrete Mathematics》2008,308(12):2502-2508
An orthogonal double cover (ODC) of the complete graph Kn by a graph G is a collection G of n spanning subgraphs of Kn, all isomorphic to G, such that any two members of G share exactly one edge and every edge of Kn is contained in exactly two members of G. In the 1980s Hering posed the problem to decide the existence of an ODC for the case that G is an almost-Hamiltonian cycle, i.e. a cycle of length n-1. It is known that the existence of an ODC of Kn by a Hamiltonian path implies the existence of ODCs of K4n and of K16n, respectively, by almost-Hamiltonian cycles. Horton and Nonay introduced two-colorable ODCs and showed: If there are an ODC of Kn by a Hamiltonian path for some n?3 and a two-colorable ODC of Kq by a Hamiltonian path for some prime power q?5, then there is an ODC of Kqn by a Hamiltonian path. In [U. Leck, A class of 2-colorable orthogonal double covers of complete graphs by hamiltonian paths, Graphs Combin. 18 (2002) 155-167], two-colorable ODCs of Kn and K2n, respectively, by Hamiltonian paths were constructed for all odd square numbers n?9. Here we continue this work and construct cyclic two-colorable ODCs of Kn and K2n, respectively, by Hamiltonian paths for all n of the form n=4k2+1 or n=(k2+1)/2 for some integer k. 相似文献
13.
《Journal of Combinatorial Theory, Series A》1987,46(2):314-318
We present some new conjugate orthogonal Latin squares which are obtained from a direct method of construction of the starter-adder type. Combining these new constructions with earlier results of K. T. Phelps and the first author, it is shown that a (3, 2, 1)- (or (1, 3, 2)-) conjugate orthogonal Latin square of order v exists for all positive integers v ≠ 2, 6. It is also shown that a (3, 2, 1)- (or (1, 3, 2)-) conjugate orthogonal idempotent Latin square of order v exists for all positive integers v ≠ 2, 3, 6 with one possible exception v = 12, and this result can be used to enlarge the spectrum of a certain class of Mendelsohn designs and provide better results for problems on embedding. 相似文献
14.
Since 1782, when Euler addressed the question of existence of a pair of orthogonal Latin squares (OLS) by stating his famous conjecture, these structures have remained an active area of research. In this paper, we examine the polyhedral aspects of OLS. In particular, we establish the dimension of the OLS polytope, describe all cliques of the underlying intersection graph and categorize them into three classes. Two of these classes are shown to induce facet-defining inequalities of Chvátal rank two. For each such class, we provide a polynomial separation algorithm of the lowest possible complexity. 相似文献
15.
《高校应用数学学报(A辑)》2015,(4)
研究了强对称自正交对角数独,引申了Lorch的构造方法,利用有限域上的线性空间理论给出了基本构造,证明了:对所有奇素数p,存在一个p2阶强对称自正交对角数独. 相似文献
16.
It is proved in this paper that every bipartite graphic sequence with the minimum degree 2 has a realization that admits a nowhere-zero 4-flow. This result implies a conjecture originally proposed by Keedwell (1993) and reproposed by Cameron (1999) about simultaneous edge-colorings and critical partial Latin squares.* Partially supported by RGC grant HKU7054/03P. Partially supported by the National Security Agency under Grants MDA904-00-1-00614 and MDA904-01-1-0022. 相似文献
17.
We say that a diagonal in an array is -balanced if each entry occurs times. Let be a frequency square of type ; that is, an array in which each entry from occurs times per row and times per column. We show that if , contains a -balanced diagonal, with only one exception up to equivalence when . We give partial results for
and suggest a generalization of Ryser’s conjecture, that every Latin square of odd order has a transversal. Our method relies on first identifying a small substructure with the frequency square that facilitates the task of locating a balanced diagonal in the entire array. 相似文献
18.
19.
Honglin Wu 《Linear algebra and its applications》2010,432(11):2909-2924
We study the 0-1 matrices whose squares are still 0-1 matrices and determine the maximal number of ones in such a matrix. The maximizing matrices are also specified. This solves a special case of a problem posed by Zhan. 相似文献
20.
We shall refer to a diagonal Latin square which is orthogonal to its (3, 2, 1)-conjugate and having its (3, 2, 1)-conjugate also a diagonal Latin square as a (3, 2, 1)-conjugate orthogonal diagonal Latin square, briefly CODLS. This article investigates the spectrum of CODLS and it is found that it contains all positive integers v except 2, 3, 6, and possibly 10. © 1997 John Wiley & Sons, Inc. J Combin Designs 5: 449–461, 1997 相似文献