Embedded Files
Noncrossing Bond Poset
Noncrossing Bond Poset
The set partition lattice is a very well studied object in combinatorics. Given a graph G on vertex set [n] := { 1, 2, ... ,n }, we have what is known as the bond lattice. We call a subgraph of G a bond if it is a spanning subgraph such that each connected component induces all edges. The figure to the right is the bond lattice of the graph with vertex set [4] and edge set {13, 14, 24}. Since this graph is a tree, all spanning subgraphs are bonds. This definition yields an injective correspondence between subgraphs and set partitions where all vertices in the same connected component form a block. For example, the set partition 13/24 corresponds to the bond eith edge set {13, 24}
A partition π = B1 / B2 / ... / Bk is called crossing if there exists distinct i and j such that a and c are in Bi and b and d are in Bj with a < b < c < d; otherwise, a partition is said to be noncrossing. Observe how each graph is drawn so that the vertices appear in ascending clockwise order. Using this graphical representation, we call a bond crossing if two edges intersect, yielding a similar definition to a crossing set partition. Hence, the noncrossing bond poset is the subposet of the bond lattice of all bond that are noncrossing. The figure to the left shows the noncrossing bond poset of G = ( [4], { 13, 14, 24 } ); the same as the above figure sand the bond whose edge set is { 13, 24 }.
We are able to present criteria on graphs for which this poset is a lattice, graded, shellable, and when it may have an noncrossing nonbroken circuit (NCNBC) interpretation. In the future, we hope to strengthen our results by finding more classes of graphs whose noncrossing bond posets have these characteristics.
Team Members
Team Members
C. Matthew Farmer (UNC Greensboro) ● Dr. Joshua Hallam (Loyola Marymount University) ● Dr. Clifford Smyth (UNC Greensboro)
Presentations
Presentations
TAG_MaC_Conference_NCBP.pdfNoncrossing_Bond_Poset-4.pdfThe_Non_Crossing_Bond_Poset.pdfFPSAC 2019 Poster
FPSAC 2019 Poster
FPSAC_2019_Poster.pdfTopological Indices
Topological Indices
The Randić Index
The Randić Index
A topological index can be defined as a function from the set of all graphs to the complex numbers that is invariant under isomorphism. We study multiple indices such the spectral radii of the adjacency, Laplacian, and signless Laplacian matrices of a graph G, as well as the graphic theoretic radius and the Randić index of a graph G, defined to the right.
The goal of this project is to learn about these indices and to find extremal graph theoretic problems regarding ratios between them.
This topological index was introduced by organic chemist Milan Randić in the 1975 in his paper On Characterization of Molecular Branching, where he called this index the branching index. Dr. Randić used hydrocarbons to define a finite graph which mirrors the carbon skeleton of these molecules by drawing an edge between two carbon atoms if and only if they were bonded. He then endeavored to establish a connection between this carbon structure of a hydrocarbon and the physical chemical properties of molecules (such as boiling point) using the above definition. He found that the branching index is a strong predictor of a hydrocarbon's boiling point. Although, it is commonly known that molar mass and boiling point are strongly related, Dr. Randić's index still serves as a better predictor. The image below shows 5 graphs obtained from carbon structures of hydrocarbons which all have the same molar mass ( MM ) but differ by boiling point ( BP ) by up to 19° C. However, the Randić index ( RI ) varies more appropriately.
Not long after Dr. Randić introduced his branching index, graph theorists begun studying generalized versions of this index, as well as many other vertex-degree based and distance based topological indices. The Randić index has shown up in many extremal problems throughout the literature, and has been the heart of some long open conjectures; one of which we will consider in our research.
The Graph Theoretic Radius
The Graph Theoretic Radius
Let G be a finite simple graph with vertex set [n] := { 1, 2, ... ,n } which is connected. The eccentricity of a vertex v is defined as ecc(v) := max { d( u, v ) : u in V(G) }, where d( u, v ) denotes the length of the shortest path between u and v. The radius ( diameter ) if G is the minimum ( maximum ) over all eccentricities of G. The radius of G is denoted by r(G) and diameter is denoted by D(G). One can easily see that the graph G to the left has a radius of 2 and diameter of 4.
Problems with Indices
Problems with Indices
The spectral radius of a graph G is defined as the largest eigenvalue of the adjacency matrix of G, denotes by a(G). Likewise, the Laplacian and signless Laplacian spectral radii are similarly defined, denoted by ℓ(G) and sℓ(G) respectively. It is known in the literature which graphs maximize the ratio R(G) / a(G). We found which graphs maximize the ratios R(G) / ℓ(G) and R(G) / sℓ(G).
In 2010, the following open conjecture was presented: Let G be a graph which is not equal to the even ordered path. Then R(G) ≥ r(G).
We have endeavored to resolve this conjecture by presenting a conjecture of our own, stating that a particular tree known as the "comet" is the unique minimizer with respect to the Randić index amongst all graphs with fixed radius. If our conjecture is true, than we will have resolved the original conjecture.
Team Members
Team Members
C. Matthew Farmer (UNC Greensboro) ● Dr. Clifford Smyth (UNC Greensboro)
Presentations
Presentations
Sermon_Talk__without_pause_.pdfANTCOG_Talk___Topological_Indices__without_pause_.pdfPage updated
Google Sites
Report abuse