高強

（山西大學 數學科學學院，山西 太原 030006）

競賽圖中的完美對集

高強

（山西大學 數學科學學院，山西 太原 030006）

Lichiardopol在離散數學-競賽圖中經過給定的0，1，2個公共頂點的圈一文中提出以下兩個公開問題；對于階為2n＋1的正則競賽圖T，（a）對任意的一個頂點w，是否存在n個有向三角形Ti生成T，且使得V（Ti）∩V（Tj）＝w（1≤i＜j≤n）是正確的.（b）是否存在一個頂點w，使得存在n個有向三角形Ti生成T，且使得V（Ti）∩V（Tj）＝w（1≤i＜j≤n）是正確的.文章擴充了滿足條件的圖類.

正則競賽圖；有向生成三角形集；完美對集

0 引言

設D＝（V，A）是有向圖，V和A分別是有向圖的頂點集和弧集，｜V（D）｜稱為D的階.對于任意的v∈V（D），用N＋（v），N-（v）分別代表v的外鄰集和內鄰集.定義d＋（v）＝｜N＋（v）｜，d-（v）＝｜N-（v）｜.設S?V（D），D 中由頂點集S 誘導生成的子圖，記作D［S］.用N＋（v；D′）和 N-（v；D′），（N＋（v；W），N-（v；W））表示v在D′（D［W］）中的外鄰集和內鄰集.N＋（S；D′）和 N-（S；D′），（N＋（S；W），N-（S；W））表示頂點集S在D′（D［W］）中的外鄰集和內鄰集.

設有向圖D，其中w∈V（D）.如果存在n個有向三角形Ti生成T，且V（Ti）∩V（Tj）＝w，（1≤i≤j≤n），那么我們說D有以w為公共頂點的有向生成三角形集.

設U，V是有向圖D 的兩個不相交的頂點集.稱M是（U，V）間的對集，如果對任意的（u，v）∈M，滿足u∈U，v∈V，M 記為（U，V）-對集.當｜U｜＋｜V｜＝V（D）且｜U｜＝｜V｜＝｜M｜時，稱M 為（U，V）-完善對集.

完全圖的定向圖稱為競賽圖.設T是競賽圖，對于任意的w∈V（T）如果滿足d＋（w）＝d-（w），那么稱T是正則的.顯然可見，若T是階為2n＋1的正則競賽圖，那么對于任意的w∈V（T）我們都有d＋（w）＝d-（w）＝n.

在本文中僅考慮幾類正則競賽圖.

且文中所涉及的圖論概念和記號，可參閱文獻［1-2］.

1 預備工作

引理1 （Hall’s smarriagetheorem）［3］設G是具有二分類（U，V）的偶圖，則G包含飽和U 每個頂點的對集，當且僅當，｜N（S）｜≥｜S｜對所有 ?≠S?U，成立.

在有向圖中應用引理1，可以立即得到下面推論.

推論1 設D是二部有向圖，其兩部頂點集分別為U，V，那么D具有（U，V）-完美對集當且僅當｜N＋（S）｜≥｜S｜對任意的?≠S?U 都成立.

引理2 設T是階為2n＋1的競賽圖，其中w∈V（T），那么存在以w為公共頂點生成三角集的充要條件是存在（N＋（w），N-（w））-完美對集.

證明 設T是階為2n＋1的競賽圖，其中w∈V（T），如果w是生成三角集｛Ti｝的公共頂點，那么弧集｛Ti＼w｝恰為（N＋（w），N-（w））-完美對集.反之，若 M 是（N＋（w），N-（w））-完美對集，由于T 是競賽圖，明顯的頂點w和對集M 中的弧誘導出D中有一個以w為公共頂點的有向生成三角形集.

2 主要結果

定理1設T 是階為2n＋1的正則競賽圖，w∈T 是一個頂點，U＝N＋（w）＝｛u1，u2，…，un｝，V＝N-（w）＝｛v1，v2，…，vn｝，若恰好存在一個整數m 滿足

那么T中存在完美對集M.

