The Topological Connectivity of the Independence Complex of Circular-Arc Graphs

Year 2019, , 159 - 169, 26.12.2019

Yousef Abd Algani

https://doi.org/10.32323/ujma.556457

Abstract

Let us denoted the topological connectivity of a simplicial complex $C$ plus 2 by $\eta(C)$. Let $\psi$ be a function from class of graphs to the set of positive integers together with $\infty$. Suppose $\psi$ satisfies the following properties: \newline $\psi{(K_{0})}$=0. \newline For every graph G there exists an edge $e=(x,y)$ of $G$ such that $$\psi{(G-e)}\geq{\psi{(G)}}$$ (where $G-e$ is obtained from $G$ by the removal of the edge $e$), and $$\psi{(G-N(\lbrace x,y \rbrace))}\geq{\psi{(G)}}-1$$  then $$\eta{(\mathcal{I}{(G)})}\geq\psi{(G)}$$ (where $(G-N(\lbrace x,y \rbrace))$ is obtained from $G$ by the removal of  all neighbors of $x$ and $y$ (including, of course, $x$ and $y$ themselves). Let us denoted the maximal function satisfying the conditions above by $\psi_0$. Berger [3] prove the following conjecture: $$\eta{(\mathcal{I}{(G)})}=\psi_{0}{(G)}$$ for trees and completements of chordal graphs. Kawamura [2]  proved conjecture, for chordal  graphs. Berger [3] proved Conjecture for trees and completements of chordal graphs. In this article I proved the following theorem: Let $G$ be a circular-arc graph $G$ if $\psi_0(G)\leq 2$ then $\eta(\mathcal{I}(G))\leq 2$. Prior the attempt to verify the previously mentioned cases, we need a few preparations which will be discussed in the introduction.

Keywords

Topological connectivity, Independence Complex, Circular-Arc graphs

References

• [1] R. Aharoni, E. Berger, R. Ziv, Independent systems of representatives in weighted graphs, Combinatorica, 27 (2007), 253–267.
• [2] K. Kawamura, Independence complex of chordal graphs, Discrete Math., 310 (2010), 2204–2211.
• [3] E. Berger, Topological Methods in Matching Theory, Faculty Of Princeton University In Candidacy.
• [4] G. A. Dirac, On rigid circuit graphs, Math. sem. Univ. Hamburg, 25 (1961), 71-76 .
• [5] D. Kozov, Combinatorial Algebraic Topology.