Proper connection and size of graphs期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Proper connection and size of graphs

Authors:	Susan A van Aardt Christoph Brause Alewyn P Burger Marietjie Frick Arnfried Kemnitz Ingo Schiermeyer

Institution:	1. Department of Mathematical Sciences, University of South Africa, UNISA, Pretoria, South Africa;2. Institut für Diskrete Mathematik und Algebra, TU Bergakademie Freiberg, 09596 Freiberg, Germany;3. Department of Logistics, University of Stellenbosch, Matieland, 7602, South Africa;4. Computational Mathematics, Technische Universität Braunschweig, 38023 Braunschweig, Germany

Abstract:	An edge-coloured graph $G$ is called properly connected if any two vertices are connected by a path whose edges are properly coloured. The proper connection number of a connected graph $G,$ denoted by $pc (G)$ , is the smallest number of colours that are needed in order to make $G$ properly connected. Our main result is the following: Let $G$ be a connected graph of order $n$ and $k \geq 2$ . If $\| E (G) \| \geq (\binom{n ? k ? 1}{2}) + k + 2$ , then $pc (G) \leq k$ except when $k = 2$ and $G \in {G_{1}, G_{2}},$ where $G_{1} = K_{1} \lor (2 K_{1} + K_{2})$ and $G_{2} = K_{1} \lor (K_{1} + 2 K_{2}) .$

Keywords:	Edge-colouring proper connection
本文献已被 ScienceDirect 等数据库收录！