On the cone of weighted graphs generated by triangles

Coen Del Valle, Peter J. Dukes, Kseniya Garaschuk

Research output: Contribution to journalArticlepeer-review

Abstract

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

Original languageEnglish
Pages (from-to)245-268
Number of pages24
JournalJournal of Combinatorial Mathematics and Combinatorial Computing
Volume116
Publication statusPublished - 1 Feb 2021

Fingerprint

Dive into the research topics of 'On the cone of weighted graphs generated by triangles'. Together they form a unique fingerprint.

Cite this