论文标题
双顶点拆下双面图
Vertex removal in biclique graphs
论文作者
论文摘要
\ textit {biclique}是最大诱导的完整二分子子图。图$ h $的\ textit {biclique graph}，用$ kb（h）$表示，是$ h $的所有比克利物中的交叉图。在这项工作中，我们解决了以下问题：给定二比图$ g = kb（h）$，是否有可能删除$ g $的顶点$ q $ q $，以便$ g - \ {q \ {q \} $是biclique图？如果可能的话，我们可以获得一个图$ h'$，以便$ g - \ {q \} = kb（h'）$？我们表明，总体问题有一个“否”答案。但是，我们证明，如果$ g $具有顶点$ q $，以便$ d（q）= 2 $，那么$ g - \ {q \} $是一个biclique图，我们展示了如何获得$ h'$。
A \textit{biclique} is a maximal induced complete bipartite subgraph. The \textit{biclique graph} of a graph $H$, denoted by $KB(H)$, is the intersection graph of the family of all bicliques of $H$. In this work we address the following question: Given a biclique graph $G=KB(H)$, is it possible to remove a vertex $q$ of $G$, such that $G - \{q\}$ is a biclique graph? And if possible, can we obtain a graph $H'$ such that $G - \{q\} = KB(H')$? We show that the general question has a "no" for answer. However, we prove that if $G$ has a vertex $q$ such that $d(q) = 2$, then $G-\{q\}$ is a biclique graph and we show how to obtain $H'$.
