(Strong) Proper vertex connection of some digraphs

Kairui Nie, Yingbin Ma and Elżbieta Sidorowicz

Applied Mathematics and Computation, 2023, vol. 458, issue C

Abstract: The (strong) proper vertex connection number spvc→(Γ), (s)pvc-number for short, is denoted as the smallest cardinality of colors required to color the digraph Γ so that Γ is (strong) properly vertex connected. The pvc-number and the spvc-number are calculated for some unique classes of digraphs in this paper, along with some fundamental results on these parameters. It is known that the pvc-number is not exceeding 3 for any strong digraph. For digraphs with pvc-number not exceeding 2, we provide some sufficient conditions. Furthermore, we prove that the spvc-number is at most 3 for any minimal strongly connected digraph, but it can be arbitrarily large for some strong digraphs.

Keywords: Properly vertex connected; Strong properly vertex connected; Digraph; Vertex-coloring (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300323004125
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:458:y:2023:i:c:s0096300323004125

DOI: 10.1016/j.amc.2023.128243

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().