Favaron's Theorem, k-dependence, and Tuza's Conjecture
classification
🧮 math.CO
keywords
favaronconjecturedependentdominatingtheoremtuzavertexconnection
read the original 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 paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.