Independent sets which meet all longest paths
type: Item
instance of: scholarly article
title: Independent sets which meet all longest paths
zbMATH Open document ID: 0856.05045
DOI: 10.1016/0012-365X(94)00261-G
author: Hortensia Galeana-Sánchez
author: Hugo Alberto Rincón-Mejía
published in: Discrete Mathematics
publication date: 1996-07-07T00:00:00Z
review text: A directed graph is said to have property \(P\) if it contains an independent set which meets every longest directed path. In 1982, \textit{J. M. Laborde}, \textit{Ch. Payan} and \textit{Nguyen Huy Xuong} [Teubner-Texte Math. 59, 173-177 (1983; Zbl 0528.05034)] conjectured that every directed graph has property \(P\). In this paper, the authors prove some sufficient conditions for a directed graph to have property \(P\).
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 897573
zbMATH Keywords: property \(P\)
zbMATH Keywords: independent set
zbMATH Keywords: longest directed path
MaRDI profile type: Publication
cites work: Q4099676
cites work: Une généralisation du théorème de Richardson sur l'existence de noyaux dans les graphes orientes
cites work: On kernels and semikernels of digraphs
cites work: On kernel-perfect critical digraphs
cites work: Q5545303
cites work: Maximal chains and antichains
cites work: Q3309863
cites work: Nombre chromatique et plus longs chemins d'un graphe
full work available at URL: 0012-365x(94)00261-g
OpenAlex ID: W2117884707
Recommended article: Shortest Paths between Shortest Paths and Independent Sets
Recommended article: Stable set meeting every longest path
Recommended article: Q5395438
Recommended article: Smallest sets of longest paths with empty intersection
Recommended article: Independence equivalence classes of paths
Recommended article: Long path lemma concerning connectivity and independence number
Recommended article: Q3199444
Recommended article: Independent sets in graphs
Recommended article: Intersection of longest paths in a graph
Recommended article: Independent sets and non-augmentable paths in generalizations of tournaments
description: scientific article; zbMATH DE number 897573