CAJ | 학술논문

假设G是一个1-可扩图.G的1-因子覆盖是G的某些1-因子的集合Μ使得UM∈ΜM=E(G).1-因子数目最小的1-因子覆盖称为excessive facorization.一个excessive factorization中的1-因子数目称为图G的excessive index,记为χ′e(G).本文我们基于G的耳朵分解和E(G)的依赖关系给出了χ′e(G)的上界.对任意正整数.κ≥3,我们构造出一个图G使得△(G)=3而χ′e(G)=κ.进而,我们考虑了乘积图的excessive index.
가설G시일개1-가확도.G적1-인자복개시G적모사1-인자적집합Μ사득UM∈ΜM=E(G).1-인자수목최소적1-인자복개칭위excessive facorization.일개excessive factorization중적1-인자수목칭위도G적excessive index,기위χ′e(G).본문아문기우G적이타분해화E(G)적의뢰관계급출료χ′e(G)적상계.대임의정정수.κ≥3,아문구조출일개도G사득△(G)=3이χ′e(G)=κ.진이,아문고필료승적도적excessive index.
Let G be a 1-extendable graph. A 1-factor cover of G is a set Μ of 1-factors of G such that UM∈ΜM=E(G). A 1-factor cover of minimum cardinality is called an excessive factorization. The excessive index of G, denote χ′e(G), is the size of an excessive factorization of G. In the present paper, we obtain a tight upper bound of χ′e(G) based on dependence relation on E(G) and ear decomposition of G. For any positive integer κ≥3, we construct a graph G with△(G) = 3 and χ′e(G) = κ. In addition, we also consider the excessive index of the Cartesian product of two graphs.