Following the lines of this question Need help with Graph notation for a subgraph , I am trying to define the subset of vertices connected to a specific vertex $v_i$ and need some help working through this process.

In that example the question and answer are using: $$ W_{v_i} = \{v \in V(G) \mid \{v,v_j\} \in E(G)\} $$

First, is it possible to use $V_{v_i}$ instead of $W_{v_i}$ since it is a subset of V based on $v_i$?

Second, for a directed graph, the ordering of the vertices in an edge matter, so would it be correct to use $v_j$ explicitly in set $V(G)$, and $v_i$ to be the first value in the set $E(G)$ so it corresponds with $V_{v_i}$: $$ V_{v_i} = \{v_j \in V(G) \mid \{v_i,v_j\} \in E(G)\} $$

Finally, the other question also defines the edges of a subgraph, although the answer also states there is no convention. From what I can find, the way to define a subgraph is $G[S]$.

Then can there be an edge induced subgraph $G_{v_i}$ defined as:

$G_{v_i} = G[E_{v_i}]$ where $E_{v_i} = \{e \in E(G) \mid v_i \in e\}$

Meaning the subgraph is composed of only the vertices and edge connected to $v_i$. Then to make a subgraph of only the directed edges that move away from $v_i$ (meaning $v_i$ is the starting vertex):

$G_{v_i} = G[E_{v_i}]$ where $E_{v_i} = \{e_{ij} \in E(G) \mid (v_i,v_j) \in e_{ij}\}$


1 Answer 1


$V_a$ = { v : {a,v} in E } is the set of vertices directly connected to a.
For directed graphs, there are three such sets,
$V_a$ = { v : (a,v) in E }, $W_a$ = { v : (v,a) in E }, $V_a \cup W_a.$

$G_a$ = ({ v : {a,v} in E }, { {a,v} : {a,v} in E })
The outgoing from a graph is
$G_a$ = ({ v : (a,v) in E }, { (a,v) : (a,v) in E })


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.