On the cone of weighted graphs generated by triangles

Coen del Valle 1, Peter J. Dukes1, Kseniya Garaschuk 2
1Mathematics and Statistics University of Victoria Victoria, BC, Canada
2Mathematics and Statistics University of the Fraser Valley Abbotsford, BC, Canada

Abstract

Motivated by problems involving triangle-decompositions of graphs, we examine the facet structure of the cone \( \tau_n \) of weighted graphs on \( n \) vertices generated by triangles. Our results include enumeration of facets for small \( n \), a construction producing facets of \( \tau_{n+1} \) from facets of \( \tau_n \), and an arithmetic condition on entries of the normal vectors. We also point out that a copy of \( \tau_n \) essentially appears via the perimeter inequalities at one vertex of the metric polytope.