On the cone of weighted graphs generated by triangles

Coen Del Valle; Peter J. Dukes; Kseniya Garaschuk

On the cone of weighted graphs generated by triangles

Coen Del Valle
, Peter J. Dukes
, Kseniya Garaschuk

Research output: Contribution to journal › Article › peer-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 language	English
Pages (from-to)	245-268
Number of pages	24
Journal	Journal of Combinatorial Mathematics and Combinatorial Computing
Volume	116
Publication status	Published - 1 Feb 2021

Handle.net

Persistent link to portal record

Cite this

@article{06dcc1e4c29748188e563fdb11d39697,

title = "On the cone of weighted graphs generated by triangles",

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.",

author = "\{Del Valle\}, Coen and Dukes, \{Peter J.\} and Kseniya Garaschuk",

note = "Funding: This research is supported by NSERC grant 312595-2017.",

year = "2021",

month = feb,

day = "1",

language = "English",

volume = "116",

pages = "245--268",

journal = "Journal of Combinatorial Mathematics and Combinatorial Computing",

issn = "0835-3026",

publisher = "Charles Babbage Research Centre",

}

TY - JOUR

T1 - On the cone of weighted graphs generated by triangles

AU - Del Valle, Coen

AU - Dukes, Peter J.

AU - Garaschuk, Kseniya

N1 - Funding: This research is supported by NSERC grant 312595-2017.

PY - 2021/2/1

Y1 - 2021/2/1

N2 - 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.

AB - 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.

UR - http://hdl.handle.net/1828/12747

M3 - Article

AN - SCOPUS:85112568431

SN - 0835-3026

VL - 116

SP - 245

EP - 268

JO - Journal of Combinatorial Mathematics and Combinatorial Computing

JF - Journal of Combinatorial Mathematics and Combinatorial Computing

ER -

On the cone of weighted graphs generated by triangles

Abstract

Handle.net

Other files and links

Fingerprint