On Detectable Factorizations of Regular 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 v of G with respect to F is the ordered k-tuple code(v) = (a_1,a_2, …,a_k) where a_i, = deg_(G_i). v. 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 show that the detection number of every cubic graph of order at most 10 is 3. Various detectable factorizations of cubic graphs are studied. It is shown that there is a connected cubic graph of order 10 that possess all possible detectable factorizations with three factors. We also investigate the largest order of a connected regular graph with prescribed detection number.