4
$\begingroup$

$H$ is a supergraph of $G$ if it can be obtained from $G$ by adding, edges, vertices, or both.

Is there a standard terminology for a graph that can be obtained from $G$ only by adding edges?

$\endgroup$
  • $\begingroup$ Sometimes it's called a closure (e.g. the transitive closure is a special case of a supergraph $H$ obtained only adding edges). However the term is only applied when you are adding all edges in order to obtain a property of the graph, so I don't think it is used as a generic term. $\endgroup$ – Bakuriu Jul 4 '16 at 11:09
3
$\begingroup$

If $H$ is made by adding only edges to $G$, then $G$ is a spanning subgraph of $H$. However, I'm not aware of any way of phrasing it that makes $H$ the subject of the sentence.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ "spanned supergraph" ​ ? ​ ​ ​ ​ $\endgroup$ – user12859 Jul 29 '16 at 17:02
3
$\begingroup$

In graph modification algorithms, a graph $H$ is called a completion of $G$ if there exists a set of edges $F \subseteq [V(G)]^2$ such that $G+F \cong H$.

You can search on arxiv for examples such as

See also:

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

We often think of a graph as the set of its edges, the vertex set being fixed. This is not a universal point of view, but is common enough. In that case you can just write $H \supseteq G$, and say that $H$ is a supergraph of $G$. Just make sure that you explain what you mean by these notations.

Generally speaking, subgraph is ambiguous — it's not clear whether you're allowed to remove vertices. Supergraph is somewhat less common, and suffers from similar ambiguity. Whenever a notion is ambiguous, and you are worried that the reader won't be able to guess correctly from context, you should explain clearly what you mean, humpty-dumpty style.

| cite | improve this answer | |
$\endgroup$

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.