Minimum degree and size conditions for the proper connection number of graphs

DOI10.1016/J.AMC.2019.01.062zbMATH Open1428.05166arXiv1806.09452OpenAlexW2811228059WikidataQ128311050 ScholiaQ128311050MaRDI QIDQ2010690FDOQ2010690

Eddie Cheng, Lina Xue, Weihua Yang, Xiaxia Guan

Publication date: 27 November 2019

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Abstract: An edge-coloured graph $G$ is called $properly$ $connected$ if every two vertices are connected by a proper path. 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. Susan A. van Aardt et al. gave a sufficient condition for the proper connection number to be at most $k$ in terms of the size of graphs. In this note, %optimizes the boundary of the number of edges %we study the $proper$ $connection$ $number$ is under the conditions of adding the minimum degree and optimizing the number of edges. our main result is the following, by adding a minimum degree condition: Let $G$ be a connected graph of order $n$, $kgeq3$. If $$, then $pc(G)leqk$, where $m$ takes the value $t$ if $delta=1$ and $lfloorfrackdelta-1floor$ if $deltageq2$. Furthermore, if $k=2$ and $delta=2$, %(i.e., $$) $pc(G)leq2$, except $Gin{G}_1,G_n$ ($ngeq8$), where $G_1=K_{1}vee3K_2$ and $G_n$ is obtained by taking a complete graph $K_{n-5}$ and $K_{1}vee(2K_2$) with an arbitrary vertex of $K_{n-5}$ and a vertex with $d(v)=4$ in $K_{1}vee(2K_2$) being joined. If $k=2$, $deltageq3$, we conjecture $pc(G)leq2$, where $m$ takes the value $1$ if $delta=3$ and $0$ if $deltageq4$ in the assumption.

Full work available at URL: https://arxiv.org/abs/1806.09452

Recommendations

• Proper connection and size of graphs
• Minimum degree conditions for the proper connection number of graphs
• On the minimum degree and the proper connection number of graphs
• Note on minimum degree and proper connection number
• Minimum degree condition for proper connection number 2

zbMATH Keywords

minimum degreeproper connection numberedge number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Cites Work

• On maximal paths and circuits of graphs
• Rainbow connections of graphs: a survey
• Title not available (Why is that?)
• Note on Hamilton Circuits
• Rainbow connection in graphs
• Maximal circuits of graphs. I
• Some Theorems on Abstract Graphs
• On proper-path colorings in graphs
• Rainbow connection in graphs with minimum degree three
• Graphs with rainbow connection number two
• Rainbow connection number of dense graphs
• Rainbow connection in sparse graphs
• Proper connection of graphs
• On two conjectures about the proper connection number of graphs
• Rainbow vertex connection of digraphs
• Proper connection and size of graphs
• Total rainbow connection of digraphs

Cited In (9)

• Minimum degree condition for a graph to be knitted
• Title not available (Why is that?)
• Properties of connected graphs having minimum degree distance
• Degree sums and proper connection number of graphs
• Title not available (Why is that?)
• On the minimum degree and the proper connection number of graphs
• The minimum restricted edge-connected graph and the minimum size of graphs with a given edge-degree
• Graphs with (strong) proper connection numbers \(m - 3\) and \(m - 4\)
• Connectivity, graph minors, and subgraph multiplicity

This page was built for publication: Minimum degree and size conditions for the proper connection number of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2010690)