Hostname: page-component-7b7567c8c-xnf5g Total loading time: 0 Render date: 2026-11-18T10:24:34.780Z Has data issue: false hasContentIssue false

NOTE ON MINIMUM DEGREE AND PROPER CONNECTION NUMBER

Part of:Graph theory

Published online by Cambridge University Press:  03 July 2020

YUEYU WU
Affiliation:
Department of Mathematics, Nanjing University, Nanjing 210093, PR China email yueyuw@smail.nju.edu.cn
YUNQING ZHANG
Affiliation:
Department of Mathematics, Nanjing University, Nanjing 210093, PR China email yunqingzh@nju.edu.cn
YAOJUN CHEN*
Affiliation:
Department of Mathematics, Nanjing University, Nanjing 210093, PR China email yaojunc@nju.edu.cn
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

An edge-coloured graph $G$ is called properly connected if any two vertices are connected by a properly coloured path. The proper connection number, $pc(G)$, of a graph $G$, is the smallest number of colours that are needed to colour $G$ such that it is properly connected. Let $\unicode[STIX]{x1D6FF}(n)$ denote the minimum value such that $pc(G)=2$ for any 2-connected incomplete graph $G$ of order $n$ with minimum degree at least $\unicode[STIX]{x1D6FF}(n)$. Brause et al. [‘Minimum degree conditions for the proper connection number of graphs’, Graphs Combin. 33 (2017), 833–843] showed that $\unicode[STIX]{x1D6FF}(n)>n/42$. In this note, we show that $\unicode[STIX]{x1D6FF}(n)>n/36$.

Information

Type
Research Article
Copyright
© 2020 Australian Mathematical Publishing Association Inc.