The generalized 3-connectivity of the Mycielskian of a graph

摘要

The generalized k-connectivity κk(G) of a graph G is a generalization of the concept of the traditional connectivity, which can serve for measuring the capability of a graph G to connect any k vertices in G. In a search for triangle-free graphs with arbitrarily large chromatic numbers, Mycielski developed a graph transformation that transforms a graph G into a new graph μ(G), which is called the Mycielskian of G. In this paper, we investigate the relation between the generalized 3-connectivity of the Mycielskian of a graph G and the generalized 3-connectivity of G, and show that κ3(μ(G))≥κ3(G)+1. Moreover, by this result, we completely determine the generalized 3-connectivity of the Mycielskian of the tree Tn, the complete graph Kn and the complete bipartite graph Ka,b.