競賽圖中的完美對集

高強(qiáng)

（山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山西 太原 030006）

競賽圖中的完美對集

高強(qiáng)

（山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山西 太原 030006）

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

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

0 引言

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

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

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

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

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

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

1 預(yù)備工作

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

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

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

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

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

2 主要結(jié)果

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

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

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

對于x∈S，有

因?yàn)閙 是正整數(shù)，所以｜N＋（S）｜≥｜S｜，

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

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

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

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

容易證明T是正則的.考慮頂點(diǎn)v的內(nèi)鄰集N＋（v）和外鄰集N-（v）.頂點(diǎn)集｜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為公共頂點(diǎn)的有向生成三角形集.但是利用定理1還可以驗(yàn)證當(dāng)刪除u，v時，新形成的競賽圖T′是正則競賽圖，而且對于任意的S是U的子集時，存在正整數(shù)m＝2，3，4，使得

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

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

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

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

［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

高強(qiáng)（1987-），男，山東臨沂人，碩士研究生，研究領(lǐng)域：圖論及其應(yīng)用.E-mail：luomu789＠126.com