关于混合图H-秩的一个注记
2022-01-18朱佳敏李双东
安徽建筑大学学报 2021年6期
朱佳敏，李双东，2
（1．安徽大学 数学科学学院，安徽 合肥 230601；2．安徽大学江淮学院，安徽 合肥 230031）
1 预备知识
引理1.1
v
不在G
的任何圈上，则（2）如果v
在G
的一个圈上，则c
(G
-v
)≤c
(G
)-1；（3）如果G
中包含顶点相交的圈，则存在位于相交圈上的顶点v
，满足c
(G
-v
)≤c
(G
)-2；（4）如果G
中的圈两两不交，则c
(G
)等于G
中圈的个数。引理1.2
引理1.3
引理1.4
定义1.5
设G
是含悬挂点的简单图，将G
中的悬挂点及其邻点一起删除的操作称为 -δ
变换。设G
是圈互不相交的简单图。对G
连续实施δ
-变换，直到得到的子图不含悬挂点，称该子图是G
的一个重要子图。把G
中的每个圈都收缩成一个新的顶点，所得不含圈的图记作T
，所有由圈收缩所得顶点构成的集合记作W
。将G
中所有的圈和与这些圈上顶点相关联的边删除，所得不含圈的图记作[T
]。引理1.6
引理1.7
定理1.8
定理1.9
G
中任意两个圈均没有公共顶点；
m
(T
)=m
([T
])，即存在T
的一个最大匹配M
，使得M
不覆盖W
中的点。引理1.10
m
(G
)- 2c
(G
), 2m
(G
)- 2c
(G
)+ 2, 2m
(G
)+c
(G
)的单圈混合图，不存在H-秩为2m
(G
)- 2c
(G
)+1的单圈混合图。2 主要结果
对于图G
的悬挂点，如果其邻点不在G
的圈上，则称该悬挂点是类型1的；否则，称该悬挂点是类型2的。引理2.1
u
是类型1的，则
u
是类型2的，则证明
u
是类型2的，则由引理1.1（2），
由引理1.6，
（1）式与定理1.9矛盾，命题得证。
满足()cG
k
= 的连通简单图称为k-圈图。设G
是-k
圈图，G
不含悬挂点的k-圈子图称为G
的基。习惯上，2-圈图也称为双圈图。不难发现，双圈图有两种类型的基：D
(p
, ℓ,q
)和θ
(r
,s
,t
)，如图1所示。设C
和C
是两个顶点不相交的圈，路P
=v
v
…v
，u
∈V
(C
)，v
∈V
(C
)。D
(p
, ℓ,q
)是分别将 和v
粘合成同一个顶点，v
和v
粘合成同一个顶点所得的图。θ
(r
,s
,t
)是将三条内部不相交的路P
，P
和P
的起点和终点分别粘合所得的图。同样不难发现，3-圈图有8种不同类型的基，记作T
,...,T
，如图2所示。
图1 双圈图的基
图2 3-圈图的基
例2.2
引理2.3
情形1
子情形1.2 c()≥3
如果在G
的圈上存在一点x
，满足x
∉V
(G
[C
,C
])，则G
-x
包含两个顶点相交的圈C
和C
，不满足定理1.9的条件（1）。否则，G
中的每个圈都是G
[C
,C
]的子图。这意味着G
[C
,C
]包含3-圈图的基T
(j
= 5,…, 8)（见图2）作为子图。因而，在G
的圈上一定存在一个顶点x
，使得G
x
- 中有两个顶点相交的圈，不满足定理1.9的条件（1），该情形得证。情形2
情形3
E
(T
)≠∅；否则G
是由顶点互不相交的圈和孤立点构成，m
(T
=m
([T
])=0，矛盾。进一步地，可以断言：T
的每个最大匹配至少覆盖一个悬挂点。否则，T
的直径路中一定包含一条M
-增广路，与引理1.7矛盾。注意到，G
不含悬挂点，则T
的悬挂点在G
中对应一个悬挂圈，记其中一个悬挂圈为C
，记C
上度为3的顶点为v
。子情形3.1
子情形3.2
定理2.4
证明
c
(G
)+1，命题得证。
图3
定理2.5
k
,k
,k
是非负整数，令k
=k
+k
+k
，，l
= 3k
+2k
，则l
可以取[ 0,3k
]中除1之外的任意整数，命题得证。