# What is a weakly-simplicial vertex?

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?

• Where did you see this?
– holf
Commented Jan 17, 2017 at 16:35

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.

• 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.
– holf
Commented Jan 18, 2017 at 13:42
• @A.Sh Thank you very much. It is what I am looking for. Commented Jan 22, 2017 at 9:47
• @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? Commented Jan 22, 2017 at 10:17
• 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. Commented Jan 22, 2017 at 10:39
• 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. Commented Jan 22, 2017 at 12:00