On perfect one-factorization of the complete graphK 2p

Anderson [1, 2] and Nakamura [4] have constructed perfect 1-factorizations ofK _2p independently, wherep is an odd prime. In this paper, we show that these two 1-factorizations are isomorphic.     

Orthogonal one-factorization graphs

An orthogonal one-factorization graph (OOFG) is a graph in which the vertices are one-factorizations of some underlying graph H, and two vertices are adjacent if and only if the one-factorizations are orthogonal. An arbitrary finite graph, G, is realizable if there is an OOFG isomorphic to G. We show that every finite graph is realizable as an OOFG with underlying graph K_n for some n. We also discuss some special cases.     

Maximum packings ofK n with copies ofK 4 − e

For eachn, we determine the maximum number of pairwise edge disjoint copies ofK ₄ – e inK _n , and all possible graphs that arise from the unused edges.     

On restricted colourings ofK n

Given a sample graphH and two integers,n andr, we colourK _n byr colours and are interested in the following problem. Which colourings of the subgraphs isomorphic to H in K _n must always occur (and which types of colourings can occur whenK _n is coloured in an appropriate way)? These types of problems include theRamsey theory, where we ask: for whichn andr must a monochromaticH occur. They also include theanti-Ramsey type problems, where we are trying to ensure a totally multicoloured copy ofH, that is, anH each edge of which has different colour.     

Arens regularity ofK(X)

LetX be a reflexive Banach space andK(X) the operator algebra of compact linear operatorsu:XX. In this note we prove the following two results: a) Any decomposable bilinear operator fromK(X)×K(X) intoK(X) is Arens regular; b) ifX has an unconditional basis then any bounded bilinear operator fromK(X)×K(X) intoK(X) is Arens regular.     

The existence of non-trivial hyperfactorizations ofK 2n

A -hyperfactorization ofK _2n is a collection of 1-factors ofK _2n for which each pair of disjoint edges appears in precisely of the 1-factors. We call a -hyperfactorizationtrivial if it contains each 1-factor ofK _2n with the same multiplicity (then =(2n–5)!!). A -hyperfactorization is calledsimple if each 1-factor ofK _2n appears at most once. Prior to this paper, the only known non-trivial -hyperfactorizations had one of the following parameters (or were multipliers of such an example)

d-Cube decompositions ofK n/K m

Necessary conditions onn, m andd are given for the existence of an edge-disjoint decomposition ofK _n/K _m into copies of the graph of ad-dimensional cube. Sufficiency is shown whend=3 and, in some cases, whend=2^t. We settle the problem of embedding 3-cube decompositions ofK _m into 3-cube decompositions ofK _n, wherenm.Research of P.A. and D.E.B. supported by Australian Research Council grant A49532750Research of D.E.B. supported by Australian Research Council grant ARCPDF015GResearch of S.I.E. and C.V.E. supported by Illinois State University Research Office     

The domestic levels ofK c are iterable

We show that the models produced by theK ^c construction before (if ever) it reaches a non-domestic premouse are all iterable. As a corollary we get thatPFA plus the existence of a measurable cardinal implies the existence of a non-domestic premouse. Partially supported by the Italian MURST. Research partially supported by NSF grant DMS 98-03292. Research partially supported by NSF grant DMS 98-03611.     

A perfect non-topologizable group

The first example of a group G whose automorphism group Aut (G) admits only discrete separated topology is presented in the paper. The group G is isomorphic to Aut (G) and all elements of the group G except for the unity satisfy some equation w(x) = 1.     

Special subdivisions ofK 4 and 4-chromatic graphs

In this paper we consider special subdivisions ofK ₄ in which some of the edges are left undivided. A best possible extremal-result for the case where the edges of a Hamiltonian path are left undivided is obtained. Moreover special subdivisions as subgraphs of 4-chromatic graphs are studied. Our main-result on 4-chromatic graphs says that any 4-critical graphG contains an odd cycleC without diagonals such thatG-V (C) is connected.     

A note on perfect Lee-codes

It is proved that there are no perfect Lee-error-correcting (PL(n, e, q))-codes over large (q?2e+1) prime power alphabets in the case e=13 for n?2, and in the case e=15 for n?2, n≠357.     

A note on perfect graphs

Let the lines of a complete graph be 3-colored so that no triangle gets 3 different colors. If two of these colors form perfect graphs then so does the third.     

A note on perfect rings

The second author was partially supported by the National Science Foundation.     

A note on perfect Gaussian elimination

We extend a result of D. J. Rose [9] on perfect Gaussian elimination for symmetric matrices. It is proved that the restriction that all pivots are to be chosen along the main diagonal can be removed without loss of generality.     

A characterization of domination perfect graphs

Let γ(G) and i(G) be the domination number and independent domination number of a graph G, respectively. Sumner and Moore [8] define a graph G to be domination perfect if γ(H) = i(H), for every induced subgraph H of G. In this article, we give a finite forbidden induced subgraph characterization of domination perfect graphs. Bollobás and Cockayne [4] proved an inequality relating γ(G) and i(G) for the class of K^1,k -free graphs. It is shown that the same inequality holds for a wider class of graphs.     

A class of weakly perfect graphs

A graph is called weakly perfect if its chromatic number equals its clique number. In this note a new class of weakly perfect graphs is presented and an explicit formula for the chromatic number of such graphs is given.     

A decomposition for strongly perfect graphs

A graph G is strongly perfect if every induced subgraph H of G contains a stable set that meets all the maximal cliques of H. We present a graph decomposition that preserves strong perfection: more precisely, a stitch decomposition of a graph G = (V, E) is a partition of V into nonempty disjoint subsets V₁, V₂ such that in every P₄ with vertices in both V_iapos;s, each of the three edges has an endpoint in V₁ and the other in V₂. We give a good characterization of graphs that admit a stitch decomposition and establish several results concerning the stitch decomposition of strongly perfect graphs.