Frequently Asked QuestionsSubmit your Thesis or DissertationStart a New Search
#uHeader {
position: relative;
}
#headerLinks {
position: absolute;
right: 0px;
top: 50px;
}
#headerLinks > a {
margin-top: 8px;
display: block;
}
#P0_NEW_SEARCH {
font-size: 16px;
font-weight: bold;
padding-top: 10px;
}

2011, Doctor of Philosophy, Ohio State University, Mathematics.

Generate a graph on n vertices by randomly assigning to each vertex v some weight w(v) in [0, 1], where each weight is taken independently and identically on the interval, and adding an edge between vertices v_{i} and v_{j} if and only if |w(v_{i}) + w(v_{j})| > 1; the results of such processes are known as threshold graphs. Similarly, if we first partition the vertices into two sets A and B, and only permit edges between vertices of different sets, then the result is a difference graph.

On these two probability spaces, we examine the behavior of the respective classes of graphs by finding the distribution of several graph invariants, such as the matching number, connectivity, and length of the longest cycle. We are aided in this task by an additional result which permits us to translate between the continuous sample spaces given above and the discrete probability space in which each such graph is chosen uniformly at random.

Boris Pittel, PhD (Advisor)

G. Neil Robertson, PhD (Committee Member)

Warren Sinnott, PhD (Committee Member)

G. Neil Robertson, PhD (Committee Member)

Warren Sinnott, PhD (Committee Member)

106 p.

Ross, C. (2011). Properties of Random Threshold and Bipartite Graphs. (Electronic Thesis or Dissertation). Retrieved from https://etd.ohiolink.edu/

Ross, Christopher. "Properties of Random Threshold and Bipartite Graphs." Electronic Thesis or Dissertation. Ohio State University, 2011. OhioLINK Electronic Theses and Dissertations Center. 25 Feb 2018.

Ross, Christopher "Properties of Random Threshold and Bipartite Graphs." Electronic Thesis or Dissertation. Ohio State University, 2011. https://etd.ohiolink.edu/