2022/02/01 by S Chan, Chan, Su Yuan, Kerri Morgan +3
Computer Science · Mathematics · #05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2202.00411
openalex publication_date 2022/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the area of extremal graph theory, there exists a problem that investigates the maximum induced density of a k-vertex graph H in any n-vertex graph G. This is known as the problem of inducibility that was first introduced by Pippenger and Golumbic in 1975. In this paper, we give a new upper bound for the inducibility for a family of Double Loop Graphs of order k. The upper bound obtained for order k=5 is within a factor of 0.964506 of the exact inducibility, and the upper bound obtained for k=6 is within a factor of 3 of the best known lower bound.