The noncrossing poset and topological indices of finite graphs
- UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
- Charles Matthew Farmer (Creator)
- Institution
- The University of North Carolina at Greensboro (UNCG )
- Web Site: http://library.uncg.edu/
- Advisor
- Clifford Smyth
Abstract: In Part I, we study the noncrossing bond poset of a graph. The partition lattice and noncrossing partition lattice are well studied objects in combinatorics. Given a graph G on vertex set {1, 2, . . . ,n}, its bond lattice, LG, is the subposet of the partition lattice formed by restricting to the partitions whose blocks induce connected subgraphs of G. In this article, we introduce a natural noncrossing analogue of the bond lattice, the noncrossing bond poset, NCG, obtained by restricting to the noncrossing partitions of LG. Both the noncrossing partition lattice and the bond lattice have many nice combinatorial properties. We show that, for several families of graphs, the noncrossing bond poset also exhibits these properties. We present simple necessary and sufficient conditions on the graph to ensure the noncrossing bond poset is a lattice. Additionally, for several families of graphs, we give combinatorial descriptions of the Möbius function and characteristic polynomial of the noncrossing bond poset. These descriptions are in terms of a noncrossing analogue of non-broken circuit (NBC) sets of the graphs and can be thought of as a noncrossing version of Whitney’s NBC theorem for the chromatic polynomial. We also consider the shellability and supersolvability of the noncrossing bond poset, providing sufficient conditions for both. In Part II, we study topological indices of finite graphs. A topological index is a function from the set of graphs to C which is invariant under graph isomorphism. We study indices such as the Randic index, the radius, and the largest eigenvalues of the adjacency, Laplacian, and signless Laplacian matrices of graphs; i.e., spectral radii. We aim to find the extremal graphs of the ratio of the Randic index against the other indices listed above and present two new theorems as well as our work on an open problem relating the Randic index to the radius of a graph. We also study a known open problem involving the Randic index of a graph and the graph theoretic radius of a graph.[This abstract may have been edited to remove characters that will not display in this system. Please see the PDF for the full abstract.]
The noncrossing poset and topological indices of finite graphs
PDF (Portable Document Format)
4166 KB
Created on 8/1/2024
Views: 25
Additional Information
- Publication
- Dissertation
- Language: English
- Date: 2024
- Keywords
- Algebraic Combinatorics, Combinatorics, Graph Theory, Order Theory, Topological Indices
- Subjects
- Combinatorial geometry
- Topological graph theory
- Partially ordered sets