几类乘积图的圈覆盖

文献［１］提出猜想：每个２─连通ｎ阶简单图都有一个圈覆盖Ｃ，使得｜ｃ｜≤（２ｎ－１）／３。此猜想至今尚未完全证实。本文对路、圈、完全图的若干笛卡尔乘积图和张量乘积图证实了猜想是正确的。     

关于图的圈覆盖

Ａ．Ｉｔａｌ和Ｍ．Ｒｏｄｅｈ给出了两个关于图的圈覆盖的猜想：（ｉ）任意２－边连通图Ｇ＝（Ｖ，Ｅ）有困覆盖Ｃ，使ｌ（Ｃ）≤｜Ｅ｜＋｜Ｖ｜－１；（ｎ）任意２－边连通图有困覆盖，使图的每条边至多被覆盖两次．本文证明了猜想对平面图和２－边连通没有３－边割的图成立，并给出了一与两猜想等价的条件．同时也对著名的２－圈覆盖猜想作了讨论．     

完全图Kn的8长圈最小覆盖设计

首先对所需要的小阶数w构作其最小覆盖设计,然后应用递归构造给出了任意v≡w（mod 16）的最小覆盖设计,从而证明了对任意正整数v完全图Kv的8长圈最小覆盖设计的存在性.     

P4-等可覆盖的路和圈及M3-等可覆盖的路和圈

若图G的每个极小H-覆盖都是它的最小H-覆盖,则称图G为H-等可覆盖.P3-等可覆盖图和M2-等可覆盖图的特征已经被刻画.主要刻画P4-等可覆盖路,P4-等可覆盖圈,M3-等可覆盖路和M3-等可覆盖圈的特征.     

覆盖数C（m＋5,m）的确定

完全有向对称图ＤＫ的覆盖数Ｃ（ｖ，ｍ）是指能覆盖ＤＫｖ的ｍ长圈的最小圈数。本文给出了Ｃ（ｍ＋５，ｍ）的值，从而将偶长圈覆盖问题压缩到ｍ＋６≤ｖ≤２ｍ－４。     

自反的定向4—圈最小覆盖设计

主要构作了一个自反的定向4-圈的最小覆盖设计。     

笛卡尔乘积图的k-路点覆盖

对于一个图G和一个正整数k,若图G中任意一条阶数为k的路都至少包含集合S⊆V(G)中的一个顶点,那么集合S就为图G的一个k-路点覆盖。最小的k-路点覆盖基数记为ψ_k(G),为图G的k-路点覆盖数。研究圈图分别与圈图、完全图及完全二部图做笛卡尔乘积图的k-路点覆盖,得到ψ_k(G)相关的精确值和上下界。     

完全有向图的奇长圈覆盖问题

给出了完全有向图ＤＫｖ的覆盖数Ｃ（ｖ，ｍ）ｖ＝ｍ＋５，２ｍ－３且ｍ是大于１的奇数。当ｍ·Ｔ（ｖ，ｍ）－ｖ（ｖ－１）时，给出了Ｃ（ｖ，ｍ）的下界。     

广义Petersen图的最小点覆盖集

点覆盖问题是一个著名的NP完全问题.本文对广义Petersen图P(n,2)的精确最小点覆盖数进行研究,讨论并证明了广义Petersen图P(n,2)的最小点覆盖数,给出了最小点覆盖集的构造方法.     

完全多部图的G-填充和覆盖

设图G是由P4带一条悬边所组成的五点四边图，本文确定了完全图Kv和完全多部图Kn(t)的图G填充数和覆盖数。