|
|
不含平衡圈的符号图的分解
|
Abstract:
本文主要在符号图框架拟阵的定义下，通过证明所含的圈中没有平衡圈的符号图G上的参数![\"\"](\"Edit_1ae8ad4d-c446-4bb4-90bf-cc7dd622727c.png\")
大于等于![\"\"](\"Edit_dc172aa0-65c4-4de8-b4c8-d745e097cc7c.png\")
，从而证明在k=1，以及任意的非负整数d的条件下，不含平衡圈的符号图能分解成两个独立集B1和I，且I在G中导出图G[I]中顶点最大度为d。
In this paper, we study the signed graph based on the frame matroid. For the signed graph G with-out contains any balanced cycle, we prove the parameter ![\"\"](\"Edit_74d7ab52-e951-4650-8d31-0d13891be38c.png\")
is greater than ![\"\"](\"Edit_f53c9acf-9b54-41cf-839a-4ddf987ed639.png\")
, then we prove when k=1 and any positive integers d, the signed graph G without con-tains any balanced cycle can decompose into two independent sets B1 and I, the degree of vertex in the induced graph G[I] is at most d.
| [1] | Edmonds, J. (1965) Minimum Partition of a Matroid into Independent Subsets. Journal of Research of the National Bu-reau of Standards, Section B, 69B, 67-72. https://doi.org/10.6028/jres.069B.004 |
| [2] | Edmonds, J. (1965) Leh-man’s Switching Game and a Theorem of Tutte and Nash-Williams. Journal of Research of the National Bureau of Standards, Section B, 69B, 73-77. https://doi.org/10.6028/jres.069B.005 |
| [3] | Kierstead, H.A. and Yang, D. (2005) Very Asymmetric Marking Games. Order, 22, 93-107.
https://doi.org/10.1007/s11083-005-9012-y |
| [4] | Fan, G., Li, Y., Song, N. and Yang, D. (2015) Decomposing a Graph into Pseudoforests with One Having Bounded Degree. Journal of Combinatorial Theory, Series B, 115, 72-95. https://doi.org/10.1016/j.jctb.2015.05.003 |
| [5] | 方旭倩. 强九龙树猜想及九龙树定理的推广研究[D]: [硕士学位论文]. 金华: 浙江师范大学, 2021. |
