On claw-free Toeplitz graphs

MaRDI QIDQ6388237zbMATH OpenFDO

Authors Gi-Sang Cheon, Bumtle Kang, Suh-Ryung Kim, Seyed Ahmad Mojallal, Homoon Ryu

Publication date 14 January 2022

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76)

Abstract: This paper was initiated by the observation that chordal Toeplitz graphs $T_{n}langle{t}_1,ldots,t_{k}angle$ with $n>t_{k-1}+t_k$ are claw-free. A Toeplitz graph with $n$ vertices is a simple graph whose adjacency matrix is an $nimesn$ $(0,1)$-symmetric Toeplitz matrix with zero diagonal and a claw in a graph means a star $K_{1,3}$ as an induced subgraph. We find an interesting family of claw-free Toeplitz graphs so called `cocoonery' and show that if $n>t_{k-1}+t_k$, then this family becomes exactly the family of claw-free Toeplitz graphs. We also completely characterize a claw-free Toeplitz graph $T_{n}langle{t}_1,ldots,t_{k}angle$ for $k=2$ and $k=3$. We go further to study Toeplitz graphs which happen to be line graphs.

This page was built for publication: On claw-free Toeplitz graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6388237)