𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The size of minimum 3-trees

✍ Scribed by Jorge L. Arocha; Joaquín Tey

Publisher
John Wiley and Sons
Year
2006
Tongue
English
Weight
199 KB
Volume
54
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A 3‐uniform hypergraph (3‐graph) is said to be tight, if for any 3‐partition of its vertex set there is a transversal triple. We give the final steps in the proof of the conjecture that the minimum number of triples in a tight 3‐graph on n vertices is exactly $\left\lceil n(n-2)/3 \right\rceil$. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 103–114, 2007

📜 SIMILAR VOLUMES

The size of minimum 3-trees: Cases 3 and
The size of minimum 3-trees: Cases 3 and 4 mod 6
✍ Arocha, Jorge L.; Tey, Joaqu�n 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 177 KB

A 3-uniform hypergraph is called a minimum 3-tree, if for any 3coloring of its vertex set there is a heterochromatic edge and the hypergraph has the minimum possible number of edges. Here we show that the number of edges in such 3-tree is for any number of vertices n ≡ 3, 4 (mod 6).

The Capacitated Minimum Spanning Tree
The Capacitated Minimum Spanning Tree
✍ K. M. Chandy; Tachen Lo 📂 Article 📅 1973 🏛 John Wiley and Sons 🌐 English ⚖ 386 KB

## Abstract The capacitated minimum spanning tree is an offspring of the minimum spanning tree and network flow problems. It has application in the design of multipoint linkages in elementary teleprocessing tree networks. Some theorems are used in conjunction with Little's branch and bound algorith

Trees with the minimum Wiener number
Trees with the minimum Wiener number
✍ Shu-Chung Liu; Li-Da Tong; Yeong-Nan Yeh 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 283 KB

The Wiener number (W) of a connected graph is the sum of distances for all pairs of vertices. As a graphical invariant, it has been found extensive application in chemistry. Considering the family of trees with n vertices and a fixed maximum vertex degree, we derive some methods that can strictly re

On the minimum size of tight hypergraphs
On the minimum size of tight hypergraphs
✍ Jorge L. Arocha; Javier Bracho; Victor Neumann-Lara 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 333 KB

## Abstract A __k__‐graph, __H__ = (__V, E__), is __tight__ if for every surjective mapping __f__: __V__ → {1,….k} there exists an edge α ϵ __E__ sicj tjat __f__|~α~ is injective. Clearly, 2‐graphs are tight if and only if they are connected. Bounds for the minimum number ϕ of edges in a tight __k_