Back to Search
Start Over
Spanning trees of 3-uniform hypergraphs
- Source :
-
Advances in Applied Mathematics . Oct2011, Vol. 47 Issue 4, p840-868. 29p. - Publication Year :
- 2011
-
Abstract
- Abstract: Masbaum and Vaintrobʼs “Pfaffian matrix-tree theorem” implies that counting spanning trees of a 3-uniform hypergraph (abbreviated to 3-graph) can be done in polynomial time for a class of “3-Pfaffian” 3-graphs, comparable to and related to the class of Pfaffian graphs. We prove a complexity result for recognizing a 3-Pfaffian 3-graph and describe two large classes of 3-Pfaffian 3-graphs – one of these is given by a forbidden subgraph characterization analogous to Littleʼs for bipartite Pfaffian graphs, and the other consists of a class of partial Steiner triple systems for which the property of being 3-Pfaffian can be reduced to the property of an associated graph being Pfaffian. We exhibit an infinite set of partial Steiner triple systems that are not 3-Pfaffian, none of which can be reduced to any other by deletion or contraction of triples. We also find some necessary or sufficient conditions for the existence of a spanning tree of a 3-graph (much more succinct than can be obtained by the currently fastest polynomial-time algorithm of Gabow and Stallmann for finding a spanning tree) and a superexponential lower bound on the number of spanning trees of a Steiner triple system. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 01968858
- Volume :
- 47
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- Advances in Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 65281111
- Full Text :
- https://doi.org/10.1016/j.aam.2011.04.006