Some new families of KP-digraphs

Articles in Press

Document Type : Original paper

Authors

1 Facultad de Ciencias, Universidad Nacional Autónoma de México, Ciudad de México, México

2 Instituto de Matemáticas, Universidad Nacional Autónoma de México, Ciudad de México, México

Abstract

A kernel $N$ of a digraph $D$ is an independent set of vertices that is absorbent (for every vertex $u\in V(D)\setminus N$, there is a vertex $v\in N$ such that $(u,v)\in A(D)$). Let $D$ be a digraph such that every proper induced subdigraph has a kernel. If $D$ has a kernel, then $D$ is a \emph{kernel perfect digraph} (KP-digraph); otherwise, $D$ is a \emph{critical kernel imperfect digraph} (CKI-digraph). A digraph with the property $P$ is a digraph such that whenever a vertex reaches two other vertices through asymmetrical arcs, then these two vertices have the same out-neighborhood. In particular, digraphs whose asymmetrical part is a disjoint union of cycles have the property $P$.   In this work, KP-digraphs with the property $P$ are characterized. As a consequence, KP-digraphs whose asymmetrical part is a Hamiltonian cycle are also characterized. For digraphs with a Hamiltonian cycle $\gamma$ as their asymmetrical part and whose diagonals are symmetrical of length 2, two algorithms are presented;  the first one determines whether a digraph is a KP-digraph or a CKI-digraph, and the second constructs the kernel of the original digraph if it is a KP-digraph. As a consequence, a characterization of all CKI-digraphs whose asymmetrical part is a Hamiltonian cycle and whose diagonals are symmetrical of length 2 is shown.

Keywords

Main Subjects

References

[1] A. Apartsin, E. Ferapontova, and V. Gurvich, A circular graph-counterexample to the duchet kernel conjecture, Discrete Math. 178 (1998), no. 1-3, 229–231.
https://doi.org/10.1016/S0012-365X(97)81830-4
[2] J. Bang-Jensen, Y. Guo, G.Z. Gutin, and L. Volkmann, A classification of locally semicomplete digraphs, Discrete Math. 167-168 (1997), 101–114.
https://doi.org/10.1016/S0012-365X(96)00219-1
[3] J. Bang-Jensen and G.Z. Gutin, Digraphs: Theory, Algorithms and Applications, Springer Science & Business Media,
2009.
[4] J. Bang-Jensen and G.Z. Gutin, Classes of Directed Graphs, Springer Publishing Company, 2018.
[5] J. Baumgardner, K. Acker, O. Adefuye, and et al., Solving a hamiltonian path problem with a bacterial computer, J. Biol. Eng. 3 (2009), no. 1, Article number: 11.
https://doi.org/10.1186/1754-1611-3-11
[6] C. Berge and P. Duchet, Recent problems and results about kernels in directed graphs., Topics on Domination (S.T. Hedetniemi, ed.), Annals Discrete Mathematics, vol. 48, Elsevier, 1991, pp. 27–31.
[7] E. Boros and V. Gurvich, A corrected version of the duchet kernel conjecture, Discrete Math. 179 (1998), no. 1-3, 231–233.
https://doi.org/10.1016/S0012-365X(97)00094-0
[8] V. Chvátal, On the computational complexity of finding a kernel, Tech. report, Report CRM-300, Centre de Recherches Mathématiques, Université de Montr´eal, 1973.
[9] C. Delorme, Cayley digraphs and graphs, European J. Combin. 34 (2013), no. 8, 1307–1315.
https://doi.org/10.1016/j.ejc.2013.05.013
[10] A.S. Fraenkel, Planar kernel and grundy with $d\le  3, d_{out}\le 2, d_{in}\le 12$ are NP-complete, Discrete Appl. Math. 3 (1981), no. 4, 257–262.
https://doi.org/10.1016/0166-218X(81)90003-2
[11] H. Galeana-Sánchez and V. Neumann-Lara, On kernel-perfect critical digraphs, Discrete Math. 59 (1986), no. 3, 257–265.
https://doi.org/10.1016/0012-365X(86)90172-X
[12] H. Galeana-Sánchez and V. Neumann-Lara, New classes of critical kernel-imperfect digraphs, Discuss. Math. Graph
Theory 18 (1998), no. 1, 85–89.
[13] P. Hell and C. Hernández-Cruz, On the complexity of the 3-kernel problem in some classes of digraphs, Discuss. Math. Graph Theory 34 (2014), no. 1, 167–185.
https://doi.org/10.7151/dmgt.1727
[14] E. J. Kim and R. Williams, Improved parameterized algorithms for above average constraint satisfaction, Parameterized and Exact Computation (Berlin, Heidelberg) (D. Marx and P. Rossmanith, eds.), Springer Berlin Heidelberg, 2012, pp. 118–131.
[15] D. Kühn and D. Osthus, A survey on Hamilton cycles in directed graphs, European J. Combin. 33 (2012), no. 5, 750–766.
https://doi.org/10.1016/j.ejc.2011.09.030
[16] J.M. Le Bars, Counterexamples of the 0-1 law for fragments of existential second-order logic: an overview, Bull. Symb. Log. 6 (2000), no. 1, 67–82.
https://doi.org/10.2307/421076
[17] J.M. Le Bars, The 0-1 law fails for frame satisfiability of propositional modal logic, Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science (USA), IEEE Computer Society, 2002, pp. 225–234.
[18] S.C. Locke and D. Witte, On non-Hamiltonian circulant digraphs of outdegree three, J. Graph Theory 30 (1999), no. 4, 319–331.
[19] J.V. Neumann and O. Morgenstern, Theory of Games and Economic Behavior, Princeton University Press, 1944.
[20] J.M. Steele, Probabilistic algorithm for the directed traveling salesman problem, Math. Oper. Res. 11 (1986), no. 2, 193–384.
https://doi.org/10.1287/moor.11.2.343
[21] J.L. Szwarcfiter and G. Chaty, Enumerating the kernels of a directed graph with no odd circuits, Inform. Process. Lett. 51 (1994), no. 3, 149–153.
https://doi.org/10.1016/0020-0190(94)00072-7
[22] Q.F. Yang, R.E. Burkard, E. Çela, and G.J. Woeginger, Hamiltonian cycles in circulant digraphs with two stripes, Discrete Math. 176 (1997), no. 1-3, 233–254.
https://doi.org/10.1016/S0012-365X(96)00298-1
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 01 August 2024

Files

Share

How to cite

Statistics