全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

3-Anti-Circulant Digraphs Are α-Diperfect and BE-Diperfect

DOI: 10.4236/ojdm.2022.123003, PP. 29-46

Keywords: 3-Anti-Circulant Digraph, Diperfect Digraph, Berge’s Conjecture, Begin-End Conjecture

Full-Text   Cite this paper   Add to My Lib

Abstract:

Let D be a digraph. A subset S of V (D) is a stable set if every pair of vertices in S is non-adjacent in D. A collection of disjoint paths \"\" is a path partition of D, if every vertex in V (D) is in exactly one path of \"\".?We say that a stable set S and a path partition \"\" are orthogonal if each path of \"\" contains exactly one vertex of S. A digraph D satisfies the α-property if for every maximum stable set S of D, there exists a path partition \"\" such that S and \"\" are orthogonal. A digraph D is α-diperfect if every induced subdigraph of D satisfies the α-property. In 1982, Berge proposed a characterization for α-diperfect digraphs in terms of forbidden anti-directed odd cycles. In 2018, Sambinelli, Silva and Lee proposed a similar conjecture. A digraph D satisfies the Begin-End-property or BE-property if for every maximum stable set S of D, there exists a path partition \"\" such that 1) S and \"\" are orthogonal and 2) for each path P \"\", either the start or the end of P belongs to S. A digraph D is BE-diperfect if every induced subdigraph of D satisfies the BE-property. Sambinelli, Silva and Lee proposed a characterization for BE-diperfect digraphs in terms of forbidden

References

[1]  Bang-Jensen, J. and Gutin, G.Z. (2008) Digraphs: Theory, Algorithms and Applications. Springer Monographs in Mathematics. Springer, London.
https://doi.org/10.1007/978-1-84800-998-1
[2]  Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory, Volume 244 of Graduate Texts in Mathematics. Springer London, New York.
https://doi.org/10.1007/978-1-84628-970-5
[3]  Berge, C. (1961) Färbung von graphen, deren sämtliche bzw. deren ungerade kreise starr sind. Wissenschaftliche Zeitschrift.
[4]  Chudnovsky, M., Robertson, N., Seymour, P. and Thomas, R. (2006) The Strong Perfect Graph Theorem. Annals of Mathematics, 51-229.
https://doi.org/10.4007/annals.2006.164.51
[5]  Berge, C. (1981) Diperfect Graphs. 1-8.
https://doi.org/10.1007/BFb0092250
[6]  Hartman, I.B.-A. (2006) Berge’s Conjecture on Directed Path Partitions—A Survey. Discrete Mathematics, 306, 2498-2514.
https://doi.org/10.1016/j.disc.2005.12.039
[7]  Sambinelli, M. and Lee, O. (2018) Partition Problems in Graphs and Digraphs. Ph.D. Thesis, University of Campinas, Campinas.
[8]  Sambinelli, M., da Silva, C.N. and Lee, O. (2022) α-Diperfect Digraphs. Discrete Mathematics, 345, 112759.
https://doi.org/10.1016/j.disc.2021.112759
[9]  Freitas, L.I.B. and Lee, O. (2021) Some Results on Berge’s Conjecture and Begin-End Conjecture. arXiv: 2111.12168.
[10]  Wang, R.X. (2014) Cycles in 3-Anti-Circulant Digraphs. Australasian Journal of Combinatorics, 60, 158-168.

Full-Text

comments powered by Disqus

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133