Let $G = (V,E)$ be a simple undirected bipartite graph with vertices $V$, edges $E$, and a chosen partition $V = X \cup Y$. Recall that the bipartite complement of $G$ is the graph on the same vertex set as $G$, with the same partition $V = X \cup Y$ of the vertex set, but with edges given by the complement of $E$ in the complete bipartite graph on $X$ and $Y$.
For a vertex $v$, we let $N_v$ denote the (open) neighbourhood of $v$, i.e. those vertices $u \in V$ such that $\{u, v\} \in E$. For a set of vertices $N$, let $E(N)$ be the set of edges incident with some vertex in $N$. If $N = \{v\}$, we write $E_v = E(\{v\}).$ Similarly, we let $\overline{E}(N)$ denote the same notion except that the edges are now taken from the bipartite complement of $G$. Define $\chi \colon E \rightarrow X$ to be the function sending an edge in $E$ to the unique vertex in $X$ it is incident with, and let $\gamma \colon E \rightarrow Y$ be defined similarly.
Consider the following properties of a bipartite graph $G$.
- Connected
- For any $u, v \in V$, the neighbourhood of $u$ is never contained in the neighbourhood of $v$. (Hence, the set consisting of all neighbourhoods of vertices in $G$ forms a clutter or a Sperner family of sets.) In particular, this implies that no two vertices of $G$ have the same neighbourhood, and so $G$ is twin-free.
- For any $x \in X$ and $y \in Y$, one has that except for $I = X - N_{y}$ and $J = Y - N_{x}$, there is no pair $(I,J)$ with $I \subseteq X - N_{y}$ and $J \subseteq Y - N_{x}$ such that $E(Y - N_{x}) \cap \bigcup_{i \in I} E_{i} = E(X - N_{y}) \cap \bigcup_{j \in J} E_{j}$.
- There is no $I \subseteq X$ and $J \subseteq Y \times Y$ such that $\overline{E}(I) \times \gamma(E(I)) = B$ where $B$ is defined as the subset $\{(e,y') \, \lvert \, \chi(e) \in \chi(E(y')) \}$ of $\bigcup_{(y,y') \in J} \overline{E}(y) \times \gamma(E(y')$.
- The same as the condition in the previous item, but with the roles of $X$ and $Y$ exchanged.
These properties are obtained from characterising the vanishing of first Hochschild cohomology with coefficients $A \otimes A$ for quadratic monomial algebras $A$ whose relations correspond to the data of a bipartite graph $G$; see section 4.1 of the following: https://www.sciencedirect.com/science/article/pii/S0022404923002633
I have tried to relate properties 3. - 5. to notions studied in the literature on bipartite graphs, but haven't been able to. For instance, if I recall correctly, property 3. above can be expressed using minors of the adjacency matrix of $G$, but I haven't found anything I can relate this to.
I am wondering about the following:
- Are there existing notions in the literature properties 3.-5. correspond to or can be expressed using?
- How reasonable is it to expect to be able to classify bipartite graphs satisfying properties 1. - 5. into a finite set of possibly infinite families?
