{"id":{"repo_id":"qucosa-diss","oai_identifier":"oai:qucosa:de:qucosa:31245"},"canonical_url":"https://search.dev.ndltd.org/etd/qucosa-diss/oai:qucosa:de:qucosa:31245","repository":{"repo_id":"qucosa-diss","name":"QUCOSA","base_url":"http://www.qucosa.de/oai/"},"display":{"title":"Proper connection number of graphs","abstract":"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 $\\delta(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_2(G)$ and determine several classes of connected graphs satisfying $pc_2(G)=2$. Among these are all graphs satisfying the Chv\\'{a}tal and Erd\\'{o}s condition ($\\alpha({G})\\leq\\kappa(G)$ with two exceptions). We also study the relationship between proper 2-connection number $pc_2(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.","abstract_html":"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} <span class=\"etd-inline-math\">pc<sub>k</sub>(G)</span>, 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 <span class=\"etd-inline-math\">&delta;(G)\\geq3</span> 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 <span class=\"etd-inline-math\">S<sub>i,j,k</sub></span>, where $i,j,k$ are three integers and $0\\leq i\\leq j\\leq k$ (where <span class=\"etd-inline-math\">S<sub>i,j,k</sub></span> 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 <span class=\"etd-inline-math\">pc<sub>k</sub>(G)</span>, 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 <span class=\"etd-inline-math\">pc<sub>2</sub>(G)</span> and determine several classes of connected graphs satisfying <span class=\"etd-inline-math\">pc<sub>2</sub>(G)=2</span>. Among these are all graphs satisfying the Chv\\&#x27;{a}tal and Erd\\&#x27;{o}s condition (<span class=\"etd-inline-math\">&alpha;({G})\\leq\\kappa(G)</span> with two exceptions). We also study the relationship between proper 2-connection number <span class=\"etd-inline-math\">pc<sub>2</sub>(G)</span> 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.","abstract_has_math":true,"creators":["Doan, Trung Duy"],"institution":"TU Bergakademie Freiberg","degree_name":null,"degree_level":"thesis.doctoral","degree_discipline":null,"degree_department":null,"school":null,"contributors":["Schiermeyer, Ingo","Kemnitz, Arnfried"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018-08-07","date_published":"2018-08-07","updated_at":"2026-07-24T03:56:21Z","subjects":["properly connected graph","properly 2-connected graph","proper connection number","proper $2$-connection number","minimum degree","forbidden induced subgraph","Cartesian product"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":null,"outbound_label":null,"outbound_source":null},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Schiermeyer, Ingo","Kemnitz, Arnfried"]},{"key":"dc:creator","label":"Author","values":["Doan, Trung Duy"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:publisher","label":"Institution","values":["Technische Universität Bergakademie Freiberg"]},{"key":"dc:type","label":"Dc Type","values":["doctoralThesis"]},{"key":"thesis:degree_level","label":"Degree Level","values":["thesis.doctoral"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["TU Bergakademie Freiberg"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["properly connected graph","properly 2-connected graph","proper connection number","proper $2$-connection number","minimum degree","forbidden induced subgraph","Cartesian product"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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 $\\delta(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_2(G)$ and determine several classes of connected graphs satisfying $pc_2(G)=2$. Among these are all graphs satisfying the Chv\\'{a}tal and Erd\\'{o}s condition ($\\alpha({G})\\leq\\kappa(G)$ with two exceptions). We also study the relationship between proper 2-connection number $pc_2(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."]},{"key":"dc:title","label":"Title","values":["Proper connection number of graphs"]}]}],"canonical_facts":{"dc:contributor":["Schiermeyer, Ingo","Kemnitz, Arnfried"],"dc:creator":["Doan, Trung Duy"],"dc:description.abstract":["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 $\\delta(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_2(G)$ and determine several classes of connected graphs satisfying $pc_2(G)=2$. Among these are all graphs satisfying the Chv\\'{a}tal and Erd\\'{o}s condition ($\\alpha({G})\\leq\\kappa(G)$ with two exceptions). We also study the relationship between proper 2-connection number $pc_2(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."],"dc:publisher":["Technische Universität Bergakademie Freiberg"],"dc:subject":["properly connected graph","properly 2-connected graph","proper connection number","proper $2$-connection number","minimum degree","forbidden induced subgraph","Cartesian product"],"dc:title":["Proper connection number of graphs"],"dc:type":["doctoralThesis"],"thesis:degree_level":["thesis.doctoral"],"thesis:institution_name":["TU Bergakademie Freiberg"]},"updated_at":"2026-07-24T03:56:21Z"}