On Minimum Spanning Subgraphs of Graphs With Proper Connection Number 2
| Autor: | Zhenming Bi, Garry L. Johns, Gary Chartrand, Ping Zhang |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
proper-path coloring
Discrete mathematics Numerical Analysis Spanning tree lcsh:Mathematics minimum spanning subgraph Minimum spanning tree lcsh:QA1-939 proper connection Theoretical Computer Science Combinatorics Discrete Mathematics and Combinatorics Connection number Mathematics Minimum degree spanning tree |
| Zdroj: | Theory and Applications of Graphs, Vol 3, Iss 2 (2016) |
| ISSN: | 2470-9859 |
| DOI: | 10.20429/tag.2017.030202 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|