Vertex removal in biclique graphs

DOI10.1016/J.DAM.2022.06.001MaRDI QIDQ2091812zbMATH OpenOpenAlexFDO

Authors Leandro Montero

Publication date 2 November 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.04583

zbMATH Keywords

intersection graphsvertex removalbicliquesbiclique graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Paths and cycles (05C38) Graph operations (line graphs, products, etc.) (05C76)

Abstract: A extit{biclique} is a maximal induced complete bipartite subgraph. The extit{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^{\prime }$ such that $G-q=KB(H^{\prime })$? 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^{\prime }$.

Recommendations

• Structural properties of biclique graphs and the distance formula
• Biclique graphs and biclique matrices
• Biclique graph of bipartite permutation graphs
• Biclique graphs of interval bigraphs
• Almost every graph is divergent under the biclique operator

Cites work

• A characterization of clique graphs
• A partial characterization of clique graphs
• Algorithm Theory - SWAT 2004
• Biclique graph of bipartite permutation graphs
• Biclique graphs and biclique matrices
• Biclique graphs of interval bigraphs
• On the iterated biclique operator
• Practical graph isomorphism. II.
• Structural properties of biclique graphs and the distance formula
• Sur deux propriétés des classes d'ensembles
• The complexity of clique graph recognition

Cited in

(7)

• Biclique graphs of interval bigraphs
• scientific article; zbMATH DE number 5354839 (Why is no real title available?)
• Biclique graph of bipartite permutation graphs
• On some conjectures on biclique graphs
• Modifying a graph using vertex elimination
• The number of convergent graphs under the biclique operator with no twin vertices is finite
• Structural properties of biclique graphs and the distance formula

Describes a project that uses

Uses Software

• Traces
• nauty

This page was built for publication: Vertex removal in biclique graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2091812)