Open Access. Powered by Scholars. Published by Universities.®
Discrete Mathematics and Combinatorics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Keyword
Articles 1 - 3 of 3
Full-Text Articles in Discrete Mathematics and Combinatorics
Domination In Graphs And The Removal Of A Matching, Geoffrey Boyer
Domination In Graphs And The Removal Of A Matching, Geoffrey Boyer
All Theses
We consider how the domination number of an undirected graph changes on the removal of a maximal matching. It is straightforward that there are graphs where no matching removal increases the domination number, and where some matching removal doubles the domination number. We show that in a nontrivial tree there is always a matching removal that increases the domination number; and if a graph has domination number at least $2$ there is always a maximal matching removal that does not double the domination number. We show that these results are sharp and discuss related questions.
Generalized Vulnerability Measures Of Graphs, Julia Vanlandingham
Generalized Vulnerability Measures Of Graphs, Julia Vanlandingham
All Theses
Several measures of vulnerability of a graph look at how easy it is to disrupt the network by removing/disabling vertices. As graph-theoretical parameters, they treat all vertices alike: each vertex is equally important. For example, the integrity parameter considers the number of vertices removed and the maximum number of vertices in a component that remains. We consider the generalization of these measures of vulnerability to weighted vertices in order to better model real-world applications. In particular, we investigate bounds on the weighted versions of connectivity and integrity, when polynomial algorithms for computation exist, and other characteristics of the generalized measures.
Cohen-Macaulay Properties Of Closed Neighborhood Ideals, Jackson Leaman
Cohen-Macaulay Properties Of Closed Neighborhood Ideals, Jackson Leaman
All Theses
This thesis investigates Cohen-Macaulay properties of squarefree monomial ideals, which is an important line of inquiry in the field of combinatorial commutative algebra. A famous example of this is Villareal’s edge ideal [11]: given a finite simple graph G with vertices x1, . . . , xn, the edge ideal of G is generated by all the monomials of the form xixj where xi and xj are adjacent in G. Villareal’s characterization of Cohen-Macaulay edge ideals associated to trees is an often-cited result in the literature. This was extended to chordal and bipartite graphs by Herzog, Hibi, and Zheng in …