✦ LIBER ✦

Decompositions of Complete Multigraphs Related to Hadamard Matrices

✍ Scribed by David A Gregory; Kevin N Vander Meulen

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 242 KB
Volume: 82
Category: Article
ISSN: 0097-3165
DOI: 10.1006/jcta.1997.2853

No coin nor oath required. For personal study only.

✦ Synopsis

Let bp(+K v ) be the minimum number of complete bipartite subgraphs needed to partition the edge set of +K v , the complete multigraph with + edges between each pair of its v vertices. Many papers have examined bp(+K v ) for v 2+. For each + and v with v 2+, it is shown here that if certain Hadamard and conference matrices exist, then bp(+K v ) must be one of two numbers. Also, generalizations to decompositions and covers by complete s-partite subgraphs are discussed and connections to designs and codes are presented.

1998 Academic Press

Throughout the paper, +K v denotes the complete multigraph with v 2 vertices and + edges between each pair of distinct vertices. A biclique in +K v is a simple complete bipartite subgraph. A biclique decomposition of +K v is a collection of bicliques whose edge sets partition the edge set of +K v . The biclique decomposition number of +K v , denoted bp(+K v ), is the minimum number of bicliques needed in a biclique decomposition of +K v . Minimum biclique decompositions of #K v and of +K v together give a biclique decomposition of (#++) K v . Therefore, bp((#++) K v ) bp(#K v )+bp(+K v ).

📜 SIMILAR VOLUMES

Cycle decompositions of complete multigr

Cycle decompositions of complete multigraphs

✍ Benjamin R. Smith 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 106 KB

## Abstract In this paper we establish necessary and sufficient conditions for decomposing the complete multigraph λ__K__~__n__~ into cycles of length λ, and the λ‐fold complete symmetric digraph λ__K__ into directed cycles of length λ. As a corollary to these results we obtain necessary and suffic

Cycle decompositions of complete multigr

Cycle decompositions of complete multigraphs

✍ Darryn Bryant; Daniel Horsley; Barbara Maenhaut; Benjamin R. Smith 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 265 KB

It is shown that the obvious necessary conditions for the existence of a decomposition of the complete multigraph with n vertices and with k edges joining each pair of distinct vertices into m-cycles, or into m-cycles and a perfect matching, are also sufficient. This result follows as an easy conseq

Applying a proof of tverberg to complete

Applying a proof of tverberg to complete bipartite decompositions of digraphs and multigraphs

✍ Dan Pritikin 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 195 KB

Graham and Pollak 121 proved that n -1 is the minimum number of edge-disjoint complete bipartite subgraphs into which the edges of K,, decompose. Tverberg 161, using a linear algebraic technique, was the first to give a simple proof of this result. We apply Tverberg's technique to obtain results for

Enumeration of generalized Hadamard matr

Enumeration of generalized Hadamard matrices of order 16 and related designs

✍ P. B. Gibbons; R. Mathon 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 142 KB

## Abstract We investigate signings of symmetric GDD($16 \times 2^i$, 16, $2^{4-i}$)s over $Z\_2$ for $1 \le i \le 3$. Beginning with $i=1$, at each stage of this process a signing of a GDD($16 \times 2^i$, 16, $2^{4-i}$) produces a GDD($16 \times 2^{i+1}$, 16, $2^{4-i-1}$). The initial GDDs ($i=1$

Constrained decompositions of integer ma

Constrained decompositions of integer matrices and their applications to intensity modulated radiation therapy

✍ Céline Engelbeen; Samuel Fiorini 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 259 KB

## Abstract We consider combinatorial optimization problems arising in radiation therapy. Given a matrix __I__ with non‐negative integer entries, we seek a decomposition of __I__ as a weighted sum of binary matrices having the consecutive ones property, such that the total sum of the coefficients i

Atomic decompositions of function spaces

Atomic decompositions of function spaces with Muckenhoupt weights, and some relation to fractal analysis

✍ Dorothee D. Haroske; Iwona Piotrowska 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 259 KB

## Abstract This paper deals with atomic decompositions in spaces of type __B^s^~p,q~__ (ℝ^__n__^ , __w__), __F^s^~p,q~__ (ℝ^__n__^ , __w__), 0 < __p__ < ∞, 0 < __q__ ≤ ∞, __s__ ∈ ℝ, where the weight function __w__ belongs to some Muckenhoupt class __A~r~__. In particular, we consider the weight fu