證明設（S?U）是任意子集，m是任意一個正整數.

對于x∈S，有

因為m 是正整數，所以｜N＋（S）｜≥｜S｜，

由于S是U任意子集，根據推論1，得T中存在完美對集M.

推論2設T 是階為2n＋1的正則競賽圖，w∈T 是一個頂點，U＝N＋（w）＝｛u1，u2，…，un｝，V＝N-（w）＝｛v1，v2，…，vn｝，其中S是U 任意子集.若恰好存在一個整數m 滿足

那么T中存在以w為公共頂點的有向生成三角形集.

在頂點集V（T′）∪｛u，v｝上定義正則競賽圖T如下：

容易證明T是正則的.考慮頂點v的內鄰集N＋（v）和外鄰集N-（v）.頂點集｜V（S1）｜＝3但是N＋（V（S1，N-（v））＝U∪｛u｝，即｜N＋（V（S1，N-（v））｜＝2.則｜N＋（V（S1，N-（v））｜≤｜V（S1）｜.由于定理1知T中不存在（N＋（v），N-（v））-完美對集.由引理3知T中不存在以v為公共頂點的有向生成三角形集.但是利用定理1還可以驗證當刪除u，v時，新形成的競賽圖T′是正則競賽圖，而且對于任意的S是U的子集時，存在正整數m＝2，3，4，使得

所以T′存在完美對集M 而且存在以w為公共頂點的有向生成三角形集.

定理3設T是階為2n＋1的正則競賽圖，w∈T 是一個頂點，U＝N＋（w）＝｛u1，u2，…，un｝，V＝N-（w）＝｛v1，v2，…，vn｝，其中S是U任意子集.若T同構于下面定義的集族Qn，則T中存在完美對集M的充要條件是T中存在以w為公共頂點的有向生成三角形集.

證明定義Qn集族是具有如下性質的正則競賽圖的圖類：對于任意的Q∈Qn，存在一個頂點x∈Q，使.對于頂點ui控制頂點＝1，2，…，n），下標的獲得通過mol（n）.根據定理1容易驗證，對于每一對不同的整數i，j，ui，jj控制住的頂點可以不同，可以選擇正整數m使得m＝n-2，滿足

此時，Q中存在著完美對集M且Q中存在著以w為公共頂點的有向生成三角形集.

［1］ Bang-Jensen J，Gutin G.Digraphs［M］.New York：Springer，2002.

［2］ Chartrand G，Lesniak G.Graphs and Digraphs［M］.London：Chapman and Hall，1996.

［3］ Hall P.On Representatives of Subsets［J］.LondonMathSoc，1935，10：559-575.

［4］ Imrich W，Klav?ar S.Product Graphs：Structure and Recognition［M］.New York：Wiley，2002.

［5］ Lichiardopol N.Cycles in a Tournament with Pairwise Zero，One or Tow Given Vertices in Common［J］.DiscreteMath，2008，308：763-771.

［6］ Lutz.Volkmann.Multipartite Tournaments：A Survey［J］.DiscreteMath，2008，307：3097-3129.

Perfect Matching in Tournaments and Dynamic Boundary

GAO Qiang
（SchoolofMathematicalSciences，ShanxiUniversity，Taiyuan030006，China）

Lichiardopol raised an open problems in his article“Cycles in a tournament with pairwise zero one or tow given vertices in common”，Discrete Math：For regular tournaments of order 2n＋1.（a）Is it true that for any vertexw，there existntrianglesTispanningTand such that：V（Ti）∩V（Tj）＝xfor 1≤i≤j≤n.（b）Is there a vertexwsuch that there existntrianglesTispanningTand such that：V（Ti）∩V（Tj）＝xfor 1≤i≤j≤n.In this paper，the results extend the conditions for the problems.

regular tournaments；spanning directed triangles；perfect matching

O157.5

A

0253-2395（2011）S2-0012-03

2011-08-11

高強（1987-），男，山東臨沂人，碩士研究生，研究領域：圖論及其應用.E-mail：luomu789＠126.com