Panconnected graphs II |
| |
Authors: | James E Williamson |
| |
Institution: | (1) Division of Sciences College of Liberal Arts, University of Dubuque, 52001 Dubuque, IA, USA |
| |
Abstract: | A graphG of orderp is said to bepanconnected if for each pairu, v of vertices ofG, there exists a,u, v-path of lengthl inG, for eachl such that dG(u, v)lp – 1, whered
G
(u, v) denotes the length of a shortestu, v-path inG. Three conditions are shown to be sufficient for a graphG of orderp to be panconnected: (1) the degree of each vertex ofG is at least (p+2)/2; (2) the sum of the degrees of each pair of nonadjacent vertices ofG is at least (3p–2)/2; (3) the graphG has at least
edges. It is also shown that each of these conditions is best possible. Additional results on panconnectedness are obtained including a characterization of those completen-partite graphs which are panconnected. |
| |
Keywords: | Primary 05C15 |
本文献已被 SpringerLink 等数据库收录! |
|