Back to Search Start Over

Induced paths in strongly regular graphs

Authors :
Bailey, Robert F.
Rowsell, Abigail K.
Publication Year :
2023

Abstract

This paper studies induced paths in strongly regular graphs. We give an elementary proof that a strongly regular graph contains a path $P_4$ as an induced subgraph if and only if it is primitive, i.e. it is neither a complete multipartite graph nor its complement. Also, we investigate when a strongly regular graph has an induced subgraph isomorphic to $P_5$ or its complement, considering several well-known families including Johnson and Kneser graphs, Hamming graphs, Latin square graphs, and block-intersection graphs of Steiner triple systems.<br />Comment: 10 pages

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2307.14493
Document Type :
Working Paper