On Detectable Factorizations of Cubic Graphs

Abstract

For a connected graph $G$ of order $n\ge 3$ and an ordered factorization $\mathcal{F}=\{G_1,G_2,\dots ,G_k\}$ of $G$ into $k$ spanning subgraphs $G_i$ ($1\le i\le k$), the color code of a vertex $v$ of $G$ with respect to $\mathcal{F}$ is the ordered $k$-tuple $c(v)=(a_1,a_2,\dots ,a_k)$ where $a_i={\text{deg}}_{G_i}v$. If distinct vertices have distinct color codes, then the factorization $\mathcal{F}$ is called a detectable factorization of $G$; while the detection number $\text{det}(G)$ of $G$ is the minimum positive integer $k$ for which $G$ has a detectable factorization into $k$ factors. We study detectable factorizations of cubic graphs. It is shown that there is a unique graph $F$ for which the Petersen graph has a detectable $F$-factorization into three factors. Furthermore, if $G$ is a connected cubic graph of order $(\genfrac{}{}{0ex}{}{k+2}{3})$ with $\text{det}(G)=k$, then $k\equiv 2(\mathrm{mod}4)$ or $k\equiv 3(\mathrm{mod}4)$. We investigate the largest order of a connected cubic graph with prescribed detection number.