Open Journal of Discrete Mathematics

Volume 12, Issue 3 (July 2022)

ISSN Print: 2161-7635   ISSN Online: 2161-7643

Google-based Impact Factor: 0.39  Citations  

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

HTML  XML Download Download as PDF (Size: 733KB)  PP. 29-46  
DOI: 10.4236/ojdm.2022.123003    196 Downloads   657 Views  Citations

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.

Share and Cite:

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.

Copyright © 2025 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.