On Detectable Factorizations of Cubic Graphs

摘要

For a connected graph G of order n ≥ 3 and an ordered factorization F = {G_1, G_2, …, G_k} of G into k spanning subgraphs G_i (1 ≤ i ≤ k), the color code of a vertex υ of G with respect to F is the ordered k-tuple c(υ) = (a_1,a_2,…,a_k) where a_i = deg_(Gi) υ. If distinct vertices have distinct color codes, then the factorization F is called a detectable factorization of G; while the detection number 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 Pe-tersen graph has a detectable F-factorization into three factors. Furthermore, if G is a connected cubic graph of order (_3~(k+2)) with det(G) = k, then k ≡ 2 (mod 4) or k ≡ 3 (mod 4). We investigate the largest order of a connected cubic graph with prescribed detection number.