Can anyone please tell me how are these graphs called in english?

  1. If we can divide a set of graph vertices in two disjoint sub sets, such as all edges connect vertices only inside these sub sets? How are those graphs called?

  2. The property of graph is called......, if for every graph G we can say that this graph has this property if subgraph G - v, v in G(V) has this property.

I just need to these words in english, so i can google them. There is very little material on those things in language I study in.

  • $\begingroup$ In (1) are all the vertices in a subset connected to each other by an edge or it is not allowed for a pair of vertices in the same subset to be not adjacent? If the first case you have a union of two complete graphs, in the second case the only thing you can say is that the graph is disconnected. $\endgroup$ – Shahab Oct 20 '13 at 9:52
  • $\begingroup$ The only thing that is not allowed in the (1) is that vertices, that are in different subsets, are not connected $\endgroup$ – Jevgenijs Strigins Oct 20 '13 at 10:06
  • $\begingroup$ In that case any disconnected graph fits your description. $\endgroup$ – Shahab Oct 20 '13 at 10:10

I'm not sure if these are what you are looking for, but seem relevant:

I hope this helps $\ddot\smile$


If the vertex set of a graph can be partitioned into two subsets $V=V_1 \cup V_2$ such that no edge is from a vertex in $V_1$ to a vertex in $V_2$, then the graph is said to be disconnected. The graph then has at least two connected components, and it has exactly two connected components if the two induced subgraphs $G[V_1]$ and $G[V_2]$ are connected.

A hereditary property is a property of a graph that holds for all induced subgraphs of $G$, whereas you are looking for a property that holds only for certain kinds of induced subgraphs of $G$, namely all the vertex-deleted subgraphs $G-v$. I don't know off-hand if there is a name for such a property.


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.