A CHARACTERIZATION FOR 2-SELF-CENTERED GRAPHS

作者：Shekarriz Mohammad Hadi^*; Mirzavaziri Madjid; Mirzavaziri Kamyar

来源：Discussiones Mathematicae - Graph Theory, 2018, 38(1): 27-37.

DOI：10.7151/dmgt.1994

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

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.

• 出版日期2018