Point- and arc-reaching sets of vertices in a digraph

MaRDI QIDQ3560719zbMATH OpenFDO

Authors K. A. Germina, Kumar Abhishek, Thomas Zaslavsky, B. D. Acharya, S. B. Rao

Publication date 14 May 2010

Full work available at URL https://arxiv.org/abs/1001.4213

zbMATH Keywords

arc-basisdigraphpoint-basisreachability

Mathematics Subject Classification ID

Signed and weighted graphs (05C22)

Abstract: In a digraph $D=(X,mathcalU)$, not necessarily finite, an arc $(x,y)inmathcalU$ is reachable from a vertex $u$ if there exists a directed walk $W$ that originates from $u$ and contains $(x,y)$. A subset $SsubseteqX$ is an arc-reaching set of $D$ if for every arc $(x,y)$ there exists a diwalk $W$ originating at a vertex $uinS$ and containing $(x,y)$. A minimal arc-reaching set is an arc-basis. $S$ is a point-reaching set if for every vertex $v$ there exists a diwalk $W$ to $v$ originating at a vertex $uinS$. A minimal point-reaching set is a point-basis. We extend the results of Harary, Norman, and Cartwright on point-bases in finite digraphs to point- and arc-bases in infinite digraphs.

Recommendations

• Hypergraphs of minimal arc bases in a digraph
• Arc dimension of a digraph
• Reachability relations and the structure of transitive digraphs
• Reachability problems in edge-colored digraphs
• Domination in digraphs

Cited in

(3)

• Hypergraphs of minimal arc bases in a digraph
• An Application of Arc-Reaching Sets in Social-Network Analysis
• Arc dimension of a digraph

This page was built for publication: Point- and arc-reaching sets of vertices in a digraph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3560719)