Minimum degree condition for proper connection number 2
| Autor: | Fei Huang, Colton Magnant, Xueliang Li, Zhongmei Qin |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Discrete mathematics
General Computer Science Induced path 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Combinatorics 010201 computation theory & mathematics Graph power 0202 electrical engineering electronic engineering information engineering k-vertex-connected graph Path graph Bound graph Graph toughness Distance Complement graph Mathematics |
| Zdroj: | Theoretical Computer Science. 774:44-50 |
| ISSN: | 0304-3975 |
| Popis: | A path in an edge-colored graph is called a proper path if no two adjacent edges of the path receive the same color. For a connected graph G, the proper connection number p c ( G ) of G is defined as the minimum number of colors needed to color its edges, so that every pair of distinct vertices of G is connected by at least one proper path in G. Recently, Li and Magnant in [8] posed the following conjecture: If G is a connected noncomplete graph of order n ≥ 5 and minimum degree δ ( G ) ≥ n / 4 , then p c ( G ) = 2 . In this paper, we show that this conjecture is true except for two small graphs on 7 and 8 vertices, respectively. As a byproduct we obtain that if G is a connected bipartite graph of order n ≥ 4 with δ ( G ) ≥ n + 6 8 , then p c ( G ) = 2 . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect