# Cyclically k-partite digraphs and k-kernels

Hortensia Galeana-Sánchez; César Hernández-Cruz

Discussiones Mathematicae Graph Theory (2011)

- Volume: 31, Issue: 1, page 63-78
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topHortensia Galeana-Sánchez, and César Hernández-Cruz. "Cyclically k-partite digraphs and k-kernels." Discussiones Mathematicae Graph Theory 31.1 (2011): 63-78. <http://eudml.org/doc/270876>.

@article{HortensiaGaleana2011,

abstract = {Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively.
A (k,l)-kernel N of D is a k-independent set of vertices (if u,v ∈ N then d(u,v) ≥ k) and l-absorbent (if u ∈ V(D)-N then there exists v ∈ N such that d(u,v) ≤ l). A k-kernel is a (k,k-1)-kernel. A digraph D is cyclically k-partite if there exists a partition $\{V_i\}_\{i = 0\}^\{k-1\}$ of V(D) such that every arc in D is a $V_i V_\{i+1\}-arc$ (mod k). We give a characterization for an unilateral digraph to be cyclically k-partite through the lengths of directed cycles and directed cycles with one obstruction, in addition we prove that such digraphs always have a k-kernel. A study of some structural properties of cyclically k-partite digraphs is made which bring interesting consequences, e.g., sufficient conditions for a digraph to have k-kernel; a generalization of the well known and important theorem that states if every cycle of a graph G has even length, then G is bipartite (cyclically 2-partite), we prove that if every cycle of a graph G has length ≡ 0 (mod k) then G is cyclically k-partite; and a generalization of another well known result about bipartite digraphs, a strong digraph D is bipartite if and only if every directed cycle has even length, we prove that an unilateral digraph D is bipartite if and only if every directed cycle with at most one obstruction has even length.},

author = {Hortensia Galeana-Sánchez, César Hernández-Cruz},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {digraph; kernel; (k,l)-kernel; k-kernel; cyclically k-partite; -kernel; -kernel; cyclically -partite},

language = {eng},

number = {1},

pages = {63-78},

title = {Cyclically k-partite digraphs and k-kernels},

url = {http://eudml.org/doc/270876},

volume = {31},

year = {2011},

}

TY - JOUR

AU - Hortensia Galeana-Sánchez

AU - César Hernández-Cruz

TI - Cyclically k-partite digraphs and k-kernels

JO - Discussiones Mathematicae Graph Theory

PY - 2011

VL - 31

IS - 1

SP - 63

EP - 78

AB - Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively.
A (k,l)-kernel N of D is a k-independent set of vertices (if u,v ∈ N then d(u,v) ≥ k) and l-absorbent (if u ∈ V(D)-N then there exists v ∈ N such that d(u,v) ≤ l). A k-kernel is a (k,k-1)-kernel. A digraph D is cyclically k-partite if there exists a partition ${V_i}_{i = 0}^{k-1}$ of V(D) such that every arc in D is a $V_i V_{i+1}-arc$ (mod k). We give a characterization for an unilateral digraph to be cyclically k-partite through the lengths of directed cycles and directed cycles with one obstruction, in addition we prove that such digraphs always have a k-kernel. A study of some structural properties of cyclically k-partite digraphs is made which bring interesting consequences, e.g., sufficient conditions for a digraph to have k-kernel; a generalization of the well known and important theorem that states if every cycle of a graph G has even length, then G is bipartite (cyclically 2-partite), we prove that if every cycle of a graph G has length ≡ 0 (mod k) then G is cyclically k-partite; and a generalization of another well known result about bipartite digraphs, a strong digraph D is bipartite if and only if every directed cycle has even length, we prove that an unilateral digraph D is bipartite if and only if every directed cycle with at most one obstruction has even length.

LA - eng

KW - digraph; kernel; (k,l)-kernel; k-kernel; cyclically k-partite; -kernel; -kernel; cyclically -partite

UR - http://eudml.org/doc/270876

ER -

## References

top- [1] J. Bang-Jensen and G. Gutin, Digraphs. Theory, Algorithms and Applications (Springer-Verlag, 2002). Zbl1001.05002
- [2] C. Berge, Graphs (North-Holland, Amsterdam, New York, 1985).
- [3] C. Berge and P. Duchet, Recent problems and results about kernels in directed graphs, Discrete Math. 86 (1990) 27-31, doi: 10.1016/0012-365X(90)90346-J. Zbl0721.05027
- [4] R.A. Brualdi and H.J. Ryser, Combinatorial Matrix Theory (Encyclopedia of Mathematics and its Applications) (Cambridge University Press, 1991).
- [5] R. Diestel, Graph Theory 3rd Edition (Springer-Verlag, Heidelberg, New York, 2005).
- [6] H. Galeana-Sánchez, On the existence of kernels and h-kernels in directed graphs, Discrete Math. 110 (1992) 251-255, doi: 10.1016/0012-365X(92)90713-P. Zbl0770.05050
- [7] M. Kucharska and M. Kwaśnik, On (k,l)-kernels of special superdigraphs of Pₘ and Cₘ, Discuss. Math. Graph Theory 21 (2001) 95-109, doi: 10.7151/dmgt.1135.
- [8] M. Kwaśnik, On (k,l)-kernels on graphs and their products, Doctoral dissertation, Technical University of Wroc aw, Wroc aw, 1980.
- [9] M. Kwaśnik, The generalizaton of Richardson's theorem, Discuss. Math. 4 (1981) 11-14.
- [10] M. Richardson, On weakly ordered systems, Bull. Amer. Math. Soc. 52 (1946) 113-116, doi: 10.1090/S0002-9904-1946-08518-3. Zbl0060.06506
- [11] A. Sánchez-Flores, A counterexample to a generalization of Richardson's theorem, Discrete Math. 65 (1987) 319-320.
- [12] W. Szumny, A. Włoch and I. Włoch, On (k,l)-kernels in D-join of digraphs, Discuss. Math. Graph Theory 27 (2007) 457-470, doi: 10.7151/dmgt.1373. Zbl1142.05040
- [13] W. Szumny, A. Włoch and I. Włoch, On the existence and on the number of (k,l)-kernels in the lexicographic product of graphs, Discrete Math. 308 (2008) 4616-4624, doi: 10.1016/j.disc.2007.08.078. Zbl1169.05039
- [14] J. Von Neumann and O. Morgenstern, Theory of Games and Economic Behavior (Princeton University Press, Princeton, 1953). Zbl0053.09303
- [15] A. Włoch and I. Włoch, On (k,l)-kernels in generalized products, Discrete Math. 164 (1997) 295-301, doi: 10.1016/S0012-365X(96)00064-7.

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.