(k,l)-kernels, (k,l)-semikernels, k-Grundy functions and duality for state splittings

Hortensia Galeana-Sánchez; Ricardo Gómez

Discussiones Mathematicae Graph Theory (2007)

  • Volume: 27, Issue: 2, page 359-371
  • ISSN: 2083-5892

Abstract

top
Line digraphs can be obtained by sequences of state splittings, a particular kind of operation widely used in symbolic dynamics [12]. Properties of line digraphs inherited from the source have been studied, for instance in [7] Harminc showed that the cardinalities of the sets of kernels and solutions (kernel's dual definition) of a digraph and its line digraph coincide. We extend this for (k,l)-kernels in the context of state splittings and also look at (k,l)-semikernels, k-Grundy functions and their duals.

How to cite

top

Hortensia Galeana-Sánchez, and Ricardo Gómez. "(k,l)-kernels, (k,l)-semikernels, k-Grundy functions and duality for state splittings." Discussiones Mathematicae Graph Theory 27.2 (2007): 359-371. <http://eudml.org/doc/270592>.

@article{HortensiaGaleana2007,
abstract = {Line digraphs can be obtained by sequences of state splittings, a particular kind of operation widely used in symbolic dynamics [12]. Properties of line digraphs inherited from the source have been studied, for instance in [7] Harminc showed that the cardinalities of the sets of kernels and solutions (kernel's dual definition) of a digraph and its line digraph coincide. We extend this for (k,l)-kernels in the context of state splittings and also look at (k,l)-semikernels, k-Grundy functions and their duals.},
author = {Hortensia Galeana-Sánchez, Ricardo Gómez},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {state splitting; line digraph; kernel; Grundy function; duality},
language = {eng},
number = {2},
pages = {359-371},
title = {(k,l)-kernels, (k,l)-semikernels, k-Grundy functions and duality for state splittings},
url = {http://eudml.org/doc/270592},
volume = {27},
year = {2007},
}

TY - JOUR
AU - Hortensia Galeana-Sánchez
AU - Ricardo Gómez
TI - (k,l)-kernels, (k,l)-semikernels, k-Grundy functions and duality for state splittings
JO - Discussiones Mathematicae Graph Theory
PY - 2007
VL - 27
IS - 2
SP - 359
EP - 371
AB - Line digraphs can be obtained by sequences of state splittings, a particular kind of operation widely used in symbolic dynamics [12]. Properties of line digraphs inherited from the source have been studied, for instance in [7] Harminc showed that the cardinalities of the sets of kernels and solutions (kernel's dual definition) of a digraph and its line digraph coincide. We extend this for (k,l)-kernels in the context of state splittings and also look at (k,l)-semikernels, k-Grundy functions and their duals.
LA - eng
KW - state splitting; line digraph; kernel; Grundy function; duality
UR - http://eudml.org/doc/270592
ER -

References

top
  1. [1] C. Berge, Graphs (North-Holland, Amsterdam, 1985). 
  2. [2] M. Boyle and R. Wagoner, Positive algebraic K-theory and shifts of finite type. Modern dynamical systems and applications (Cambridge University Press, 2004) 45-66. Zbl1148.37303
  3. [3] H. Galeana-Sánchez, On the existence of (k,l)-kernels in digraphs, Discrete Math. 85 (1990) 99-102, doi: 10.1016/0012-365X(90)90167-G. Zbl0729.05020
  4. [4] H. Galeana-Sánchez and Xueliang Li, Semikernels and (k,l)-kernels in digraphs, SIAM J. Disc. Math. 11 (1998) 340-346. Zbl0907.05025
  5. [5] H. Galeana-Sánchez, L. Pastrana Ramí rez and H.A. Rincón Mejí a, Semikernels, quasikernels and Grundy functions in the line digraph, SIAM J. Disc. Math. 4 (1991) 80-83. Discrete Math. 59 (1986) 257-265. 
  6. [6] R. Gómez, Positive K-theory for finitary isomorphisms of Markov chains, Ergodic Theory and Dynam. Systems. 23 (2003) 1485-1504, doi: 10.1017/S0143385702001700. Zbl1060.37007
  7. [7] M. Harminc, Solutions and kernels of a directed graph, Math. Slovaca 32 (1982) 263-267. Zbl0491.05029
  8. [8] B. Kitchens, Symbolic dynamics. One-sided, two-sided and countable state Markov shifts (Springer-Verlag, 1998). Zbl0892.58020
  9. [9] M. Kwaśnik, On the (k,l)-kernels, Graph Theory ( agów, 1981), 114-121, Lecture Notes in Math., 1018 (Springer, Berlin, 1983). 
  10. [10] M. Kwaśnik, A. Włoch and I. Włoch, Some remarks about (k,l)-kernels in directed and undirected graphs, Discuss. Math. 13 (1993) 29-37. 
  11. [11] 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. 
  12. [12] D. Lind and B. Marcus, An introduction to symbolic dynamics and coding (Cambridge University Press, 1995), doi: 10.1017/CBO9780511626302. Zbl1106.37301
  13. [13] V. Neumann-Lara, Seminuclei of a digraph, (Spanish) An. Inst. Mat. Univ. Nac. Autónoma México 11 (1971) 55-62. Zbl0286.05113

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.