Comparing the $p$-independence number of regular graphs to the $q$-independence number of their line graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909605307613184 |
|---|---|
| author | Caro, Yair Davila, Randy Pepper, Ryan |
| author_facet | Caro, Yair Davila, Randy Pepper, Ryan |
| contents | 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 $α_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 $α_p(G) \leq α_q(L(G))$ for all r-regular graphs. Triples $(p, q, r)$ having this property are called \emph{valid $α$-triples}. Among the results we prove are: \begin{itemize}
\item $(p, q, r)$ is valid $α$-triple for $p \geq 0$, $q \geq 3$ , and $r\geq 2$.
\item $(p, q, r)$ is valid $α$-triple for $p \leq q < 3$ and $r\geq 2$.
\item $(p, q, r)$ is valid $α$-triple for $p \geq 0$, $q = 2$, and $r$ even.
\item $(p, q, r)$ is valid $α$-triple for $p \geq 0$, $q = 2$, and $r$ odd with $r = \max \Big \{ 3, \frac{17(p+1)}{16}\Big \}$. \end{itemize} We also show a close relation between undetermined possible valid $α$-triples, the Linear Aboricity Conjecture, and the Path-Cover Conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_03233 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Comparing the $p$-independence number of regular graphs to the $q$-independence number of their line graphs Caro, Yair Davila, Randy Pepper, Ryan Combinatorics 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 $α_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 $α_p(G) \leq α_q(L(G))$ for all r-regular graphs. Triples $(p, q, r)$ having this property are called \emph{valid $α$-triples}. Among the results we prove are: \begin{itemize} \item $(p, q, r)$ is valid $α$-triple for $p \geq 0$, $q \geq 3$ , and $r\geq 2$. \item $(p, q, r)$ is valid $α$-triple for $p \leq q < 3$ and $r\geq 2$. \item $(p, q, r)$ is valid $α$-triple for $p \geq 0$, $q = 2$, and $r$ even. \item $(p, q, r)$ is valid $α$-triple for $p \geq 0$, $q = 2$, and $r$ odd with $r = \max \Big \{ 3, \frac{17(p+1)}{16}\Big \}$. \end{itemize} We also show a close relation between undetermined possible valid $α$-triples, the Linear Aboricity Conjecture, and the Path-Cover Conjecture. |
| title | Comparing the $p$-independence number of regular graphs to the $q$-independence number of their line graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2409.03233 |