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

Abstract

top
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 - a r c (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.

How to cite

top

Hortensia 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. [1] J. Bang-Jensen and G. Gutin, Digraphs. Theory, Algorithms and Applications (Springer-Verlag, 2002). Zbl1001.05002
  2. [2] C. Berge, Graphs (North-Holland, Amsterdam, New York, 1985). 
  3. [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. [4] R.A. Brualdi and H.J. Ryser, Combinatorial Matrix Theory (Encyclopedia of Mathematics and its Applications) (Cambridge University Press, 1991). 
  5. [5] R. Diestel, Graph Theory 3rd Edition (Springer-Verlag, Heidelberg, New York, 2005). 
  6. [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. [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. [8] M. Kwaśnik, On (k,l)-kernels on graphs and their products, Doctoral dissertation, Technical University of Wroc aw, Wroc aw, 1980. 
  9. [9] M. Kwaśnik, The generalizaton of Richardson's theorem, Discuss. Math. 4 (1981) 11-14. 
  10. [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. [11] A. Sánchez-Flores, A counterexample to a generalization of Richardson's theorem, Discrete Math. 65 (1987) 319-320. 
  12. [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. [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. [14] J. Von Neumann and O. Morgenstern, Theory of Games and Economic Behavior (Princeton University Press, Princeton, 1953). Zbl0053.09303
  15. [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. 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.