0
$\begingroup$

By definitions, both ' induced sub graph ' and ' partial graph' seem to be the same. But these two terms often confuse me as why two different terminologies to mean a same stuff? In the following, $H$ is an induced sub graph (partial graph) of $G$:enter image description here

Edited: A sub graph $G_1=(V_1, E_1)$ of $G_2=(V_2, E_2)$ is called a partial graph of $G_2$ if $E_1$ consists of edges in $G_2$ whose joining vertices are in $V_1$. I found this definition from a source but couldn't get it to cite now.

$\endgroup$
2
  • 2
    $\begingroup$ What does the term "partial graph" mean? I've never seen or heard it. $\endgroup$
    – saulspatz
    Commented Mar 1, 2019 at 15:52
  • 1
    $\begingroup$ Are you translating from a language other than English? "Partial graph" sounds like it might be a literal translation of the term some other language used for "subgraph" (that is, not necessarily an induced one). $\endgroup$
    – hmakholm left over Monica
    Commented Mar 1, 2019 at 17:50

1 Answer 1

Reset to default
1
$\begingroup$

If $H$ is an induced subgraph of $G$, then part of what that means is that there is is an injection $\alpha$ from $V(H)$ (the set of $H$'s vertices) to $V(G)$, and that for every edge $h_1h_2$ of $H$, $\alpha(h_1)\alpha(h_2)$ is an edge in $G$. But it also means that if $h_1, h_2$ are vertices of $H$ and $H$ does not have an edge $h_1h_2$, then $\alpha(h_1)\alpha(h_2)$ is not an edge in $G$.

IME the adjective "induced" is used before the name of a graph rather than some subgraph $H$ of another graph $G$ with all $H$'s vertices already labelled with some of $G$'s vertices' labels. We use phrases such as "induced 4-cycle" -- which does not presuppose any prior correspondence between the 4-cycle's vertices and 4 of $G$'s vertices.

To come back to your example, $G$ does indeed have an induced copy of your $H$. But consider the statement "$G$ has an induced 4-cycle". It does, but $befc$ would not be an example. This is because $G$ has the edge $ce$, which joins two of the 4-cycle's vertices but is not an edge of that cycle. ($G$ has induced 4-cycles such as $adfe$. For $adfe$ to qualify, not only must $G$ have all its 4 edges, $G$ must also lack edges $af$ and $de$.)

$\endgroup$
4
  • 2
    $\begingroup$ The injection $\alpha$ is convenient to have for technical reasons, but I think it's more intuitive to say that an "induced subgraph" is what you get by taking some of the vertices of $G$ together with all the edges that connect two of the chosen vertices, whereas for a plain "subgraph" you take some of the vertices and some of the edges that connect two of the chosen vertices. $\endgroup$
    – hmakholm left over Monica
    Commented Mar 1, 2019 at 17:53
  • $\begingroup$ @Rosie F well, it's interesting. So, can we said to have induced 1-cycle (if loops are allowed) and is it possible to have induced 2-cycle? Or induced 3-cycle is the smallest possible? $\endgroup$
    – gete
    Commented Mar 1, 2019 at 18:30
  • $\begingroup$ A 3-cycle is the complete graph $K_3$. So any 3-cycle of a graph $G$ is an induced 3-cycle. I'm not sure about induced 2-cycles because in order to have 2-cycles at all you must allow multiple edges between the same two vertices, and I'm not familiar with the conventions there. (Perhaps "induced 2-cycle $aba$" means that there are exactly 2 edges, no more, between $a$ and $b$?) $\endgroup$
    – Rosie F
    Commented Mar 1, 2019 at 18:35
  • $\begingroup$ @Henning Makholm yes you are right, this is exactly what i am considering here as an induced sub graph. So, would you confirm that $H$ is an induced sub graph of $G$ in the above example ? $\endgroup$
    – gete
    Commented Mar 1, 2019 at 18:38

You must log in to answer this question.

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