3
$\begingroup$

Given a connected graph $G =(V_1,V_2,E)$, such that there are no edges among the vertices in set $V_1$, however the other set $V_2$ can have edges in itself. There is actually a restriction for $V_2$, which is that we cannot remove any vertex in $V_2$ such that graph $G$ is still connected. Therefore a minimality constraint is there for $V_2$. Is there a standard name for this graph?

The need for it is because im writing a manuscript which includes a result on such graphs and i need to refer this graph with some name. So, i was wondering if there was some name for it. Obviously i couldn't find it. Any other suggestion/comment is also appreciated.

$\endgroup$
  • $\begingroup$ there is actually a restriction for $V_2$, which is that we cannot remove any vertex in $V_2$ such that graph G is still connected. Therefore a minimality constraint is there for $V_2$. $\endgroup$ – singhsumit Jul 12 '11 at 16:33
  • 2
    $\begingroup$ Add that restriction into the question. $\endgroup$ – Dave Clarke Jul 12 '11 at 17:04
  • $\begingroup$ So in other words the vertex set can be partitioned into a stable set and a set of cut-vertices? $\endgroup$ – Andrew D. King Jul 12 '11 at 20:03
  • $\begingroup$ @Andrew.. yes... the set $V_1$ is independent set and every vertex of $V_2$ is a cut vertex. When forming largest independent set, some of the vertices in $V_2$ $may$ join the vertices of $V_1$ to form that. $\endgroup$ – singhsumit Jul 13 '11 at 5:26
2
$\begingroup$

Well, split graphs correspond to the case where $V_1$ is an independent set and $V_2$ forms a clique, but I'm not aware of another name in the case where $V_2$ has no particular restriction.

$\endgroup$
  • $\begingroup$ there is actually a restriction for $V_2$, which is that we cannot remove any vertex in $V_2$ such that graph G is still connected. Therefore a minimality constraint is there for $V_2$. $\endgroup$ – singhsumit Jul 12 '11 at 16:32

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.