Skip to main content
Springer Nature Link
Log in

(k,l)-kernels in line digraphs

  • Applied Mathematics And Mechanics
  • Published:
Journal of Shanghai University (English Edition)

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Berge C. Graphs [M]. North-Holland, Amsterdam, 1985.

    Google Scholar 

  2. von Neumann J V, Morgenstern O. Theory of Games and Economic Behavior[M]. Princeton University Press, Princeton, NJ, 1944.

    Google Scholar 

  3. Berge C. Ramachandra Rao A. A combinatorial problem in logic[J]. Discrete Math., 1977, 17: 23–26.

    Article  MATH  MathSciNet  Google Scholar 

  4. Haynes T W, Hedetniemi S T, Slater P J. Domination in Graphs Advanced Topics [M]. Marcel Dekker, New York, 1998.

    Google Scholar 

  5. Kwaśnik M. The generalization of Richardson theorem [J]. Discussiones Math., 1981, IV: 11–14.

    Google Scholar 

  6. Galeana-Sánchez H. On the existence of(k,l)-kernels in digraphs[J]. Discrete Math., 1990, 85: 99–102.

    Article  MATH  MathSciNet  Google Scholar 

  7. Galeana-Sánchez H. On the existence of kernels and k-kernels in directed graphs [J]. Discrete Math., 1992, 110: 251–255.

    Article  MATH  MathSciNet  Google Scholar 

  8. Galeana-Sánchez H, Li Xue-liang. Semikernels and (k,l)-kernels in digraphs [J]. SIAM J. Discrete Math., 1998, 11: 340–346.

    Article  MATH  MathSciNet  Google Scholar 

  9. 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.

    MATH  MathSciNet  Google Scholar 

  10. Harminc M. Solutions and kernels of a directed graph[J]. Math. Slovaca, 1982, 32: 263–267.

    MATH  MathSciNet  Google Scholar 

  11. 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).

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, College of Sciences, Shanghai University, 200444, Shanghai, P.R. China

    Lu Qin, Shan Er-fang Ph. D. (Assoc. Prof.) & Zhao Min

Authors
  1. Lu Qin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shan Er-fang Ph. D.
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Zhao Min
    View author publications

    You can also search for this author in PubMed Google Scholar

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

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11741-006-0042-5

Key words

2000 Mathematics Subject Classification

Search

Navigation