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?

Improve this question
$\endgroup$
1
  • $\begingroup$ Where did you see this? $\endgroup$
    – holf
    Jan 17, 2017 at 16:35

1 Answer 1

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

Improve this answer
$\endgroup$
8
  • 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, 2017 at 13:42
  • $\begingroup$ @A.Sh Thank you very much. It is what I am looking for. $\endgroup$
    – Gunelle
    Jan 22, 2017 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, 2017 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$
    – MonadBoy
    Jan 22, 2017 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$
    – MonadBoy
    Jan 22, 2017 at 12:00

Your Answer

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

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