Intersection properties of maximal directed cuts in digraphs

详细信息    查看全文

• 作者：G. Chiaselotti ; ^{giampiero.chiaselotti@unical.it" class="auth_mail" title="E-mail the corresponding author} ; T. Gentile ^{gentile@mat.unical.it" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Directed cuts ; Digraphs ; Maximal paths ; Cycles
• 刊名：Discrete Mathematics
• 出版年：2017
• 出版时间：6 January 2017
• 年：2017
• 卷：340
• 期：1
• 页码：3171-3175
• 全文大小：387 K

文摘

If class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302242&_mathId=si1.gif&_user=111111111&_pii=S0012365X16302242&_rdoc=1&_issn=0012365X&md5=d772421c2bb2de0ac7c57d7dd7c72061" title="Click to view the MathML source">Dclass="mathContainer hidden">class="mathCode">$D$ is a finite digraph, a directed cut is a subset of arcs in class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302242&_mathId=si1.gif&_user=111111111&_pii=S0012365X16302242&_rdoc=1&_issn=0012365X&md5=d772421c2bb2de0ac7c57d7dd7c72061" title="Click to view the MathML source">Dclass="mathContainer hidden">class="mathCode">$D$ having tail in some subset class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302242&_mathId=si3.gif&_user=111111111&_pii=S0012365X16302242&_rdoc=1&_issn=0012365X&md5=6f9b65066860be9988428d7e70c9982e" title="Click to view the MathML source">X⊆V(D)class="mathContainer hidden">class="mathCode">$X\subseteq V\left(D\right)$ and head in class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302242&_mathId=si4.gif&_user=111111111&_pii=S0012365X16302242&_rdoc=1&_issn=0012365X&md5=0ee020a239f915c9e3d8702e71e1f1b4" title="Click to view the MathML source">V(D)∖Xclass="mathContainer hidden">class="mathCode">$V\left(D\right)\setminus X$. In this paper we prove two general results concerning intersections between maximal paths, cycles and maximal directed cuts in class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302242&_mathId=si1.gif&_user=111111111&_pii=S0012365X16302242&_rdoc=1&_issn=0012365X&md5=d772421c2bb2de0ac7c57d7dd7c72061" title="Click to view the MathML source">Dclass="mathContainer hidden">class="mathCode">$D$. As a direct consequence of these results, we deduce that there is a path, or a cycle, in class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302242&_mathId=si1.gif&_user=111111111&_pii=S0012365X16302242&_rdoc=1&_issn=0012365X&md5=d772421c2bb2de0ac7c57d7dd7c72061" title="Click to view the MathML source">Dclass="mathContainer hidden">class="mathCode">$D$ that crosses each maximal directed cut.