pith. sign in

arxiv: 0712.0663 · v1 · submitted 2007-12-05 · 🧮 math.CO

Quasi-kernels and quasi-sinks in infinite graphs

classification 🧮 math.CO
keywords pointquasi-kerneldirectedgraphgraphsinducedinfinitequasi-sink
0
0 comments X
read the original abstract

Given a directed graph G=(V,E) an independent set A of the vertices V is called quasi-kernel (quasi-sink) iff for each point v there is a path of length at most 2 from some point of A to v (from v to some point of A). Every finite directed graph has a quasi-kernel. The plain generalization for infinite graphs fails, even for tournaments. We investigate the following conjecture here: for any digraph G=(V,E) there is a a partition (V_0,V_1) of the vertex set such that the induced subgraph G[V_0] has a quasi-kernel and the induced subgraph G[V_1] has a quasi-sink.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.