Operations Research Transactions ›› 2011, Vol. 15 ›› Issue (3): 51-56.
• Original Articles • Previous Articles Next Articles
WANG Guang-Hui, ZHOU Shan
Online:
Published:
Abstract: Let $K_{n}^{c}$ denote a complete graph on $n$ vertices whose edges are colored in an arbitrary way. Let $\Delta^{mon} (K_{n}^{c})$ denote the maximum number of edges of the same color incident with a vertex of $K^c_{n}$. A properly colored cycle (path) in $K_{n}^{c}$ is a cycle (path) in which adjacent edges have distinct colors. B. Bollob\'{a}s and P. Erd\"{o}s (1976) proposed the following conjecture: If $\Delta^{{mon}} (K_{n}^{c})<\lfloor \frac{n}{2} \rfloor$, then $K_{n}^{c}$ contains a properly colored Hamiltonian cycle. This conjecture is still open. In this paper, we study properly colored paths and cycles under the condition mentioned in the above conjecture.
Key words: properly colored cycle, complete graph
WANG Guang-Hui, ZHOU Shan. Properly Colored Paths and Cycles in Complete Graphs[J]. Operations Research Transactions, 2011, 15(3): 51-56.
0 / / Recommend
Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks
URL: https://www.ort.shu.edu.cn/EN/
https://www.ort.shu.edu.cn/EN/Y2011/V15/I3/51