On the panconnectivity of graphs with large degrees and neighborhood unions
type: Item
instance of: scholarly article
title: On the panconnectivity of graphs with large degrees and neighborhood unions
zbMATH Open document ID: 0906.05039
author: K. Appert
published in: Graphs and Combinatorics
publication date: 1999-02-01T00:00:00Z
review text: It is shown that if \(G\) is a \(3\)-connected graph of order \(n\) such that for any triple of independent vertices \(\{u,v,w\}\), the \(\min \{| N(u) \cup N(v)|+ d(w), | N(u) \cup N(w)|+ d(v), | N(v) \cup N(w)|+ d(u) \} \geq n+ 1\), then \(G\) is \([7,n]\)-panconnected. There is a corresponding result for \(2\)-connected graphs if certain pairs of cutvertices are avoided. Let \(\text{NC}(G)\) be the minimum number of vertices in the union of the neighborhood of any pair of nonadjacent vertices of the graph \(G\). A corollary of this is that if \(\text{NC}(G)+ \delta(G) \geq n+ 1\), then \(G\) is vertex pancyclic. This confirms a conjecture of \textit{R. J. Faudree} et al. in [Ars Comb. 31, 139-148 (1991; Zbl 0739.05056)].
reviewed by: Ralph Faudree
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1211726
zbMATH Keywords: panconnected
zbMATH Keywords: vertex pancyclic
zbMATH Keywords: neighborhood condition
MaRDI profile type: Publication
full work available at URL: s003730050030
OpenAlex ID: W2067124261
DOI: 10.1007/S003730050030
description: scientific article; zbMATH DE number 1211726