شماره راهنما :
1303 دكتري
پديد آورنده :
شفيعي، فاطمه
عنوان :
برش هاي مينيمم گراف هاي فاصله- منظم جهت دار
محل تحصيل :
اصفهان : دانشگاه صنعتي اصفهان
استاد راهنما :
غلامرضا اميدي
استاد مشاور :
رامين جوادي
توصيفگر ها :
ابر همبند راسي , ابر همبند يالي , برش هاي مينيمم , قضيه فزوني طيف لاپلاسين , گراف هاي قويا منظم جهت دار , گراف هاي فاصله- منظم جهت دار و گراف هاي فاصله- منظم جهت دار- ضعيف
استاد داور :
عليرضا عبدالهي، ابراهيم قرباني، بهناز عمومي
تاريخ ورود اطلاعات :
1397/10/19
كد ايرانداك :
ID1303 دكتري
چكيده انگليسي :
Minimum cuts of distance regular digraphs Fateme Shafiei fateme shafiei@math iut ac ir June 15 2015 Ph D Thesis in Farsi Department of Mathematical Sciences Isfahan University of Technology Isfahan 84156 8311 IranSupervisor Professor Gholamreza Omidii romidi@cc iut ac irAdvisor Professor Ramin Javadi rjavadi@cc iut ac ir2000 MSC 05C50 05E30 05C88 05C89 Keywords A Laplacian spectral excess theorem Distance regular digraphs Minimum cut Su per edge connectivity Super vertex connectivity Strongly regular digraphs Weakly distance regular digraphs Abstract In this theses first we investigate to the structure of minimum vertex and edge cuts of distance regular digraphs We show that each distance regular digraph different from an undirectedcycle is super edge connected i e any minimum edge cut of is the set of all edges going into or coming out of a single vertex Moreover we will show that except undirected cycles anydistance regular digraph with diameter D 2 degree k 3 or 0 is the number of2 paths from u to v for an edge uv of is super vertex connected i e any minimum vertex cutof is the set of all out neighbors or in neighbors of a single vertex in These results extendthe same known results for the undirected case with quite different proofs Also we show that for every weakly distance regular digraph with valency k the edge connec tivity equals k Moreover if k 2 then any minimum edge cut is the set of all edges going into orcoming out of a single vertex Here we show that this result holds for weakly distance regulardigraphs with diameter 3 We also prove that this result holds for all weakly distance regular kdigraphs when or k where for a weakly distance regular digraph of valency k 2we define resp to be the number of paths of length 2 from a vertex u to a vertex v in whenever u is adjacent to v resp v is at distance 2 from u Here we only use the combinatorialtechniques and we do not need eigenvalue methods The spectral excess theorem due to Fiol and Garriga in 1997 is an important result because itgives a good characterization of distance regularity in graphs Up to now some authors havegiven some variations of this theorem Motivated by this we give the corresponding result byusing the Laplacian spectrum for digraphs We also illustrate this Laplacian spectral excesstheorem for digraphs with few Laplacian eigenvalues and we show that any strongly connectedand regular digraph that has normal Laplacian matrix with three distinct eigenvalues is distance regular Hence such a digraph is strongly regular with girth g 2 or g 3 IntroductionA digraph or a directed graph is an ordered pair V E where V is a set whose elementsare called vertices or nodes and E is a set of ordered pairs of vertices called arcs or directededges In contrast a graph in which the edges are bidirectional is called an undirected graph Inorder to simplify our notations we will use the word edge instead of the word directed edges in the paper A digraph with no multiple edges or loops corresponding to a binary adjacencymatrix with 0 s on the diagonal is called simple Here we only consider finite simple graphs
استاد راهنما :
غلامرضا اميدي
استاد مشاور :
رامين جوادي
استاد داور :
عليرضا عبدالهي، ابراهيم قرباني، بهناز عمومي
