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

arXiv1407.2336MaRDI QIDQ6252982FDOQ6252982

Gregory J. Puleo

Publication date: 8 July 2014

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.

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)

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)