Comparing the $p$-independence number of regular graphs to the $q$-independence number of their line graphs

Abstract

Let $G$ be a simple graph and let $L(G)$ denote the \emph{line graph} of $G$. A \emph{$p$-independent} set in $G$ is a set of vertices $S\subseteq V(G)$ such that the subgraph induced by $S$ has maximum degree at most $p$. The \emph{$p$-independence number} of $G$, denoted by $\hat{I}{\pm }_p(G)$, is the cardinality of a maximum $p$-independent set in $G$. In this paper, and motivated by the recent result that independence number is at most matching number for regular graphs~\cite{CaDaPe2020}, we investigate which values of the non-negative integers $p$, $q$, and $r$ have the property that $\hat{I}{\pm }_p(G)\le \hat{I}{\pm }_q(L(G))$ for all r-regular graphs. Triples $(p,q,r)$ having this property are called \emph{valid $\hat{I}\pm$-triples}. Among the results we prove are: \begin{itemize} \item $(p,q,r)$ is valid $\hat{I}\pm$-triple for $p\ge 0$, $q\ge 3$ , and $r\ge 2$. \item $(p,q,r)$ is valid $\hat{I}\pm$-triple for $p\le q<3$ and $r\ge 2$. \item $(p,q,r)$ is valid $\hat{I}\pm$-triple for $p\ge 0$, $q=2$, and $r$ even. \item $(p,q,r)$ is valid $\hat{I}\pm$-triple for $p\ge 0$, $q=2$, and $r$ odd with $r=\max \{3,\frac{17(p+1)}{16}\}$. \end{itemize} We also show a close relation between undetermined possible valid $\hat{I}\pm$-triples, the Linear Aboricity Conjecture, and the Path-Cover Conjecture.