\(k\)-Connected Graphs Without \(K_4^-\)

Xiang-Jun Li1
1 School of Information and Mathematics Yangtze University Jingzhou, Hubei, 434102, PR China

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\).