Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

A characterization of the Centers of Chordal Graphs

Published

Author(s)

James Shook, Bing Wei

Abstract

A graph is $k$-chordal if it does not have an induced cycle with length greater than $k$. We call a graph chordal if it is $3$-chordal. Let $G$ be a graph. The distance between the vertices $x$ and $y$, denoted by $d_G}(x,y)$, is the length of a shortest path from $x$ to $y$ in $G$. The eccentricity of a vertex $x$ is defined as $\epsilon_G}(x)= \max\d_G}(x,y)|y\in V(G)\}$. The radius of $G$ is defined as $Rad(G)=\min\\epsilon_G}(x)|x\in V(G)\}$. The diameter of $G$ is defined as $Diam(G)=\max\\epsilon(x)|x\in V(G)\}$. The graph induced by the set of vertices of $G$ with eccentricity equal to the radius is called the center of $G$. In this paper we present new bounds for the diameter of $k$-chordal graphs, and we give a concise characterization of the centers of chordal graphs.
Citation
arXiv
Volume
2210

Keywords

graph theory, chordal graph, center, diameter

Citation

Shook, J. and Wei, B. (2022), A characterization of the Centers of Chordal Graphs, arXiv, [online], https://doi.org/10.48550/arXiv.2210.00039, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=933482, https://arxiv.org/abs/2210.00039 (Accessed January 28, 2023)
Created September 30, 2022, Updated November 29, 2022