𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On a conjecture of Tuza about packing and covering of triangles

✍ Scribed by Michael Krivelevich

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
312 KB
Volume
142
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Zs. Tuza conjectured that if a simple graph G does not contain more than k pairwise edge disjoint triangles, then there exists a set of at most 2k edges which meets all triangles in G. We prove this conjecture for K,, 3 -free graphs (graphs that do not contain a homeomorph of K,. 3). Two fractional versions of the conjecture are also proved.

📜 SIMILAR VOLUMES

On a Conjecture of Nicolas–Sárközy about
On a Conjecture of Nicolas–Sárközy about Partitions
✍ F. Ben saı̈d 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 152 KB

Let N be the set of positive integers, B ¼ fb 1 5 . . . 5b k g & N, N 2 N, and N5b k . For i ¼ 0 or 1, A ¼ A i ðB; NÞ is the set (introduced by Nicolas, Ruzsa, and Sa´rko¨zy, J. Number Theory 73 (1998), 292-317) such that A \ f1; . . . ; Ng ¼ B and pðA; nÞ iðmod2Þ for n 2 N; n4N, where pðA; nÞ denot

Strongly edge triangle regular graphs an
Strongly edge triangle regular graphs and a conjecture of Kotzig
✍ B.Radhakrishnan Nair; A. Vijayakumar 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 513 KB

The concepts of strongly vertex triangle regular graphs and strongly edge triangle regular graphs are introduced. An expression for the triangle number of a vertex in the composition of two graphs is obtained. It is proved that a self-complementary graph is strongly regular if and only if it is stro

On a conjecture about the generalized ex
On a conjecture about the generalized exponent of primitive matrices
✍ Bolian Liu; Qiaoliang Li 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 122 KB

## Abstract In this paper the conjecture on the __k__th upper multiexponent of primitive matrices proposed by R.A. Brualdi and Liu are completely proved.