A Characterization For 2-Self-Centered Graphs

A Graph is called 2-self-centered if its diameter and radius both equal to 2. In this paper, we begin characterizing these graphs by characterizing edge-maximal 2-self-centered graphs via their complements. Then we split characterizing edge-minimal 2-self-centered graphs into two cases. First, we ch...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2019-10
Main Authors: Mohammad Hadi Shekarriz, Mirzavaziri, Madjid, Mirzavaziri, Kamyar
Format: Article
Language:English
Subjects:
Graph theory
Graphs
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A Graph is called 2-self-centered if its diameter and radius both equal to 2. In this paper, we begin characterizing these graphs by characterizing edge-maximal 2-self-centered graphs via their complements. Then we split characterizing edge-minimal 2-self-centered graphs into two cases. First, we characterize edge-minimal 2-self-centered graphs without triangles by introducing \emph{specialized bi-independent covering (SBIC)} and a structure named \emph{generalized complete bipartite graph (GCBG)}. Then, we complete characterization by characterizing edge-minimal 2-self-centered graphs with some triangles. Hence, the main characterization is done since a graph is 2-self-centered if and only if it is a spanning subgraph of some edge-maximal 2-self-centered graphs and, at the same time, it is a spanning supergraph of some edge-minimal 2-self-centered graphs.
ISSN:2331-8422
DOI:10.48550/arxiv.1910.12110