The Topological Connectivity of the Bipartite Graph’s Independence Complex

Abstract

Let ($\complement$) signify a simplicial complex; the topological connectivity of $\complement$ is denoted by $\zeta$ ($\complement$), which equals $\complement$+2, where $\zeta$ is a function from the class of graphs to the set ${\mathbb{Z}}^{+}=\left\{0,1,2,\dots ,\infty \right\}$. Let the function $\zeta$ possesses the following characteristics: 1. $\zeta \left(K_0\right)=0$. 2. For any graph $G\left(V,E\right)$, there exists an edge $\left\{x,y\right\}$in G such that $\zeta \left(G\left(V,E\right)-\left\{x,y\right\}\right)\ge \zeta \left(G\left(V,E\right)\right)$ where ($G\left(V,E\right)-\left\{x,y\right\})$ means to remove the edge $\left\{x,y\right\}$ from the graph $G\left(V,E\right)$), and $\zeta \left(G\left(V,E\right)-\mathrm{\Delta }\left(\left\{x,y\right\}\right)\right)\ge \zeta \left(G\left(V,E\right)\right)-1$where ($G\left(V,E\right)-\mathrm{\Delta }(\left\{x,y\right\}$) means to remove the vertices $x\text{and}y$ and all their neighbors. Then $\mu (\mathrm{\Gamma }\left(G\left(V,E\right)\right)\ge \zeta \left(G\left(V,E\right)\right)$. Let ${\zeta }_0$ denote the maximal function $\zeta$ that satisfies the aforementioned constraints. Berger proved that $\mu (\mathrm{\Gamma }\left(G\left(V,E\right)\right)\ge {\zeta }_0\left(G\left(V,E\right)\right)$ for trees and for complements of chordal graphs. Kawamura proved the same theorem for chordal graphs, and Abd Algani proved it for circular-arc graph: Let $G\left(V,E\right)$ be a circular-arc graph; if ${\zeta }_0\left(G\left(V,E\right)\right)\le 2,\text{then}\mu \left(\mathrm{\Gamma }\left(G\left(V,E\right)\right)\right)\le 2.$ In this chapter, we will prove the following theorem: Let $G\left(V,E\right)$ be a bipartite graph; if ${\zeta }_0\left(G\left(V,E\right)\right)\le 2,\text{then}\mu \left(\mathrm{\Gamma }\left(G\left(V,E\right)\right)\right)\le 2$.

1. Introduction

The set $\complement \ne \varphi$ is a simplicial complex if $\omega \in \complement$ and $\lambda \subseteq \omega$ indicate $\lambda \in \complement$. Each simplicial complex has a distinctive (up to homeomorphism) geometric recognition, specifically an inserting in the space ${\mathbb{R}}^n$, wherein each simplex $\omega \in \complement$ is grasped as a homeomorph of a simplex in ${\mathbb{R}}^n$.

The connection between two simplicial complexes $M$ and $N$ is called join, and it will be denoted by $M\ast N$ and is defined as

$$M\ast N=\left\{\omega \cup \lambda |\omega \in M_{\lambda }N\right\}.$$

The topological space $X\ast v_{\left(\text{vertex}\right)}$ is called a cone over $X$ and is denoted by ${\complement }_{v}X$. And the topological space $X\ast S_0$ is called a suspension and is denoted by $\mathit{\text{susp}}-M$.

A complex would be identified by its geometric recognition. The topological connectivity of a simplicial complex $\complement$ is the biggest number ${\complement }_0$ that being said for each number $d\le {\complement }_0$, each inserting of the $d$-dimensional sphere $S_d$ is extendable to an inserting of the $\left(d+1\right)$-dimensional ball $B_d+1$ in $\complement$. The connectivity of a complex could be infinite. The connectivity of $\complement +2$ is signified by $\mu \left(\complement \right)$. This is because the addition of $2$ makes the creation of some grades more sophisticated.

For a graph $G\left(V,E\right)$ with the vertex set $V$ and edge set E, a subgroup $U$ of $V$ is no two distinct vertices of U in V are adjacent. $A$ subgroup $S$ of $V$ is leading in $G\left(V,E\right)$ if each vertex $v\in V$ is nearby to a vertex of $S$. The dominance number $\delta \left(G\left(V,E\right)\right)$ is the lowest of the cardinality of leading groups of $G\left(V,E\right):\delta \left(G\left(V,E\right)\right)=min\left\{\left|S\right|:S\text{is dominating in}G\left(V,E\right)\right\}$.

Let H be a graph; we signify by $\mathrm{\Gamma }\left(H\right)$ the simplicial complex containing all the autonomous groups of vertices in $H$. Let $V_k,k\le m,$ be a divider of the vertex set of a graph $G$. Given a vertex $v\in V\left(G\left(V,E\right)\right)$, we write $k\left(v\right)$ for the index $k$ for which $v\in V_k$. For a set $Z$ of vertices, we write $\mathrm{\Gamma }\left(Z\right)=\left\{k\left(z\right):z\in Z\right\}$. Typically, we signify the set $\left\{1,\dots ,f\right\}$ by $\left[f\right]$. Assuming a subset $\mathrm{\Gamma }$of $\left[f\right]$, we write $V_I\text{for}{U}_{k\in K}{V}_i$.

Consider a graph $G\left(V,E\right)$ with a divider $V_1,V_2,\dots ,V_f$ of its vertex set. A select of one vertex from every set $V_i$ is termed an autonomous structure of representative ($\mathrm{ISR}$) if the designated vertices are nonadjacent in $G\left(V,E\right)$. The connection between topological connectivity and ISR was recognized in [1]. Existence of $\mathrm{ISR}$:

Theorem 1. If for all $\mathrm{\Gamma }\subseteq \left[f\right]$

$$\mu \left(\mathrm{\Gamma }\left(G\left(V,E\right)\left[V_{\mathrm{\Gamma }}\right]\right)\right)\ge \left|\mathrm{\Gamma }\right|,$$

then the partition $\left(V_k\right)\left(k\le f\right)$ of $V\left(G\left(V,E\right)\right)$ has an $\mathrm{ISR}$.

Graph $G\left(V,E\right)$ is a bipartite graph if there is a division of V into two groups, A and B, so that every edge of $G\left(V,E\right)$ has one end at A and the other at B. In this instance, there occurs an $\mathrm{ISR}$ if and only if the graph is not a whole bipartite. But not being complete bipartite means the presence of a linking in $\mathrm{\Gamma }\left(G\left(V,E\right)\right)$ between both simplices $V_1$ and $V_2$ of $\mathrm{\Gamma }(G\left(V,E\right)$). Consequently, not being a whole bipartite is equal to $\mathrm{\Gamma }\left(G\left(V,E\right)\right)$ being related, which, in the aforementioned terminology, means being zero-connected, which means that $\mu \left(\mathrm{\Gamma }\left(G\left(V,E\right)\right)\right)\ge 2$. Consequently, in this instance, the state of the theorem is not only adequate but also essential. The following theorem is due to Ahrone [1]; we carry here its new formulation.

Theorem 2. Let ($\complement$) signify a simplicial complex and $\zeta \left(\complement \right)$ denote the topological connectivity of $\complement$, which equals $\complement$+2. Let $\zeta$ be a function from the class of graphs to the set ${\mathbb{Z}}^{+}=\left\{0,1,2,\dots ,\infty \right\}$.

Let the function $\zeta$ possess the following characteristics:

1. $\zeta \left(K_0\right)=0$

2. There exists, for any graph G, an edge $\left\{x,y\right\}$ in G,

   $$\zeta \left(G\left(V,E\right)-\left\{x,y\right\}\right)\ge \zeta \left(G\left(V,E\right)\right)$$

($G\left(V,E\right)-\left\{x,y\right\})$ means to remove the edge $\left\{x,y\right\}$ from the graph $G\left(V,E\right)$),

and

$$\zeta \left(G\left(V,E\right)-\mathrm{\Delta }\left(\left\{x,y\right\}\right)\right)\ge \zeta \left(G\left(V,E\right)\right)-1.$$

Then

$$\mu (\mathrm{\Gamma }\left(G\left(V,E\right)\right)\ge \zeta \left(G\left(V,E\right)\right).$$

($G\left(V,E\right)-\mathrm{\Delta }(\left\{x,y\right\}$) means to remove the vertices $x\text{and}y$ and all their neighbors).

Let ${\zeta }_0$ denote the maximal function $\zeta$ that satisfies the aforementioned constraints.

Actually, there exists a maximal function ${\zeta }_0$ filling the conditions of the theorem. It is best defined in terms of a game between two actors: (a) and (b). Player (a) needs to take full benefit of the function$\zeta$ in the theorem (and hereafter show that $\zeta$ is big), whereas player (b) needs to minimize $\zeta$. Player (a) chooses an edge $e=\left\{x,y\right\}$ in the graph assumed at the current phase of the game. Player (b) selects between two options: he or she either (I) removes e from the graph, or else (II) erases all neighbors of the vertices $x$ and $y$ (including, $x$ and $y$ themselves). The game finishes when either there remains a secluded vertex, in which case $\zeta$ is well-defined as $\infty$, or there are no remaining vertices, in which case $\zeta$ is recognized as the number of steps of player (b) of type (II).

We describe ${\zeta }_0\left(G\left(V,E\right)\right)$ as the maximal value of $\zeta \left(G\left(V,E\right)\right)$ player (a) can gain in the game. Moreover, it was declared that $\mu \left(\mathrm{\Gamma }\left(G\right)\right)\ge \zeta \left(G\right).$

We can also describe ${\zeta }_0$ recursively in the following way:

$${\zeta }_0\left(G\left(V,E\right)\right)=\left\{\begin{array}{c}0,\text{if}G\left(V,E\right)\text{is empty}\\ \infty ,\text{if}G\left(V,E\right)\mathrm{has}\text{an isolated vertex}\\ {max}_{e\in E}min({\zeta }_0\left(G\left(V,E\right)-e\right),{\zeta }_0\left(G\left(V,E\right)-\mathrm{\Delta }\left[x\right]-\mathrm{\Delta }\left[y\right]\right)+1,\\ \text{otherwise}.\end{array}\right.$$

Aharoni and colleagues [1] proved the following assumption:

Theorem 3.

$$\mu \left(\mathrm{\Gamma }\left(G\left(V,E\right)\right)\right)={\zeta }_0\left(G\left(V,E\right)\right)$$

Kawamura [2] showed the theorem for chordal graphs. Now, we describe a chordal graph that is defined as follows: A graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge linking two nodes that are not together in the cycle.

The chordal graphs are the joint graphs of subtrees of a tree. A typical theorem of Dirac [3] declares that for each chordal graph $G$, there is a vertex, named a simplicial vertex, such that $\mathrm{\Delta }\left(v\right)$ is a complete graph.

In a previous study [4], Abd Algani showed the theorem for circular-arc graphs, which is known as the joining graphs of a set of arcs on a circle. This graph comprises one vertex for each arc in the set and an edge connecting every two vertices whose arcs intersect.

Officially, let

$${\mathrm{\Gamma }}_1,{\mathrm{\Gamma }}_2,\dots \dots \dots \dots ,{\mathrm{\Gamma }}_n\subseteq {\mathrm{S}}_1$$

be a set of arcs. Then, the corresponding circular-arc graph is $G$, such that

$$V=\left\{{\mathrm{\Gamma }}_1,{\mathrm{\Gamma }}_2,\dots \dots \dots \dots ,{\mathrm{\Gamma }}_n\right\}$$

and

$$\left\{{\mathrm{\Gamma }}_{\alpha },{\mathrm{\Gamma }}_{\beta }\right\}\in E\iff {\mathrm{\Gamma }}_{\alpha }\cap {\mathrm{\Gamma }}_{\beta }\ne \varnothing .$$

A group of edges that parallels to $G\left(V,E\right)$ is termed an arc model of $G\left(V,E\right)$.

In [5], the following theorem was demonstrated.

Theorem 4. Let G be a $\mathit{min}$ counterexample for Theorem 3. Then, $G$ has no vertex of degree $1.$

Moreover, Theorems 1 and 2 grasp for each tree.

In addition, Berger [5] proved the following:

Theorem 5. Let $G\left(V,E\right)$ be a chordal graph; then, ${\zeta }_0\left(\overline{G\left(V,E\right)}\right)=\infty .$

Theorems 2, 3, and 5 were shown in [5] for complements of chordal graphs and for trees. Kawamura [2] verified the theorem for chordal graphs.

Theorem 6. Let $G\left(V,E\right)$ be a chordal graph. Then, $\mathrm{\Gamma }\left(G\left(V,E\right)\right)$ is either contractible¹ or is homotopy² equal to the section of finitely several spheres $\bigvee S^{k_t}$ where $k_t\ge \delta \left(G\left(V,E\right)\right)-1\text{for each}{k}_t$.

On the contrary, all limited wedges appear as homotopy types of independence complex of chordal graphs.

Kawamura [2] proves the following theorem:

Theorem 7. Let L be a simplicial complex and let $k_1,\dots \dots .,k_r$ be subcomplexes of L (repetitions allowable). Consider individual points $u_1,\dots \dots \dots .,u_r$ and $v$with $\left\{u_1,\dots \dots \dots ,u_r,v\right\}\cap L;$then, the union

$$\mathrm{\Lambda }={\complement }_{v}L\cup {\bigcup }_{i=1}^r\left(C_{u_i}\cap K_i\right)$$

subject to the conditions

$$C_{u_i}{K}_i\cap C_{v}L=K_i\text{and}$$

$${\complement }_{u_i}{K}_i\cap {\complement }_{u_j}{K}_j=K_i\cap K_j\left(i,j=1,\dots .r,i\ne j\right).$$

1. Is homotopy corresponding to ${\bigvee }_{i=1}^r\mathit{\text{susp}}{K}_i$

2. The suspension $\mathit{\text{susp}}\left(\mathrm{\Lambda }\right)$ is contractible for each contractible complex $\mathrm{\Lambda }$.

3. $\text{susp}\left(\bigvee S^{k_r}\right)\approx \bigvee S^{k_r+1}$.

Theorems 7–10 [1, 3] offer us a strong understanding of the construction of chordal graphs’ independence complexes.

For a vertex $v$ of a graph $G\left(V,E\right)$, let ${\mathrm{\Gamma }}_v\left(G\left(V,E\right)\right)$ be the subcomplex generated by the independent sets containing $v$:

${\mathrm{\Gamma }}_v\left(G\left(V,E\right)\right)=\{U\mid \text{there exists}\mathrm{a}\text{simplex}B\in \mathrm{\Gamma }\left(G\left(V,E\right)\right)$such that

$$\left\{v\in B\mathit{\text{and}}U\subset B\right\}.$$

Theorem 8. Let $G\left(V,E\right)$ be a graph and let $v$ be a simplicial vertex of $G\left(V,E\right)$. Enumerate $\mathrm{\Delta }\left(v\right)$ as $\mathrm{\Delta }\left(v\right)=\left\{w_1,\dots \dots ,w_r\right\}$. Then, we have the following:

$$\mathrm{\Gamma }\left(G\left(V,E\right)\right)\approx \bigvee \mathit{\text{susp}}\mathrm{\Gamma }\left(G-\mathrm{\Delta }\left[w_i\right]\right).$$

For every chordal graph $G\left(V,E\right)$, we term $\mu \left(G\left(V,E\right)\right)\in {\mathbb{Z}}^{+}$as follows: if $\mathrm{\Gamma }\left(G\left(V,E\right)\right)$ is contractible, then let $\mu \left(G\left(V,E\right)\right)=\infty$, and if $\mathrm{\Gamma }\left(G\left(V,E\right)\right)$ is homotopy equal to the wedge $\bigvee S^{i_r}$, then let $\mu \left(G\left(V,E\right)\right)=min\left(i_r\right)$, the minimum dimension of the related spheres. Theorems 6 and 7 offer the following theorem:

Theorem 9. Let $G\left(V,E\right)$be a chordal graph; then, $\mu \left(G\left(V,E\right)\right)\ge \delta \left(G\left(V,E\right)\right)-1$.

Theorem 10. Let v be a simplicial vertex of the graph G(V, E) and enumerate $\mathrm{\Delta }\left(v\right)$ as $\mathrm{\Delta }\left(v\right)=\left\{w_1,\dots \dots ,w_r\right\}.$Then, we have the equation $\mu \left(G\left(V,E\right)\right)=min\left\{\mu \left(G\left(V,E\right)-\mathrm{\Delta }\left[w_k\right]\right)│k=1,\dots \dots ,r\right\}+1$.

And we can agree that $$min\left\{\infty ,\dots \dots ,\infty \right\}+1=\infty .$$

For the path graph $P_n$ with $n$ edges, $\mathrm{\Gamma }\left(P_n\right)$ is contractible if $n\equiv 0\left(\mathit{mod}3\right)$ and is homotopy equal to the sphere of $\left[\frac{n}{3}\right]\text{dimension}$. Then, we have the following equation:

$$\mu \left(P_n\right)=\left\{\begin{array}{c}\infty ,\text{if}n\equiv 0\left(\mathit{mod}3\right)\\ \frac{n}{3},\text{otherwise}.\end{array}\right.$$

It should be noted that Kawamura [2] proved Theorems 6–10 for chordal graphs. In previous research [4], Abd Algani proved Theorem 2 about circular-arc graphs. In addition, in the same paper, he found that for path graph ($P_n$):

$$\mu \left(P_n\right)={\zeta }_0\left(P_n\right)=\left\{\begin{array}{c}\infty ,\text{if}n\equiv 0\left(\mathit{mod}3\right)\\ \frac{n}{3},\text{otherwise}.\end{array}\right.$$

Moreover, for the general case of circle graph (${\complement }_n$), it was determined that

$$\mu \left(C_n\right)=min\left(\mu \left(P_{n-5}\right)+1,\mu \left(P_{n-6}\right)+2\right)=\frac{n}{3}.$$

2. New result

In a previous paper, Abd Algani [4] demonstrated the following theorem:

Let $G\left(V,E\right)$ be a circular arc graph; if ${\zeta }_0\left(G\left(V,E\right)\right)\le 2$, then $\mu \left(\mathrm{\Gamma }\left(G\left(V,E\right)\right)\right)\le 2$.

In this chapter, the theorem will be generalized for a bipartite graph.

Main theorem: Let $G$ be a bipartite graph; if ${\zeta }_0\left(G\left(V,E\right)\right)\le 2$, then $\mu \left(\mathrm{\Gamma }\left(G\left(V,E\right)\right)\right)\le 2$.

Proof.

Let $G\left(V,E\right)$ be a bipartite graph, that is, a graph with the property: if we remove each edge in the graph with all its neighbors, the graph that we will be obtain is a complete bipartite graph.³

We need to prove that if ${\zeta }_0\left(G\right)\le 2$, then $\mu \left(\mathrm{\Gamma }\left(G\right)\right)\le 2$.

First, we remove all the possible edges. In this situation, the graph will look like Figure 1.

Figure 1.

The graph looks like (1) or (2) when we remove all possible edges.

The graph of ${\complement }_6$ is a bipartite graph, and each set is an independent set (see Figure 2). Now, color the sets by two colors, for example, red and blue, as follows: Mark the graph vertices with colors such that no two vertices sharing the same edge have the same color (see Figure 2).

Figure 2.

The inflated graph of C₆.

Each set has a vertex, where the set front does not have a neighbor, so we have built the largest set of vertices (see Figure 2).

The result leads to a construction, as clarified in Figure 3.

Figure 3.

The result of performing a retraction is a cube.

The result of performing a retraction⁴ is a cube. The cube has two foreign edges and two various vertices (see Figure 4). If the path $P_4$ exist in the bipartite graph and the path $P_5$ not exist, then:

Figure 4.

The cube has two foreign edges and two various vertices.

If we insert a vertex into the path $P_4$, as clarified in Figure 5: If we remove their edge $1$ (see Figure 5), then we have two isolated vertices.

Figure 5.

The form of the neighbors of $P_4$.

If we have path $P_4$ and path $P_5$ and do not have ${\complement }_6$ (see Figure 6). In Figure 6, if we remove edge $\left\{3,4\right\}$ with all of its neighbors, the remaining graph is a complete bipartite graph; then, vertex (1) and vertex (6) remain and are connected by an edge, and we obtain graph ${\complement }_6$.

Figure 6.

Without $C_6.$

If we cannot remove the edges from the graph, then $\mu =2$.

Now, we prove that $\mu =2$ before we remove any edges. We have three cases.

Case 1: The graph resembles Figure 7; the red edges may not exist. If there are no edges (red edges in Figure 7), then we perform a retraction, with the result being an induced matching.

Figure 7.

If there are no red edges, then we perform a retraction, with the result being an induced matching.

Case 2: With the existence of the red edges, the graph will resemble Figure 8: If we remove the “Blue” edge (between two sets) with all of its neighbors, then the vertex $V_1$ will be isolated.

Figure 8.

Existence of red edges.

We can remove the “Green” edges in Figure 8, and we can remove the (main) “Black” edges in the same figure, then we have two connected components.

Note that the situation, as described in Figure 9, cannot exist, because there is a vertex in set 1, which is not connected to a vertex in set 3 by an edge, and therefore, the complementary complex is a chordal graph; thus, $\left(\mu ={\zeta }_0=\infty \right).$

Figure 9.

This situation cannot exist.

If we have a bipartite graph, and we know that the complementary independent complex of a bipartite graph is a chordal graph, then $\mu ={\zeta }_0=\infty$.

In the case of $P_4$ (see Figure 10), if we remove edge $\left\{3,4\right\}$, then the vertex $V_1$ is isolated.

Figure 10.

If we remove edge $\left\{3,4\right\}$, then vertex $V_1$ is isolated.

We cannot remove edge $\left\{2,3\right\}$ because the vertices $v_2$ and $v_3$ are two dominating vertices.

Case 3: After we remove all possible edges, we obtain $P_5$ (but do not have $C_5$); we cannot remove edge $\left\{1,2\right\}$ (see Figure 11) because $v_6$ is a neighbor of $v_5$. This situation is $C_6$.

Figure 11.

We cannot remove edge $\left\{1,2\right\}.$

Thus, we have found the independence complex of the topological connectivity of the bipartite graph:

if

$${\zeta }_0\left(G\right)\le 2$$

then

$$\mu \left(c_i\left(G\right)\right)\le 2.$$

3. Conclusion

In this chapter, we found that the topological connectivity of the bipartite graph’s independence complex where the theorem that if ${\zeta }_0\left(G\left(V,E\right)\right)\le 2,\text{then}\mu \left(\mathrm{\Gamma }\left(G\left(V,E\right)\right)\right)\le 2$ is proven for a bipartite graph $G\left(V,E\right)$ by examining all possible cases. For future research, we recommend trying to prove that $\mu (\mathrm{\Gamma }\left(G\left(V,E\right)\right)\ge {\zeta }_0\left(G\left(V,E\right)\right)$ for bipartite chordal graphs (the topological connectivity of independence complex of bipartite chordal graph). It is worth noting that the topological connectivity of independence complex has been proven previously for trees and complements of chordal graphs by Berger [5], for chordal graphs by Kawamura [2], and for circular-arc graph by Abd Algani [4].