On the acyclic disconnection of multipartite tournaments

详细信息    查看全文

• 作者：A.P. Figueroa^a ; B. Llano^b ; M. Olsen^a ; ^{olsen@matem.unam.mx} ; E. Rivera-Campo^b
• 关键词：Multipartite tournaments ; Acyclic disconnection ; Regular bipartite tournaments
• 刊名：Discrete Applied Mathematics
• 出版年：2012
• 出版时间：July, 2012
• 年：2012
• 卷：160
• 期：10-11
• 页码：1524-1531
• 全文大小：233 K

文摘

The acyclic disconnection of a digraph is the maximum number of components that can be obtained by deleting from the set of arcs of an acyclic subdigraph. We give bounds for the acyclic disconnection of strongly connected bipartite tournaments and of regular bipartite tournaments. For the latter case, we exhibit an infinite family of tournaments with acyclic disconnection equal to 4.