2
$\begingroup$

A subgraph is called spanning when it includes all of the vertices of the given graph.

Is there a term for a subgraph which includes all the edges of a graph?

Thanks.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

If the subgraph includes all edges of the original graph, then it also includes all its vertices, except maybe some with degree $0$.

The minimal such subgraph is the graph in which all $0$-degree vertices were removed. It is called the $1$-core of the graph, a very special case of $k$-core.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Why do you have to remove all the vertices of degree 0? If you only remove some of the vertices of degree 0 then it still contains all the edges. $\endgroup$
    – Gordon Royle
    Commented Jan 14, 2021 at 3:41
  • 1
    $\begingroup$ Indeed! I thought we were talking of the minimal such subgraph, but this is not in the question. The original graph itself actually is one such subgraph. I edited the answer to make this clear, thanks. $\endgroup$
    – Matthieu Latapy
    Commented Jan 14, 2021 at 6:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .