On Almost Self-centered Graphs and Almost Peripheral Graphs

摘要

An almost self-centered graph is a connected graph of order n with exactly n - 2 central vertices, and an almost peripheral graph is a connected graph of order n with exactly n - 1 peripheral vertices. We determine (1) the maximum girth of an almost self-centered graph of order n; (2) the maximum independence number of an almost self-centered graph of order n and radius r; (3) the minimum order of a k-regular almost self-centered graph; (4) the maximum size of an almost peripheral graph of order n; (5) possible maximum degrees of an almost peripheral graph of order n and (6) the maximum number of vertices of maximum degree in an almost peripheral graph of order n with maximum degree n - 4 which is the second largest possible. Whenever the extremal graphs have a neat form, we also describe them.

关键词