Favaron's Theorem, k-dependence, and Tuza's Conjecture

Abstract

A vertex set $D$ in a graph $G$ is $k$-dependent if $G[D]$ has maximum degree at most $k-1$, and $k$-dominating if every vertex outside $D$ has at least $k$ neighbors in $D$. Favaron proved that if $D$ is a $k$-dependent set maximizing the quantity $k|D|-|E(G[D])|$, then $D$ is $k$-dominating. We extend this result, showing that such sets satisfy a stronger structural property, and we find a surprising connection between Favaron's theorem and a conjecture of Tuza regarding packing and covering of triangles.

12 pages. Strengthened main theorem and simplified its proof by replacing vertex-orderings with orientations

References in corpus (1)

• Tuza's Conjecture for Graphs of Maximum Average Degree Less Than 7

Cited by in corpus (1)

• Maximal $k$-Edge-Colorable Subgraphs, Vizing's Theorem, and Tuza's Conjecture