On almost self-centered graphs and almost peripheral graphs

DOI10.11650/TJM/220401zbMATH Open1498.05083arXiv2106.12148OpenAlexW3174637211MaRDI QIDQ2083239FDOQ2083239

Authors: Yanan Hu, Xingzhi Zhan 

Publication date: 10 October 2022

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Girth of sparse graphs
• Almost self-centered graphs
• Almost-peripheral graphs
• The dissimilarity characteristic of Husimi trees
• Embeddings into almost self-centered graphs of given radius
• Eccentric sequences in graphs
• Constructing almost peripheral and almost self-centered graphs revisited
• Possible cardinalities of the center of a graph
• Simplified constructions of almost peripheral graphs and improved embeddings into them

Cited In (6)

• On the g-centroidal problem in special classes of perfect graphs
• Title not available (Why is that?)
• Almost self-centered median and chordal graphs
• On special classes of self-centred graphs
• A characterization for 2-self-centered graphs
• Title not available (Why is that?)

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)