Abstract
Let D=(V,A) be a digraph with minimum indegree at least one and girth at least k, where k⩾2 is an integer. In this paper , the following results were proved. A digraph D has a (k,l)-kernel if and only if its line digraph L(D) does, and the number of (k,l)-kernels in D is equal to the number of (k,l)-kernels in L(D), where 1⩽l<k. As a consequence, previous results about k-kernels in the line digraphs were gained.
Similar content being viewed by others
References
Berge C. Graphs [M]. North-Holland, Amsterdam, 1985.
von Neumann J V, Morgenstern O. Theory of Games and Economic Behavior[M]. Princeton University Press, Princeton, NJ, 1944.
Berge C. Ramachandra Rao A. A combinatorial problem in logic[J]. Discrete Math., 1977, 17: 23–26.
Haynes T W, Hedetniemi S T, Slater P J. Domination in Graphs Advanced Topics [M]. Marcel Dekker, New York, 1998.
Kwaśnik M. The generalization of Richardson theorem [J]. Discussiones Math., 1981, IV: 11–14.
Galeana-Sánchez H. On the existence of(k,l)-kernels in digraphs[J]. Discrete Math., 1990, 85: 99–102.
Galeana-Sánchez H. On the existence of kernels and k-kernels in directed graphs [J]. Discrete Math., 1992, 110: 251–255.
Galeana-Sánchez H, Li Xue-liang. Semikernels and (k,l)-kernels in digraphs [J]. SIAM J. Discrete Math., 1998, 11: 340–346.
Galeana-Sánchez H, Rincón-Mejia H A. A sufficient condition for the existence of k-kernels in digraphs[J]. Discussiones Mathematicae Graph Theory, 1998, 18: 197–204.
Harminc M. Solutions and kernels of a directed graph[J]. Math. Slovaca, 1982, 32: 263–267.
Shan Er-fang, Kang Li-ying, Lu Qin. k-semikernels, k-quasikernels, k-kernels in digraphs and their line digraphs [A]. Utilitas Mathematica (to appear).
Author information
Authors and Affiliations
Additional information
Project supported by National Natural Science Foundation of China(Grant No. 10571117)
About this article
Cite this article
Lu, Q., Shan, Ef. & Zhao, M. (k,l)-kernels in line digraphs. J. of Shanghai Univ. 10, 484–486 (2006). https://doi.org/10.1007/s11741-006-0042-5
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/s11741-006-0042-5