0
$\begingroup$

The usual definition of a vertex-induced subgraph goes like this:

A vertex-induced subgraph1 is a subset of the vertices of a graph $G$ together with any edges with both endpoints in this subset.

For itself a subgraph is just a graph which can be embedded into some other graphs which it is a subgraph of.

I wonder if the following weaker (and more general) definition of a subgraph has been investigated before (and been found fruitful):

A vertex-induced subgraph2 is a subset of the vertices of a graph $G$ together with any edges with at least one endpoint in this subset.

In the case of directed graphs, this definition gives rise to interesting features a subgraph2 $G_2$ can have, but not a a subgraph1. These features have to do with the existence of input and output nodes:

  • $i$ is an input node of $G_2$ when there is an edge $(n,i)$ in $G_2$ with node $n$ not in $G_2$

  • $o$ is an output node of $G_2$ when there is an edge $(o,n)$ in $G_2$ with node $n$ not in $G_2$.

An interesting feature might be being a source/sink, i.e. not containing an input/output node.

Of course, a subgraph2 is not a graph according to the standard definition of a graph. But it would be equivalent to an "input/output graph" which can be defined as a graph together with two functions $in$ and $out$ assigning to each vertex a number of (virtual) input and output edges.

Once again my question:

Has the above definition of subgraphs2 been investigated before?

Alternatively: Has the above definition of input/output graphs been investigated before?

If so, under which name?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Not an answer if your question is contrued strictly, yet the following two things are tagentially relevant: (1) it is very usual to consider boundaries of vertex sets, in the sense of sets of edges with exactly one end in the given vertex set, and of course you can cobble together a "definition" from this concept of 'boundary' and the usual 'ordinary subgraph'. (2) when working with e.g. string diagrams and operads, a concept of half-edges exists. I have not seen your idea addressed as such. $\endgroup$
    – Peter Heinig
    Commented Aug 10, 2017 at 18:22
  • 1
    $\begingroup$ A related definition which is a graph, and a problem which is not completely trivial involving that definition". * Define a "1-indirect vertex induced subgraph of graph $G = (V,E)$ induced by $U\subset V$ to have edge-set $F$ of exactly those edges with at least one vertex in $U$, and vertex set $W$ consisting of those vertices touched by a member of $F$. * The nontrivial problem is: Find a graph $G$ and subset $U$ of its vertices such that the 1-indirect vertex-induced subgraph of $G$ by $U$ has greater chromatic number than that of the vertex-induced subgraph of $G$ by $U$. $\endgroup$
    – Mark Fischler
    Commented Aug 10, 2017 at 18:50

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .