Discussiones Mathematicae Graph Theory 27(2) (2007) 359-371
doi: 10.7151/dmgt.1367

[BIBTex] [PDF] [PS]

(k,l)-KERNELS, (k,l)-SEMIKERNELS, k-GRUNDY FUNCTIONS AND DUALITY FOR STATE SPLITTINGS

Hortensia Galeana-Sánchez  and  Ricardo Gómez

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: state splitting, line digraph, kernel, Grundy function, duality.

2000 Mathematics Subject Classification: 05C20.

References

[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 Pm and Cm, 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.

Received 19 May 2006
Revised 30 November 2006
Accepted 30 November 2006