Kernels and partial line digraphs

Let D = ( V , A ) be a digraph with minimum in-degree at least 1 and girth at least l + 1 , where l ≥ 1 . In this work, the following result is proved: a digraph D has a ( k , l ) -kernel if and only if its partial line digraph L D does, where 1 ≤ l < k . As a consequence, the h -iterated line di...

Full description

Saved in:
Bibliographic Details
Published in:Applied mathematics letters 2010-10, Vol.23 (10), p.1218-1220
Main Authors: Balbuena, C., Guevara, M.
Format: Article
Language:English
Subjects:
[formula omitted]-kernel
Applied mathematics
Directed graphs
Exact sciences and technology
Grafs, Teoria de
Kernel
Line digraph
Matemàtica aplicada
Matemàtica discreta
Matemàtiques i estadística
Mathematical analysis
Mathematics
Numerical analysis
Numerical analysis. Scientific computation
Partial line digraph
Sciences and techniques of general use
Teoria de grafs
Àrees temàtiques de la UPC
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let D = ( V , A ) be a digraph with minimum in-degree at least 1 and girth at least l + 1 , where l ≥ 1 . In this work, the following result is proved: a digraph D has a ( k , l ) -kernel if and only if its partial line digraph L D does, where 1 ≤ l < k . As a consequence, the h -iterated line digraph L h ( D ) is shown to have a kernel if and only if D has a kernel.
ISSN:0893-9659
1873-5452
DOI:10.1016/j.aml.2010.06.001