1
$\begingroup$

While studying chordal bipartite graphs, I have come across weakly simplicial vertices. I have searched for some time to understand what a weakly simplicial vertex is but I haven't succeeded.

A simplicial vertex is a vertex whose neighborhood induces a clique.

So, what is the weak form of this definition?

$\endgroup$
  • $\begingroup$ Where did you see this? $\endgroup$ – holf Jan 17 '17 at 16:35
4
$\begingroup$

According to the 59th slide of the following pdf:

https://grow2015.sciencesconf.org/file/174789 (A talk by D.Kratsch at GROW 2015)

we have that

A vertex in a graph is weakly simplicial if its neighborhood is an independent set and the neighborhoods of its neighbors form a chain under inclusion.

See the slide for an illustration. The context where this definition is found in the slides is chordal bipartite graphs, so I guess this might be what you are looking for.

$\endgroup$
  • 2
    $\begingroup$ Observe that the hypergraph defined by a chordal bipartite graph is what is called a $\beta$-hypergraph. In this case then, taking the definition found by @a-sh, a weakly simplicial vertex $x$ is also called nested point or $\beta$-leaf (the edges of the hypergraph containing $x$ are ordered by inclusion) : see arxiv.org/abs/1403.7076. Such vertices are used to characterized $\beta$-acyclicity of hypergraphs or chordality of bipartite graphs: a bipartite graph $(X,Y,E)$ is chordal iff you can iteratively remove weakly simplicial vertices from $X$, until $X$ becomes empty. $\endgroup$ – holf Jan 18 '17 at 13:42
  • $\begingroup$ @A.Sh Thank you very much. It is what I am looking for. $\endgroup$ – Gunelle Jan 22 '17 at 9:47
  • 1
    $\begingroup$ @A.Sh However, does chain under inclusion mean the chain is formed by the neighborhood of the weakly simplicial vertex and the neighborhood of its neighbors? $\endgroup$ – Gunelle Jan 22 '17 at 10:17
  • 1
    $\begingroup$ As far as I can parse the definition, let $u$ be a weakly simplicial vertex. Then the components of the chain are the neighborhoods of neighbors of $u$, i.e. if $\{v_i\}$ is the neighborhood of $u$, and $V_i$ denote the neighborhood of each $v_i$, then the set $\{V_i\}$ (ordered appropriately) should be a chain under inclusion. $\endgroup$ – A.Sh Jan 22 '17 at 10:39
  • 1
    $\begingroup$ I think that the top vertices in the figure in the slide are supposed to be weakly simplicial. Let's enumerate the top vertices $s_1,s_2$ etc. from left to right, and the bottom ones $f_1,f_2$ etc. from left to right. The neighborhood of, say, $s_1$, is $\{f_1,f_2,f_3\}$. Then the corresponding neighborhoods, let's call them $F_1$ through $F_3$, are $F_1=\{s_1,s_2\}$, $F_2=\{s_1,s_2,s_3\}$ and $F_3=\{s_1,s_2,s_3,s_4\}$. Clearly $F_1 \subset F_2 \subset F_3$, and so $s_1$ is weakly simplicial. $\endgroup$ – A.Sh Jan 22 '17 at 12:00

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.