Premium
On claw‐free M ‐oriented critical kernel‐imperfect digraphs
Author(s) -
GaleanaSánchez H.
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199601)21:1<33::aid-jgt4>3.0.co;2-n
Subject(s) - combinatorics , digraph , mathematics , diagonal , conjecture , chord (peer to peer) , kernel (algebra) , directed graph , discrete mathematics , computer science , geometry , distributed computing
A kernel of a digraph D is an independent and dominating set of vertices of D . A chord of a directed cycle C = (0, 1,…, n , 0) is an arc ij of D not in C with both terminal vertices in C . A diagonal of C is a chord ij with j ≠ i − 1. Meyniel made the conjecture (now know to be false) that if D is a diagraph such that every odd directed cycle has at least two chords then D has a kernel. Here we obtain some properties of claw‐free M ‐oriented critical kernel‐imperfect digraphs. As a consequence we show that if D is an M ‐oriented K 1,3 ‐free digraph such that every odd directed cycle of length at least five has two diagonals then D has a kernel. © 1996 John Wiley & Sons, Inc.