Proper connection number of graphs

The concept of \emph{proper connection number} of graphs is an extension of proper colouring and is motivated by rainbow connection number of graphs. Let $G$ be an edge-coloured graph. Andrews et al.\cite{Andrews2016} and, independently, Borozan et al.\cite{Borozan2012} introduced the concept of proper connection number as follows: A coloured path $P$ in an edge-coloured graph $G$ is called a \emph{properly coloured path} or more simple \emph{proper path} if two any consecutive edges receive different colours. An edge-coloured graph $G$ is called a \emph{properly connected graph} if every pair of vertices is connected by a proper path. The \emph{proper connection number}, denoted by $pc(G)$, of a connected graph $G$ is the smallest number of colours that are needed in order to make $G$ properly connected. Let $k\geq2$ be an integer. If every two vertices of an edge-coloured graph $G$ are connected by at least $k$ proper paths, then $G$ is said to be a \emph{properly $k$-connected graph}. The \emph{proper $k$-connection number} pc_k(G), introduced by Borozan et al. \cite{Borozan2012}, is the smallest number of colours that are needed in order to make $G$ a properly $k$-connected graph. The aims of this dissertation are to study the proper connection number and the proper 2-connection number of several classes of connected graphs. All the main results are contained in Chapter 4, Chapter 5 and Chapter 6. Since every 2-connected graph has proper connection number at most 3 by Borozan et al. \cite{Borozan2012} and the proper connection number of a connected graph $G$ equals 1 if and only if $G$ is a complete graph by the authors in \cite{Andrews2016, Borozan2012}, our motivation is to characterize 2-connected graphs which have proper connection number 2. First of all, we disprove Conjecture 3 in \cite{Borozan2012} by constructing classes of 2-connected graphs with minimum degree δ(G)\geq3 that have proper connection number 3. Furthermore, we study sufficient conditions in terms of the ratio between the minimum degree and the order of a 2-connected graph $G$ implying that $G$ has proper connection number 2. These results are presented in Chapter 4 of the dissertation. In Chapter 5, we study proper connection number at most 2 of connected graphs in the terms of connectivity and forbidden induced subgraphs S_i,j,k, where $i,j,k$ are three integers and $0\leq i\leq j\leq k$ (where S_i,j,k is the graph consisting of three paths with $i,j$ and $k$ edges having an end-vertex in common). Recently, there are not so many results on the proper $k$-connection number pc_k(G), where $k\geq2$ is an integer. Hence, in Chapter 6, we consider the proper 2-connection number of several classes of connected graphs. We prove a new upper bound for pc₂(G) and determine several classes of connected graphs satisfying pc₂(G)=2. Among these are all graphs satisfying the Chv\'{a}tal and Erd\'{o}s condition (α({G})\leq\kappa(G) with two exceptions). We also study the relationship between proper 2-connection number pc₂(G) and proper connection number $pc(G)$ of the Cartesian product of two nontrivial connected graphs. In the last chapter of the dissertation, we propose some open problems of the proper connection number and the proper 2-connection number.

Level thesis:degree_level

thesis.doctoral

Grantor dc:publisher

TU Bergakademie Freiberg

Year

2018

Author dc:creator

• Doan, Trung Duy

Contributors dc:contributor

• Schiermeyer, Ingo
• Kemnitz, Arnfried

• properly connected graph
• properly 2-connected graph
• proper connection number
• proper $2$-connection number
• minimum degree
• forbidden induced subgraph
• Cartesian product