A characterization of the Centers of Chordal Graphs

Published

September 30, 2022

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

Pub Weblink

https://arxiv.org/abs/2210.00039

Pub Type

Websites

Download Paper

https://doi.org/10.48550/arXiv.2210.00039

Local Download

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 December 17, 2024)