A \(2\)-noncrossing tree is a rooted tree drawn in the plane with its vertices (colored black or white) on the boundary of a circle such that the edges are line segments that do not intersect inside the circle and there is no black-black ascent in any path from the root. A rooted tree is said to be increasing if the labels of the vertices are increasing as one moves away from the root. In this paper, we use generating functions and bijections to enumerate \(2\)-noncrossing increasing trees by the number of blacks vertices and by root degree. Bijections with noncrossing trees, ternary trees, 2-plane trees, certain Dyck paths, and certain restricted lattice paths are established.
This paper introduces the new notion of total chromatic vertex stress of a graph. Results for certain tree families and other \(2\)-colorable graphs are presented. The notions of chromatically-stress stability and chromatically-stress regularity are also introduced. New research avenues are also proposed.
Coloring the arcs of biregular graphs was introduced with possible applications to industrial chemistry, molecular biology, cellular neuroscience, etc. Here, we deal with arc coloring in some non-bipartite graphs. In fact, for \(1<k\in\mathbb{Z}\), we find that the odd graph \(O_k\) has an arc factorization with colors \(0,1,\ldots,k\) such that the sum of colors of the two arcs of each edge equals \(k\). This is applied to analyzing the influence of such arc factorizations in recently constructed uniform 2-factors in \(O_k\) and in Hamilton cycles in \(O_k\) as well as in its double covering graph known as the middle-levels graph \(M_k\).
Let \(G\) be a graph with \(n\) vertices. The second Zagreb energy of graph \(G\) is defined as the sum of the absolute values of the eigenvalues of the second Zagreb matrix of graph \(G\). In this paper, we derive the relation between the second Zagreb matrix and the adjacency matrix of graph \(G\) and derive the new upper bound for the second Zagreb energy in the context of trace. We also derive the second Zagreb energy of \(m-\)splitting graph and \(m-\)shadow graph of a graph.
The Sombor index (\(SO\)) and the modified Sombor index (\(^mSO\)) are two closely related vertex-degree-based graph invariants. Both were introduced in the 2020s, and have already found a variety of chemical, physicochemical, and network-theoretical applications. In this paper, we examine the product \(SO \cdot {^mSO}\) and determine its main properties. It is found that the structure-dependence of this product is fully different from that of either \(SO\) or \(^mSO\). Lower and upper bounds for \(SO \cdot {^mSO}\) are established and the extremal graphs are characterized. For connected graphs, the minimum value of the product \(SO \cdot {^mSO}\) is the square of the number of edges. In the case of trees, the maximum value pertains to a special type of eclipsed sun graph, trees with a single branching point.
