共查询到20条相似文献,搜索用时 494 毫秒
1.
The incidence matrix of a (υ, k, λ)-design is a (0, 1)-matrix A of order υ that satisfies the matrix equation AAT=(k?λ)I+λJ, where AT denotes the transpose of the matrix A, I is the identity matrix of order υ, J is the matrix of 1's of order υ, and υ, k, λ are integers such that 0<λ<k<υ?1. This matrix equation along with various modifications and generalizations has been extensively studied over many years. The theory presents an intriguing joining together of combinatorics, number theory, and matrix theory. We survey a portion of the recent literature. We discuss such varied topics as integral solutions, completion theorems, and λ-designs. We also discuss related topics such as Hadamard matrices and finite projective planes. Throughout the discussion we mention a number of basic problems that remain unsolved. 相似文献
2.
Let qυ=υ(υ–1)(υ–2)/24 and let Iυ={0, 1, 2, …, qυ–14}∪{qυ–12, qυ–8, qυ}, for υ?8 Further, let J[υ] denote the set of all k such that there exists a pair of Steiner quadruple systems of order υ having exactly k blocks in common. We determine J[υ] for all υ=2n, n?2, with the possible exception of 7 cases for υ=16 and of 5 cases for each υ?32. In particular we show: J[υ]?Iυ for all υ≡2 or 4 (mod 6) and υ?8, J[4]={1}, J[8]=I8={0, 2, 6, 14}, I16?{103, 111, 115, 119, 121, 122, 123}?J[16], and Iυ? {qυ–h:h=17, 18, 19, 21, 25}?J[υ] for all υ=2n, n?5. 相似文献
3.
Say that graph G is partitionable if there exist integers α?2, ω? 2, such that |V(G)| ≡ αω + 1 and for every υ?V(G) there exist partitions of V(G)\ υ into stable sets of size α and into eliques of size ω. An immediate consequence of Lovász' characterization of perfect graphs is that every minimal imperfect graph G is partitionable with α ≡ α (G) andω ≡ ω(G).Padberg has shown that in every minimal imperfect graph G the cliques and stable sets of maximum size satisfy a series of conditions that reflect extraordinary symmetry G. Among these conditions are: the number of cliques of size ω(G) is exactly |V(G)|; the number of stable sets of size α(G) is exactly |V(G)|: every vertex of G is contained in exactly ω(G) cliques of size ω(G) and α(G) stable sets of size α(G): for every clique Q (respectively, stable set S) of maximum size there is a unique stable set S (clique O) of maximum size such that Q∩S ≡ Ø.Let Cnk denote the graph whose vertices can be enumerated as υ1,…,υn in such a way that υ1 and υ1 are adjacent in G if and only if i and j differ by at most k, modulo n. Chvátal has shown that Berge's Strong Perfect graph Conjecture is equivalent to the conjecture that if G is minimal imperfect with α(G) ≡ αandω(G) ≡ ω, then G has a spanning subgraph isomorphic to Cαω+1ω. Padberg's conditions are sufficiently restrictive to suggest the possibility of establishing the Strong Perfect Graph Conjecture by proving that any graph G satisfying these conditions must contain a spanning subgraph isomorphic to Cαω+1ω, whereα(G) ≡ αandω(G) ≡ ω. It is shown here, using only elementary linear algebra, that all partitionable graphs satisfy Padberg's conditions, as well as additional properties of the same spirit. Then examples are provided of partitionable graphs which contain no spanning subgraph isomorphic to Cαω+1ω, whereα(G) ≡ α and ω(G) ≡ ω. 相似文献
4.
Difference sets have been extensively studied in groups, principally in Abelian groups. Here we extend the notion of a difference set to loops. This entails considering the class of 〈υ, k〉 systems and the special subclasses of 〈υ, k, λ〉 principal block partial designs (PBPDs) and 〈υ, k, λ〉 designs. By means of a certain permutation matrix decomposition of the incidence matrices of a system and its complement, we can isomorphically identify an abstract 〈υ, k〉 system with a corresponding system in a loop. Special properties of this decomposition correspond to special algebraic properties of the loop. Here we investigate the situation when some or all of the elements of the loop are right inversive. We identify certain classes of 〈υ, k, λ〉 designs, including skew-Hadamard designs and finite projective planes, with designs and difference sets in right inverse property loops and prove a universal existence theorem for 〈υ, k, λ〉 PBPDs and corresponding difference sets in such loops. 相似文献
5.
F.E Bennett E Mendelsohn N.S Mendelsohn 《Journal of Combinatorial Theory, Series A》1980,29(2):142-150
Let k, λ, and υ be positive integers. A perfect cyclic design in the class PD(υ, k, λ) consists of a pair (Q, B) where Q is a set with |Q| = υ and B is a collection of cyclically ordered k-subsets of Q such that every ordered pair of elements of Q are t apart in exactly λ of the blocks for t = 1, 2, 3,…, k?1. To clarify matters the block [a1, a2, …, ak] has cyclic order a1 < a2 < a3 … < ak < a1 and ai and ai+1 are said to be t apart in the block where i + t is taken mod k. In this paper we are interested only in the cases where λ = 1 and υ ≡ 1 mod k. Such a design has blocks. If the blocks can be partitioned into υ sets containing pairwise disjoint blocks the design is said to be resolvable, and any such partitioning of the blocks is said to be a resolution. Any set of pairwise disjoint blocks together with a singleton consisting of the only element not in one of the blocks is called a parallel class. Any resolution of a design yields υ parallel classes. We denote by RPD(υ, k, 1) the class of all resolvable perfect cyclic designs with parameters υ, k, and 1. Associated with any resolvable perfect cyclic design is an orthogonal array with k + 1 columns and υ rows with an interesting conjugacy property. Also a design in the class RPD(υ, k, 1) is constructed for all sufficiently large υ with υ ≡ 1 mod k. 相似文献
6.
A Hartman 《Journal of Combinatorial Theory, Series A》1982,33(2):121-134
A Steiner-quadruple system of order υ is an ordered pair (X, Q), where X is a set of cardinality υ, and Q is a set of 4-subsets of X, called blocks, with the property that every 3-subset of X is contained in a unique block. In this paper we show that if there exists a quadruple system of order V with a subsystem of order υ, then there exists a quadruple system of order 3V ? 2υ with subsystems of orders V and υ. Hanani has given a proof of this result for υ = 1, and in a previous paper, the author has proved the case when V ≡ 2υ(mod 6). The construction given here proves all remaining cases, and has many applications to other existence problems for 3-designs. 相似文献
7.
Denote by pk(M) or υk(M) the number of k-gonal faces or k-valent of the convex 3-polytope M, respectively. Completely solving a problem by B. Grünbaum, the following theorem is proved: Given sequences of nonnegative integers p = (p3, p4,…pm), υ = (υ3, υ4,…,υn) satisfying ∑k?3(6−k)pk + 2∑k?3(3−k)υk = 12, there exists a convex 3-polytope M with pk(M) = pk for all k ≠ 6 and υk for all k ≠ 3 if and only if for the sequences p, υ the following does not hold: ∑pi = 0 for i odd and ∑υi = 1 for i ? 0 (mod 3). 相似文献
8.
A family ( X, B1 ), (X, B2 ), . . . , (X, Bq ) of q STS(v)s is a λ-fold large set of STS(v) and denoted by LSTS λ (v) if every 3-subset of X is contained in exactly λ STS(v)s of the collection. It is indecomposable and denoted by IDLSTS λ (v) if there does not exist an LSTS λ'(v) contained in the collection for any λ' λ. In this paper, we show that for λ = 5, 6, there is an IDLSTS λ (v) for v ≡ 1 or 3 (mod 6) with the exception IDLSTS6 (7). 相似文献
9.
A subset S of the vertex set of a graph G is called an F-set if every α?Γ(G), the automorphism group of G, is completely specified by specifying the images under α of all the points of S, and S has a minimum number of points. The number of points, k(G), in an F-set is an invariant of G, whose properties are studied in this paper. For a finite group Γ we define k(Γ) = max{k(G) | Γ(G) = Γ}. Graphs with a given Abelian group and given k-value (k ≤ k(Γ)) have been constructed. Graphs with a given group and k-value 1 are constructed which give simple proofs to the theorems of Frucht and Bouwer on the existence of graphs with given abstract/permutation groups. 相似文献
10.
A triple system is a balanced incomplete block design D(v, k, λ, b, r) with k = 3. Although it has been shown that triple systems exist for all values of the parameters satisfying the necessary conditions: direct methods (nonrecursive) of construction are not available in general. In this paper we give a direct method to construct a triple system for all values of the parameters satisfying the necessary conditions. 相似文献
11.
《Journal of Combinatorial Theory, Series A》1986,42(2):239-251
A t-design or generalized Steiner systemS(λ; t, k, υ) is a pair (X, B) with a υ-set X of points and a family B of k-subsets of X called blocks such that, each block has k points and any t points are contained in exactly λ blocks. An automorphism of (X, B) is a permutation of X which preserves B. In this paper the algebra of matrices, whose rows and columns are indexed by the members of P(X), that are invariant under the natural action of a group G ⩽Sym(X) is introduced. An epimorphism τ from this algebra onto the matrices whose rows and columns are indexed by the orbits of G acting on P(X) is discovered. This mapping carries the matrices of Wilson onto the matrices of Kramer and Mesner and therefore can be used to generalize the t-design inequalities of Fisher, Wilson, and Ray-Chaudhuri. A conjecture of Earl Kramer is settled and an elementary proof of a theorem of Livingstone and Wagner is presented. 相似文献
12.
A directed BIBD with parameters () is a BIBD with parameters () in which each ordered pair of varieties occurs together in exactly blocks. It is shown that (mod 3) is a necessary and sufficient condition for the existence of a directed () BIBD with k = 3. 相似文献
13.
《Discrete Mathematics》1986,62(2):197-210
A Kirkman square with index λ, latinicity μ, block size k and v points, KSk(v; μ, λ), is a t × t array (t = λ(v − 1)/μ(k − 1)) defined on a v-set V such that (1) each point of V is contained in precisely μ cells of each row and column, (2) each cell of the array is either empty or contains a k subset of V, and (3) the collection of blocks obtained from the nonempty cells of the array is a (v, k, λ)-BIBD. The existence question for KS2(v; μ, λ) has been completely selttled. We are interested in the next case k = 3. The case k = 3 and μ = λ = 1 appears to be quite difficult, although some existence results are available. For λ > 1 and μ ⩾ 1, the problem is more tractable. In this paper, we prove the existence of KS3(v; 2, 4) for v ≡ 3 (mod 12), v ≡ 6 (mod 60) and v ≡ 9 (mod 96). 相似文献
14.
D.A. Holton 《Discrete Mathematics》1973,4(2):151-158
A Michigan graph G on a vertex set V is called semi-stable if for some υ?V, Γ(Gυ) = Γ(G)υ. It can be shown that all regular graphs are semi-stable and this fact is used to show (i) that if Γ(G) is doubly transitive then G = Kn or K?n, and (ii) that Γ(G) can be recovered from Γ(Gυ). The second result is extended to the case of stable graphs. 相似文献
15.
Kozo Bannai 《Journal of Combinatorial Theory, Series B》1978,24(2):181-188
Watkins (J. Combinatorial Theory 6 (1969), 152–164) introduced the concept of generalized Petersen graphs and conjectured that all but the original Petersen graph have a Tait coloring. Castagna and Prins (Pacific J. Math. 40 (1972), 53–58) showed that the conjecture was true and conjectured that generalized Petersen graphs G(n, k) are Hamiltonian unless isomorphic to G(n, 2) where n ≡ 5(mod 6). The purpose of this paper is to prove the conjecture of Castagna and Prins in the case of coprime numbers n and k. 相似文献
16.
S.L. Ma 《Discrete Mathematics》1984,52(1):75-89
A (υ,k,α,β)-partial difference set in a finite group G of order υ is a subset D of G with k distinct elements such that expressions dnd?12 for d1 and d2 in D, represent each non-identity element not contained in D exactly α times and each non-identity element contained in D exactly α+β times. Such a set is closely related to association schemes of PBIB designs with two associate classes. 相似文献
17.
A subset S={s1,…,sk} of an Abelian group G is called an St-set of size k if all sums of t different elements in S are distinct. Let s(G) denote the cardinality of the largest S2-set in G. Let v(k) denote the order of the smallest Abelian group for which s(G)?k. In this article, bounds for s(G) are developed and v(k) is determined for k?15 by computing s(G) for Abelian groups of order up to 183 using exhaustive backtrack search with isomorph rejection. 相似文献
18.
Sylwia Cichacz 《Central European Journal of Mathematics》2014,12(3):529-533
A Γ-distance magic labeling of a graph G = (V, E) with |V| = n is a bijection ? from V to an Abelian group Γ of order n such that the weight $w(x) = \sum\nolimits_{y \in N_G (x)} {\ell (y)}$ of every vertex x ∈ V is equal to the same element µ ∈ Γ, called the magic constant. A graph G is called a group distance magic graph if there exists a Γ-distance magic labeling for every Abelian group Γ of order |V(G)|. In this paper we give necessary and sufficient conditions for complete k-partite graphs of odd order p to be ? p -distance magic. Moreover we show that if p ≡ 2 (mod 4) and k is even, then there does not exist a group Γ of order p such that there exists a Γ-distance labeling for a k-partite complete graph of order p. We also prove that K m,n is a group distance magic graph if and only if n + m ? 2 (mod 4). 相似文献
19.
20.
We characterize the structure of maximum-size sum-free subsets of a random subset of an abelian group G. In particular, we determine the threshold above which, with high probability as |G| → ∞, each such subset is contained in some maximum-size sum-free subset of G, whenever q divides |G| for some (fixed) prime q with q ≡ 2 (mod 3). Moreover, in the special case G = ?2n , we determine the sharp threshold for the above property. The proof uses recent ‘transference’ theorems of Conlon and Gowers, together with stability theorems for sum-free sets of abelian groups. 相似文献