點團的橫截與合併問題

Abstract

在一個圖形G 中，一個點團（clique）是一個極大的（maximal ）頂點（vertice ） 集合，其中的元素是兩兩相連（pairwise adjacent ）。點團的橫截問題（clique transversal problem ）是要找一個最小數目的頂點集合而能碰到圖形G 的所有點團 。這個數目被表為τc （G ）。點團的合併問題（clique packing problem）是要找 一個大數目而且由彼此互不相（pairwise disjiont ）之點團所成的族。這個數目被 表為νc （G ）。 這篇論文的主要目的就是要研究點團的橫截和合併問題。首先我們證明點團的橫截問 題和合併問題對分裂圖形而言都是NP-complete 。接下來，我們研究一個圖形G 的τ c －完美性。（即νc （G'）＝τc （G'）對圖形G 中任何的頂點誘導子圖形（ver- tex induced subgraph G' ））。為了求出分裂圖形G 之τc （G ）的上限（upper bound ）。我們重新以超圖形（hypergraph）的語言來看點團的橫截問題。這部分的 主要結果是：一個每邊恰含４點的均勻超圖形（４－uniform hypergraph），它τc 的上限是２（m ＋n ）╱９（m 是邊數，n 是點數）。最後，對於BCC 圖形的點團橫 截問題，我們提供了一個有效率的演算法（algorithm ）BCC 圖形是指一個圖形它的 每一個區組（block ）是一個二部圖（bipartite graph ），或是一個點團，或是一 個循環（cycle ）。