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

MaRDI QIDQ6252982FDO

Authors Gregory J. Puleo

Publication date 8 July 2014

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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.

This page was built for publication: Favaron's Theorem, k-dependence, and Tuza's Conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6252982)