پديد آورنده :
غلامي چنارستان عليا، طيبه
عنوان :
مشخصه سازي گراف ها با روش مكمل ستاره اي
مقطع تحصيلي :
كارشناسي ارشد
گرايش تحصيلي :
رياضي كاربردي نظريه گراف
محل تحصيل :
اصفهان: دانشگاه صنعتي اصفهان،دانشكده علوم رياضي
صفحه شمار :
[نه]،112ص.: مصور،جدول،نمودار
يادداشت :
ص.ع.به: فارسي و انگليسي
استاد راهنما :
غلامرضا اميدي
استاد مشاور :
بهناز عمومي
توصيفگر ها :
مجموعه ستاره اي , مقدار ويژه , گراف ماكزيمال
تاريخ نمايه سازي :
88/12/12
استاد داور :
بهروز طايفه رضايي،عاطفه قرباني
چكيده فارسي :
به فارسي و انگليسي: قابل رويت در نسخه ديجيتالي
چكيده انگليسي :
Characterization Of Graphs By Star Complement Technique Tayebe Gholami Chenarestan Olya t gholami@math iut ac ir December 02 2009 Master of Science Thesis in Farsi Department of Mathematical Sciences Isfahan University of Technology Isfahan 84156 83111 IranSupervisor Dr Gholam Reza Omidi r0midi@cc iut ac ir2000 MSC 05c50 Key words Eigenvalue Graph maximal Star complement Star set Abstract In this thesis characterization of graphs is studied by star complement technique LetG be a graph of order n and let be its eigenvalue of multiplicity k A star complementfor in G H is an induced subgraph of G of order n k with no eigenvalue The setof all vertices in G H X is called a star set for in G One main problem in the contextof star complement is determination of all maximal graphs prescribing a given graph H asa star complement for a given eigenvalue The reconstruction theorem states that for agiven eigenvalue of G knowledge of a star complement corresponding to together withknowledge of the edge set between X and its complement X are su cient to reconstruct G For a given star complement H the range of possible values for the corresponding eigenvalue is constrained by the condition that must be a simple eigenvalue of some one vertexextension of H and a double eigenvalue of some two vertex extension of H In this thesis we give some known characterizations of graphs by star complements technique We study the maximal graphs as well as regular graphs which have Kr s tK1 as a starcomplement for eigenvalue 1 It turns out that some well known strongly regular graphsare uniquely determined by such a star complement Some general observations concerninggraphs with the complete bipartite graph Kr s r s 2 as a star complement are followedby a complete analysis of the case r 2 s 5 The results include a characterization ofthe Schla i graph and the construction of all the regular graphs which have K2 5 as a starcomplement Various graphs related to generalized line graphs or their complements arecharacterized by star complements corresponding to eigenvalues 2 or 1 We rst identifyamong trees and complete graphs those graphs which can be star complements for 1 as thesecond largest eigenvalue Using the graphs just obtained we next search for their maximalextensions either by theoretical means or by computer aided search Finally we study graphs all of whose star sets induce cliques or co cliques We show thatthe star sets of every tree for each eigenvalue are independent sets Among other results itis shown that each star set of a connected graph G with three distinct eigenvalues induces aclique if and only if G K1 2 or K2 2 It is also proved that stars are the only graphs withthree distinct eigenvalues having a star partition with independent star sets 1
استاد راهنما :
غلامرضا اميدي
استاد مشاور :
بهناز عمومي
استاد داور :
بهروز طايفه رضايي،عاطفه قرباني
