pith. sign in

arxiv: 1407.2336 · v3 · pith:HNHZKJ3Nnew · submitted 2014-07-09 · 🧮 math.CO

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

classification 🧮 math.CO
keywords favaronconjecturedependentdominatingtheoremtuzavertexconnection
0
0 comments X
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.