Search ETDs:
Properties of Random Threshold and Bipartite Graphs
Ross, Christopher Jon

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 vi and vj if and only if |w(vi) + w(vj)| > 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)
106 p.

Recommended Citations

Hide/Show APA Citation

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

Hide/Show MLA Citation

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

Hide/Show Chicago Citation

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

Files

osu1306296991.pdf (756.15 KB) View|Download