Scholarlink

<p>This paper studies induced paths in strongly regular graphs. We give an elementary proof that a strongly regular graph contains a path <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(P_4\)</EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(P_5\)</EquationSource> </InlineEquation> 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Induced Paths in Strongly Regular Graphs

  • 期刊论文

  • 发表日期：

    2026年1月13日

查看全文
  • Robert F. Bailey,
  • Abigail K. Rowsell

摘要

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.