Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm considering a problem on random graphs, where it makes sense to look the edges which "touch" a connected component, but which do not belong to it.

Consider a fixed graph $G$, where as usual we interpret edges $e \in E(G)$ as unordered pairs, that is $E(G) \subseteq \binom{V(G)}{2}$; and consider a connected subgraph $H \subset G$. One class of edges of the sort which touch the subgraph $H$ is the edge boundary of $H$ in $G$, of edges which are incident both to $V(H)$ and its complement:

$$ \partial (H) \;=\; \Bigl\{ e \in E(G) \;\Big|\; e \not\subset V(H) ~~\&~~ e \notin E(G \smallsetminus V(H)) \Bigr\} .$$

Obviously, $\partial (H)$ is a set of edges which do not belong to the induced graph $H$, nor even to the induced subgraph $G[V(H)]$.

Question. I'm interested in a sort of complementary notion: the set of edges which are in the induced subgraph $G[V(H)]$, but which still do not belong to $H$. That is, $$C (H) \;=\; \Bigl\{ e \in E(G) \;\Big|\; e \subset V(H) ~~\&~~ e \notin E(H) \Bigr\}.$$ Does this set have an established name in the literature?

I use the notation $C(H)$ above because it seems a natural generalization of the notion of a chord of a cycle; by definition, $H$ is a chordless cycle in $G$ if and only if $H$ is a cycle for which $C(H) = \varnothing$. However, the definition of $C(H)$ above also applies naturally to spanning trees of graphs: for a spanning tree $T \subset G$, we have $C(T) = E(G) \smallsetminus E(T)$.

A reference to one or more papers in the literature to attest to the definition, and the terminology, would also be nice.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.