
doi: 10.1137/080728470
Summary: The Gallai-Milgram theorem asserts that the vertex set of any digraph with stability number \(k\) can be partitioned into \(k\) directed paths. Hahn and Jackson conjectured that, for any positive integer \(k\), there exists a digraph with stability number \(k\) such that the subdigraph obtained by deleting any \(k-1\) directed paths still has stability number \(k\). They established the existence of such digraphs for \(k=1,2,3\). Here, we construct examples for arbitrarily large values of \(k\).
path deletion, conjecture, Graph operations (line graphs, products, etc.), Directed graphs (digraphs), tournaments, stability number, digraph, antichain, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), transversal, Paths and cycles, lexicographic product, directed path
path deletion, conjecture, Graph operations (line graphs, products, etc.), Directed graphs (digraphs), tournaments, stability number, digraph, antichain, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), transversal, Paths and cycles, lexicographic product, directed path
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
