Upper bounds of proper connection number of graphs
2017
A path in an edge-colored graph is called a proper path if no two adjacent edges of the path are colored with one same color. An edge-colored graph is proper connected if any two distinct vertices of the graph are connected by a proper path in the graph. For connected graph G, the smallest number of colors that are needed in order to make G proper connected is called the proper connection number of G, denoted by pc(G). In this paper, we present an upper bound for the proper connection number of a graph in terms of the bridge-block tree of the graph. We also use this upper bound as an efficient tool to investigate the Erdos-Gallai-type problem for the proper connection number of a graph.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
19
References
14
Citations
NaN
KQI