On almost self-centered graphs and almost peripheral graphs

DOI10.11650/TJM/220401MaRDI QIDQ2083239zbMATH OpenOpenAlexFDO

Authors Yanan Hu, Xingzhi Zhan

Publication date 10 October 2022

Published in Taiwanese Journal of Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

girthindependence numberalmost self-centered graphalmost peripheral graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Vertex degrees (05C07) Distance in graphs (05C12)

Abstract: 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 and (4) the maximum size of an almost peripheral graph of order $n;$ (5) which numbers are possible for the maximum degree of an almost peripheral graph of order $n;$ (6) the maximum number of vertices of maximum degree in an almost peripheral graph of order $n$ whose maximum degree is the second largest possible. Whenever the extremal graphs have a neat form, we also describe them.

Recommendations

• Constructing almost peripheral and almost self-centered graphs revisited
• Almost self-centered median and chordal graphs
• Almost-peripheral graphs
• Almost self-centered graphs
• Embeddings into almost self-centered graphs of given radius

Cites work

• scientific article; zbMATH DE number 194437 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• Almost self-centered graphs
• Almost-peripheral graphs
• Constructing almost peripheral and almost self-centered graphs revisited
• Eccentric sequences in graphs
• Embeddings into almost self-centered graphs of given radius
• Girth of sparse graphs
• Possible cardinalities of the center of a graph
• Simplified constructions of almost peripheral graphs and improved embeddings into them
• The dissimilarity characteristic of Husimi trees

Cited in

(9)

• On the g-centroidal problem in special classes of perfect graphs
• scientific article; zbMATH DE number 4150203 (Why is no real title available?)
• Constructing almost peripheral and almost self-centered graphs revisited
• Almost self-centered median and chordal graphs
• Simplified constructions of almost peripheral graphs and improved embeddings into them
• On special classes of self-centred graphs
• A characterization for 2-self-centered graphs
• Almost-peripheral graphs
• scientific article; zbMATH DE number 5844247 (Why is no real title available?)

This page was built for publication: On almost self-centered graphs and almost peripheral graphs

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