Not All Saturated 3-Forests Are Tight

Authors:

HGHeidi Gebauer
Heidi Gebauer
AGAnna Gundert
Anna Gundert
RMRobin A. Moser
Robin A. Moser
YOYoshio Okamoto
Yoshio Okamoto

Preprint

Publisher website

Google Scholar

15 September 2011

preprint
Published by arXiv in arXiv

DOI:10.48550/arXiv.1109.3390

Abstract

A basic statement in graph theory is that every inclusion-maximal forest is connected, i.e. a tree. Using a definiton for higher dimensional forests by Graham and Lovasz and the connectivity-related notion of tightness for hypergraphs introduced by Arocha, Bracho and Neumann-Lara in, we provide an example of a saturated, i.e. inclusion-maximal 3-forest that is not tight. This resolves an open problem posed by Strausz.

Keywords

INCLUSION MAXIMAL
FORESTS ARE TIGHT
BASIC STATEMENT
GRAPH THEORY
CONNECTED
SATURATED

All Related Versions

Version 1, 2011-09-15, ArXiv

This publication has 2 references indexed in Scilit:

Forestation in Hypergraphs: Linear $k$-Trees
The Electronic Journal of Combinatorics, 2003
On the minimum size of tight hypergraphs
Journal of Graph Theory, 1992