Domination problems in directed graphs and inducibility of nets

dc.contributor.advisor Bernard Lidicky Blumenthal, Adam
dc.contributor.department Mathematics 2020-06-26T19:57:06.000 2020-06-30T03:22:02Z 2020-06-30T03:22:02Z Fri May 01 00:00:00 UTC 2020 2020-06-23 2020-01-01
dc.description.abstract <p>In this thesis we discuss two topics: domination parameters and inducibility. In the first chapter, we introduce basic concepts, definitions, and a brief history for both types of problems. We will first inspect domination parameters in graphs, particularly independent domination in regular graphs and we answer a question of Goddard and Henning. Additionally, we provide some constructions for graphs regular graphs of small degree to provide lower bounds on the independent domination ratio of these classes of graphs. In Chapter 3 we expand our exploration of independent domination into the realm of directed graphs. We will prove several results including providing a fastest known algorithm for determining existence of an independent dominating set in directed graphs with minimum in degree at least one and period not eqeual to one. We also construct a set of counterexamples to the analogue of Vizing's Conjecture for this setting. In the fourth chapter, we pivot from independent domination to split domination in directed graphs, where we introduce the split domination sequence. We will determine that almost all possible split domination sequences are realizable by some graphs, and state several open questions that would be of interest to continue on this field. In the fifth chapter we will provide a brief introduction to Flag Algebras, then determine the unique maximizer of induced net graphs in graphs of certain orders.</p>
dc.format.mimetype application/pdf
dc.identifier archive/
dc.identifier.articleid 8959
dc.identifier.contextkey 18242547
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath etd/17952
dc.language.iso en
dc.source.bitstream archive/|||Wed Jun 24 20:32:14 UTC 2020
dc.source.bitstream archive/|||Fri Jan 14 21:31:37 UTC 2022
dc.subject.keywords Directed Graphs
dc.subject.keywords Domination
dc.subject.keywords Extremal Combinatorics
dc.subject.keywords Graphs
dc.subject.keywords Inducibility
dc.title Domination problems in directed graphs and inducibility of nets
dc.type article
dc.type.genre thesis
dspace.entity.type Publication
relation.isOrgUnitOfPublication 82295b2b-0f85-4929-9659-075c93e82c48 Mathematics thesis Doctor of Philosophy
Original bundle
Now showing 1 - 2 of 2
505.96 KB
Adobe Portable Document Format
490.17 KB
Adobe Portable Document Format