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.

Improve this question
$\endgroup$
4
  • $\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, 2011 at 16:33
  • 2
    $\begingroup$ Add that restriction into the question. $\endgroup$
    – Dave Clarke
    Jul 12, 2011 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, 2011 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, 2011 at 5:26

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\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, 2011 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.