On Minimum Spanning Subgraphs of Graphs With Proper Connection Number 2

Abstract

An edge coloring of a connected graph G is a proper-path coloring if every two vertices of G are connected by a properly colored path. The minimum number of colors required of a proper-path coloring of G is called the proper connection number pc(G) of G. For a connected graph G with proper connection number 2, the minimum size of a connected spanning subgraph H of G with pc(H) = 2 is denoted by μ(G). It is shown that if s and t are integers such that t ≥ s + 2 ≥ 5, then μ(K_{s,t} ) = 2t − 2. We also determine μ(G) for several classes of complete multipartite graphs G. In particular, it is shown that if G = K_{n_1, n_2, ..., n_k} is a complete k-partite graph, where k ≥ 3, r = \sum^{k−1}_{i=1} n_i ≥ 3 and t = n_k ≥ r^2 + r, then μ(G) = 2t − 2r + 2.

Keywords

• proper-path coloring
• proper connection
• minimum spanning subgraph