子立方图的D(2)−点和可区别边染色

D(2)−Vertex Sum Distinguishing Edge Coloring of Subcubic Graphs

  • 摘要: 子立方图是指最大度不超过3的简单连通图。 正常子立方图是最小度至少为2的立方图,即图中任意顶点的度数在2与3之间。 图的 D(2)- 点和可区别边染色是指图的一个正常边染色,满足图中任意两个距离不超过2的顶点 u 、 v ,其关联边所染的颜色数之和互不相同。 本文通过分析子立方图的结构特点,利用反证法和极小反例原理假设子立方图不存在某一最小性质的反例,又有矛盾证明极小反例存在,最后又由整个断言存在矛盾进而证明定理成立,组合零点定理通过代数工具分析结构中元素数量关系,多维度揭示了子立方图的结构特点,讨论了子立方图的 D(2)- 点和可区别边染色问题,得到了其 D(2)- 点和可区别边色数不超过12,为图论中图的染色理论研究提供新的理论成果与实践参考。

     

    Abstract: A subcubic graph refers to a simple connected graph with a maximum degree of no more than 3. A normal subcubic graph is a subcubic graph with a minimum degree of at least 2, meaning that the degree of any vertex in the graph ranges between 2 and 3. A D(2)- vertex sum distinguishing edge coloring of a graph is a proper edge coloring such that for any two vertices \mathrmu and \mathrmv with a distance of no more than 2 in the graph, the sums of the colors of the edges incident to them are different.In this paper, by analyzing the structural characteristics of subcubic graphs, the method of proof by contradiction and the principle of minimal counterexamples are employed. Specifically, it is assumed that there exists a minimal counterexample that does not possess a certain minimal property. Then, a contradiction is derived, demonstrating the existence of such a minimal counterexample. Subsequently, another contradiction arises from the overall assertion, thereby proving the validity of the theorem. Combining the Zero-One Polynomial Theorem, which utilizes algebraic tools to analyze the quantitative relationships among elements within the structure, the structural characteristics of subcubic graphs are revealed from multiple dimensions. This paper discusses the D(2)- vertex sum distinguishing edge coloring problem of subcubic graphs and concludes that their D(2)- vertex sum distinguishing edge chromatic number does not exceed 12, providing new theoretical achievements and practical references for the study of graph coloring theory in graph theory.

     

/

返回文章
返回