پارامترهاي بهينه در گراف ها با دنباله درجه معلوم

چكيده انگليسي :

Optimum invariants in graphs with given degree sequence Fateme Sadat Khademi Master of Science Thesis in Farsi Departement of Mathematical Sciences Isfahan University of Technology Isfahan 84156 83111 IranSupervisor Prof Behnaz Omoomi bomoomi@iut ac ir2010 MSC 05C07 05C69 05C19 Keywords degree sequence choromatic number domination number independence set slater number annihilation number Abstract In each graph the degrees of the vertices form a sequence which we call the degree sequence Conversely for everysequence d of positive integers cannot be found a simple graph with degree sequence d The sequence d is calledgraphic where there is a simple graph G with the degree sequence d and the graph G is called a realization of d Havel and Hakimi found and proved the necessary and sufficient condition for a sequence of numbers to be graphic For a graphic sequence d graph parameter and opt min max let opt d opt G G G d where G d is the family of graphs with degree sequence d For every graph G the values of min d G and max d G are the best possible lower and upper bounds on G that only depend on the degree sequence ofG Since there are degree sequences of graphs that have exponentially many nonisomorphic realizations efficientalgorithms that determine for a given graph or forest do not immediately lead to efficient algorithms that determinethe above parameters Many of the boundaries obtained for these two parameters are related to the degree sequence orits derivatives including order size maximum degree and The most important of these parameters are chromaticnumber independence number and domination number In the first chapter the definitions and concepts required by the dissertation are stated In the second chapter ananalogue of Reed s Conjecture bounding the chromatic number by a convex combination of the clique number andmaximum degree are considered If d is a degree sequence we let d d h d and H d denote the maximumvalue of the chromatic number the size of the largest clique the size of the largest clique subdivision and the size ofthe largest clique minor respectively In this chapter we will state some Conjectures about the chromatic numberof graphs with the same degree sequence It is also shown that there is a subdivision of a clique of order d thatsubdivision is done only once on each edge i e G h1 d G which is related to Hajo s conjecture and inparticular satisfies Neil Robertson s Conjecture that d H d In the third chapter the relationship of the smallest dominating set between all realization of d are studied Also F Famong the realization forests of d min d and max d where F d is the family of forests with degree sequenced are studied and an optimal method for determining these two parameters for each graphic sequence are presented Preliminary results show that for every graphic sequence d with positive components there is a realization with thelowest number of the vertices with the largest degree make up the smallest dominating set In the fourth chapter in special circumstances the domination number and independence number of forest that real ized from the graphic sequence are studied Then for the graphic sequence d the largest domination number and thesmallest independence number are studied In the last chapter the boundaries of domination number of a tree are improved First the upper and lower bordersof the slater number in terms of the number of vertices are defined then the borders of the domination number of treeaccording to the slater number are determined

خادمي، فاطمه سادات

پارامترهاي بهينه در گراف ها با دنباله درجه معلوم

دنباله درجه. , عدد رنگي , عدد احاطه گري , عدد استقلال , عدد اسلتر , عدد نابودي