2進一般化de Bruijnグラフのフィードバック頂点集合

摘要

本論文では，2進一般化de BruijnグラフG_B（n，2）の最小フィードバック頂点集合について考察 を行う．頂点数n が3の倍数でないものに対してほ最小フィードバック頂点集合の構成方法を示し，nが3の 倍数のときは下界より1だけ大きいフィードバック頂点集合の構成方法を示す．特にn ＝18，24のときはその フィードバック頂点集合が最小のものであることも示す．また，n ≤ 150に対して計算機実験により得られた最 小フィードバック頂点集合を示す.