A Characterization for 2-Self-Centered Graphs

• Autorzy: Mohammad Hadi Shekarriz , Madjid Mirzavaziri , Kamyar Mirzavaziri
• Języki publikacji: EN

Abstrakty

EN

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 specialized bi-independent covering (SBIC) and a structure named 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.

Słowa kluczowe

EN

self-centered graphs; specialized bi-independent covering (SBIC); generalized complete bipartite graphs (GCB)

Kategorie tematyczne

• 05C12: Distance in graphs
• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 38
• Numer: 1
• Strony: 27-37

Daty

wydano

2018-02-01

otrzymano

2015-11-30

poprawiono

2016-08-24

zaakceptowano

2016-09-01

online

2017-12-30

Twórcy

autor

Mohammad Hadi Shekarriz

• , , P.O. Box 1159, , Iran

autor

Madjid Mirzavaziri

• , , P.O. Box 1159, , Iran

autor

Kamyar Mirzavaziri

• , , Iran

Identyfikatory

DOI

10.7151/dmgt.1994