多部競賽圖中包含在一些圈中的頂點
2016-07-10 08:07:53梁素萍
電子技術與軟件工程 2016年8期
1 引言及預備知識
本文所采用的符號和術語可參考文獻[1]， 所涉及的圖為無重弧和環的有向圖。一個多部競賽圖或c-部競賽圖是一個完全c-部圖的定向。設D是一個有向圖，我們用V（D）表示它的頂點集。若xy是D中的一條弧，我們說x控制y，記為x→y。對于V（D）的兩個子集 X和Y，若X的每個頂點控制Y的任意頂點，我們說X控制Y，記為X→Y。稱一個有向圖D是強聯通的，若對于D中任意兩頂點u和v，都存在一條從u到v的路。有向圖D的一個圈稱為哈密爾頓的，若它包含D所有的頂點。
參考文獻
[1]Bang-Jensen J，Gutin G. Digraph：Theory，Algorithms and Applications[M].London：Springer， 2000.
[2]Goddard W.D，Oellermann O.R.On the cycle structure of multipartite tournaments.Graph Theory， Combinatorics and Applications[M]. New York：Wiley-Interscience，1991， vol.1：525-533.
[3]Guo Y，Volkmann L.Extendable cycles in semicomplete multipartite digraphs. Graphs Combin[J]，2004（20）：185-190.
[4]Volkmann L.A remark on cycles through an arc in strongly connected multipartite tournaments.Appl.Math. Lett[J]，2007（20）：1148-1.
作者簡介
梁素萍（1966-）女，山西省大同市人。大學本科學歷。現為山西傳媒學院副教授。主要研究方向為基礎數學。
作者單位
山西傳媒學院 山西省晉中市 030619
