Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Mathematics
Asteroidal Sets And Dominating Targets In Graphs, Oleksiy Al-Saadi
Asteroidal Sets And Dominating Targets In Graphs, Oleksiy Al-Saadi
Department of Computer Science and Engineering: Dissertations, Theses, and Student Research
The focus of this PhD thesis is on various distance and domination properties in graphs. In particular, we prove strong results about the interactions between asteroidal sets and dominating targets. Our results add to or extend a plethora of results on these properties within the literature. We define the class of strict dominating pair graphs and show structural and algorithmic properties of this class. Notably, we prove that such graphs have diameter 3, 4, or contain an asteroidal quadruple. Then, we design an algorithm to to efficiently recognize chordal hereditary dominating pair graphs. We provide new results that describe the …
Pascal's Triangle Modulo N And Its Applications To Efficient Computation Of Binomial Coefficients, Zachary Warneke
Pascal's Triangle Modulo N And Its Applications To Efficient Computation Of Binomial Coefficients, Zachary Warneke
Honors Theses
In this thesis, Pascal's Triangle modulo n will be explored for n prime and n a prime power. Using the results from the case when n is prime, a novel proof of Lucas' Theorem is given. Additionally, using both the results from the exploration of Pascal's Triangle here, as well as previous results, an efficient algorithm for computation of binomial coefficients modulo n (a choose b mod n) is described, and its time complexity is analyzed and compared to naive methods. In particular, the efficient algorithm runs in O(n log(a)) time (as opposed to …