Graphs cospectral with a friendship graph or its complement

سال انتشار: 1392
نوع سند: مقاله ژورنالی
زبان: انگلیسی
مشاهده: 199

فایل این مقاله در 16 صفحه با فرمت PDF قابل دریافت می باشد

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

JR_COMB-2-4_004

تاریخ نمایه سازی: 29 آبان 1400

چکیده مقاله:

‎Let n be any positive integer and F_n be the friendship (or Dutch windmill) graph with ۲n+۱ vertices and ۳n edges‎. ‎Here we study graphs with the same adjacency spectrum as F_n‎. ‎Two graphs are called cospectral if the eigenvalues multiset of their adjacency matrices are the same‎. ‎Let G be a graph cospectral with F_n‎. ‎Here we prove that if G has no cycle of length ۴ or ۵‎, ‎then G\cong F_n‎. ‎Moreover if G is connected and planar then G\cong F_n‎. ‎All but one of connected components of G are isomorphic to K_۲‎. ‎The complement \overline{F_n} of the friendship graph is determined by its adjacency eigenvalues‎, ‎that is‎, ‎if \overline{F_n} is cospectral with a graph H‎, ‎then H\cong \overline{F_n}‎.

نویسندگان

Alireza Abdollahi

University of Isfahan

Shahrooz Janbaz

University of Isfahan

Mohammad Reza Oboudi

University of Isfahan