Back
 OJDM  Vol.12 No.3 , July 2022
3-Anti-Circulant Digraphs Are α-Diperfect and BE-Diperfect
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 blocking odd cycles. In this paper, we verified both conjectures for 3-anti-circulant digraphs. We also present some structural results for α-diperfect and BE-diperfect digraphs.
Cite this paper: Freitas, L. and Lee, O. (2022) 3-Anti-Circulant Digraphs Are α-Diperfect and BE-Diperfect. Open Journal of Discrete Mathematics, 12, 29-46. doi: 10.4236/ojdm.2022.123003.
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.

 
 
Top