7269

6775

كارشناسي ارشد

رياضي كاربردي

اصفهان: دانشگاه صنعتي اصفهان، دانشكده علوم رياضي

1391

نه، 77ص.: مصور، جدول، نمودار

ص.ع. به فارسي و انگليسي

بهناز عمومي

غلامرضا اميدي

21/8/91

عباداله محموديان، رامين جوادي

1396/09/21

كتابنامه

علوم رياضي

رياضي

ID6775

به فارسي و انگليسي: قابل رويت در نسخه ديجيتالي

Biclique Covering of Graphs Somaye Beigi s beygirizi@math iut ac ir 08 09 2012 Department of Mathematical Sciences Isfahan University of Technology Isfahan 84156 83111 Iran Supervisor Dr Behnaz Omoomi bomoomi@cc iut ac ir Advisor Dr Gholam Reza Omidi romidi@cc iut ac ir 2010 MSC 05C70 Keywords biclique cover biclique cover number fractional biclique cover boolean rank booleaninteval dimension Abstract In this thesis we study the biclique covering of graphs A covering of G is a family of subgraphs say G1 Gt having the property that each edge of G is contained in at least one graph Gi forsome i If all Gi 1 i t belong to a speci ed class of graphs H such a covering is called anH covering of G If we require all subgraphs in the covering to be edge disjoint the covering is alsocalled a decomposition of G One of the fundamental topics in graph is to study the edge covering of graphs Much work hasbeen done on H covering for various classes H say cliques bicliques compelet bipartite subgraph compelet multipartite and If H is the set of complete bipartite graphs H covering is called anbiclique covering The biclique covering number bc G of a graph G is the smallest number of bicliquesin a biclique covering The smallest number of bicliques in a biclique decomposition is known as thebiclique partition number and is denoted by bp G Note that bc G bp G n 1 hold for anygraph G on n vertices just because stars are bicliques These measures of graphs were considered by many authors The classical result of Graham andPollak shows that bp Kn n 1 here Kn is a complete graph on n vertices On the other hand wehave bc Kn log2 n

بهناز عمومي

غلامرضا اميدي

عباداله محموديان، رامين جوادي