pith. sign in

arxiv: 1507.01426 · v2 · pith:YZDNXQJLnew · submitted 2015-07-06 · 🧮 math.CO

Proper connection number and 2-proper connection number of a graph

classification 🧮 math.CO
keywords propergraphconnectionnumberconnectedpathcallededge-colored
0
0 comments X
read the original abstract

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 called $k$-proper connected if any two vertices of the graph are connected by $k$ internally pairwise vertex-disjoint proper paths in the graph. The $k$-proper connection number of a $k$-connected graph $G$, denoted by $pc_k(G)$, is defined as the smallest number of colors that are needed in order to make $G$ $k$-proper connected. For $k=1$, we write $pc(G)$ other than $pc_1(G)$, and call it the proper connection number of $G$. In this paper, we present an upper bound for the proper connection number of a graph $G$ in terms of the minimum degree of $G$, and give some sufficient conditions for a graph to have $2$-proper connection number two. Also, we investigate the proper connection numbers of dense graphs.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.