Download PDF - (k,l)-kernels, (k,l)-semikernels, k-Grundy functions and duality for state splittingsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

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

Authors 1, 1

Affiliations

  1. Instituto de Matemáticas de la Universidad Nacional Autónoma de México, Circuito Exterior, Ciudad Universitaria C.P. 04510, México D.F. México

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.

Keywords

ENG
state splitting, line digraph, kernel, Grundy function, duality

Bibliography

  1. C. Berge, Graphs (North-Holland, Amsterdam, 1985).
  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.
  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.
  4. H. Galeana-Sánchez and Xueliang Li, Semikernels and (k,l)-kernels in digraphs, SIAM J. Disc. Math. 11 (1998) 340-346.
  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. 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.
  7. M. Harminc, Solutions and kernels of a directed graph, Math. Slovaca 32 (1982) 263-267.
  8. B. Kitchens, Symbolic dynamics. One-sided, two-sided and countable state Markov shifts (Springer-Verlag, 1998).
  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. 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. 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. D. Lind and B. Marcus, An introduction to symbolic dynamics and coding (Cambridge University Press, 1995), doi: 10.1017/CBO9780511626302.
  13. V. Neumann-Lara, Seminuclei of a digraph, (Spanish) An. Inst. Mat. Univ. Nac. Autónoma México 11 (1971) 55-62.
Discussiones Mathematicae Graph Theory
2007/27/2
Export to PBN, Opens in new tab
Pages:
359-371
Main language of publication
English
Received
2006-05-19
Accepted
2006-11-30
Published
2007

DOI: 10.7151/dmgt.1367

Exact and natural sciences