$k$-Connected Graphs Without $K_4^{-}$

Abstract

Let $K_4^{-}$ be the graph obtained from $K_4$ by deleting one edge. A graph $G$ is called $K_4^{-}$-free if it does not contain $K_4^{-}$ as a subgraph. K. Kawarabayashi showed that a $K_4^{-}$-free $k$-connected graph has a $k$-contractible edge if $k$ is odd. Furthermore, when $k$ is even, K. Ando et al. demonstrated that every vertex of a $K_4^{-}$-free contraction critical $k$-connected graph is contained in at least two triangles. In this paper, we extend Kawarabayashi’s result and obtain a new lower bound on the number of $k$-contractible edges in a $K_4^{-}$-free $k$-connected graph when $k$ is odd. Additionally, we provide characterizations and properties of $K_4^{-}$-free contraction critical $k$-connected graphs and prove that such graphs have at least $\frac{2|G|}{k-1}$ vertices of degree $k$.