Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.