Quasi-Kernels for Oriented Paths and Cycles

ABSTRACT

If D is a digraph, then K∈V(D) is a quasi-kernel of D if D［K］is discrete and for each y∈V(D)－K there is x∈K such that the directed distance from y to x is less than three. We give formulae for the number of quasi-kernels and for the number of minimal quasi-kernels of oriented paths and cycles.

If D is a digraph, then K∈V(D) is a quasi-kernel of D if D［K］is discrete and for each y∈V(D)－K there is x∈K such that the directed distance from y to x is less than three. We give formulae for the number of quasi-kernels and for the number of minimal quasi-kernels of oriented paths and cycles.

Cite this paper

S. Bowser and C. Cable, "Quasi-Kernels for Oriented Paths and Cycles,"*Open Journal of Discrete Mathematics*, Vol. 2 No. 2, 2012, pp. 58-61. doi: 10.4236/ojdm.2012.22010.

S. Bowser and C. Cable, "Quasi-Kernels for Oriented Paths and Cycles,"

References

[1] V. Chvátal and L. Lovász, “Every Directed Graph Has a Semi-Kernel,” Hypergraph Seminar, Lecture Notes in Mathematics, Vol. 441, Springer-Verlag, Berlin, 1974, p. 175.

[2] G. Gutin, K. M. Koh, E. G. Tay and A. Yeo, “On the Number of Quasi-Kernels in Digraphs,” Journal of Graph Theory, Vol. 46, No. 1, 2004, pp. 48-56. doi:10.1002/jgt.10169

[3] S. Bowser and C. Cable, “At Least Three Minimal Quasi-Kernels,” Discrete Applied Mathematics, Vol. 160, No. 4-5, 2012, pp. 673-675. doi:10.1016/j.dam.2011.08.017

[4] S. Heard and J. Huang, “Disjoint Quasi-Kernels in Digraphs,” Journal of Graph Theory, Vol. 58, No. 3, 2008, pp. 251-260. doi:10.1002/jgt.20310

[1] V. Chvátal and L. Lovász, “Every Directed Graph Has a Semi-Kernel,” Hypergraph Seminar, Lecture Notes in Mathematics, Vol. 441, Springer-Verlag, Berlin, 1974, p. 175.

[2] G. Gutin, K. M. Koh, E. G. Tay and A. Yeo, “On the Number of Quasi-Kernels in Digraphs,” Journal of Graph Theory, Vol. 46, No. 1, 2004, pp. 48-56. doi:10.1002/jgt.10169

[3] S. Bowser and C. Cable, “At Least Three Minimal Quasi-Kernels,” Discrete Applied Mathematics, Vol. 160, No. 4-5, 2012, pp. 673-675. doi:10.1016/j.dam.2011.08.017

[4] S. Heard and J. Huang, “Disjoint Quasi-Kernels in Digraphs,” Journal of Graph Theory, Vol. 58, No. 3, 2008, pp. 251-260. doi:10.1002/jgt.20310