Packing and Covering Directed Triangles

被引：3

作者：

McDonald, Jessica ^{[1
]}

Puleo, Gregory J. ^{[1
]}

Tennenhouse, Craig ^{[2
]}

机构：

[1] Auburn Univ, Dept Math & Stat, Auburn, AL 36849 USA

[2] Univ New England, Dept Math Sci, Biddeford, ME 04005 USA

来源：

GRAPHS AND COMBINATORICS | 2020年 / 36卷 / 04期

关键词：

Digraphs; Packing; Covering; Triangles; CONJECTURE; GRAPHS;

D O I：

10.1007/s00373-020-02167-8

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove that if a directed multigraph D has at most t pairwise arc-disjoint directed triangles, then there exists a set of less than 2t arcs in D which meets all directed triangles in D, except in the trivial case t=0. This answers affirmatively a question of Tuza from 1990.

引用

页码：1059 / 1063

页数：5

共 12 条

[1] Tuza's Conjecture is Asymptotically Tight for Dense Graphs [J].

Baron, Jacob D. ;

Kahn, Jeff .

COMBINATORICS PROBABILITY & COMPUTING, 2016, 25 (05) :645-667

[2] PACKING TRIANGLES IN WEIGHTED GRAPHS [J].

Chapuy, Guillaume ;

Devos, Matt ;

McDonald, Jessica ;

Mohar, Bojan ;

Scheide, Diego .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2014, 28 (01) :226-239

[3] Integer and fractional packings in dense graphs [J].

Haxell, PE ;

Rödl, V .

COMBINATORICA, 2001, 21 (01) :13-38

[4] Packing and covering triangles in graphs [J].

Haxell, PE .

DISCRETE MATHEMATICS, 1999, 195 (1-3) :251-254

[5] Packing and Covering Triangles in K 4-free Planar Graphs [J].

Haxell, Penny ;

Kostochka, Alexandr ;

Thomasse, Stephan .

GRAPHS AND COMBINATORICS, 2012, 28 (05) :653-662

[6] ON A CONJECTURE OF TUZA ABOUT PACKING AND COVERING OF TRIANGLES [J].

KRIVELEVICH, M .

DISCRETE MATHEMATICS, 1995, 142 (1-3) :281-286

[7] Small Edge Sets Meeting all Triangles of a Graph [J].

Lakshmanan, S. Aparna ;

Bujtas, Cs. ;

Tuza, Zs. .

GRAPHS AND COMBINATORICS, 2012, 28 (03) :381-392

[8] Tuza's Conjecture for graphs with maximum average degree less than 7 [J].

Puleo, Gregory J. .

EUROPEAN JOURNAL OF COMBINATORICS, 2015, 49 :134-152

[9] A CONJECTURE ON TRIANGLES OF GRAPHS [J].

TUZA, Z .

GRAPHS AND COMBINATORICS, 1990, 6 (04) :373-380

[10] PERFECT TRIANGLE FAMILIES [J].

TUZA, Z .

BULLETIN OF THE LONDON MATHEMATICAL SOCIETY, 1994, 26 :321-324

← 1 2 →