Menu
For a connected graph \( G \) of order \( n \geq 3 \) and an ordered factorization \( \mathcal{F} = \{G_1, G_2, \ldots, G_k\} \) of \( G \) into \( k \) spanning subgraphs \( G_i \) (\( 1 \leq i \leq 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, \ldots, 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 \( \binom{k+2}{3} \) with \( \text{det}(G) = k \), then \( k \equiv 2 \pmod{4} \) or \( k \equiv 3 \pmod{4} \). We investigate the largest order of a connected cubic graph with prescribed detection number.