Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOrdering tree-like phenylenes by their Mostar indices
205
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Based on a measure of peripherality in graphs, a bond-additive structural invariant Mostar index $Mo(G)$ was introduced by Dov{s}li{c} et al., defined as $Mo(G)=sum_{e=uvin E(G)}|n_{u}-n_{v}|$, where $n_{u}$ (resp., $n_{v}$) is the number of vertices whose distance to vertex $u$ (resp., $v$) is smaller than the distance to vertex $v$ (resp., $u$). In this study, we determine the first three minimal values of the Mostar index of tree-like phenylenes with a fixed number of hexagons and characterize all the tree-like phenylenes attaining these values.
rate research
Read More
Topological indices are a class of numerical invariants that predict certain physical and chemical properties of molecules. Recently, two novel topological indices, named as Sombor index and reduced Sombor index, were introduced by Gutman, defined as $$SO(G)=sum_{uvin E(G)}sqrt{d_{G}^{2}(u)+d_{G}^{2}(v)},$$ $$SO_{red}(G)=sum_{uvin E(G)}sqrt{(d_{G}(u)-1)^{2}+(d_{G}(v)-1)^{2}},$$ where $d_{G}(u)$ denotes the degree of vertex $u$ in $G$. In this paper, our aim is to order the chemical trees, chemical unicyclic graphs, chemical bicyclic graphs and chemical tricyclic graphs with respect to Sombor index and reduced Sombor index. We determine the first fourteen minimum chemical trees, the first four minimum chemical unicyclic graphs, the first three minimum chemical bicyclic graphs, the first seven minimum chemical tricyclic graphs. At last, we consider the applications of reduced Sombor index to octane isomers.
Minimum Bisection denotes the NP-hard problem to partition the vertex set of a graph into two sets of equal sizes while minimizing the width of the bisection, which is defined as the number of edges between these two sets. We first consider this problem for trees and prove that the minimum bisection width of every tree $T$ on $n$ vertices satisfies $MinBis(T) leq 8 n Delta(T) / diam(T)$. Second, we generalize this to arbitrary graphs with a given tree decomposition $(T,X)$ and give an upper bound on the minimum bisection width that depends on the structure of $(T,X)$. Moreover, we show that a bisection satisfying our general bound can be computed in time proportional to the encoding length of the tree decomposition when the latter is provided as input.
We give a simple proof of a major index determinant formula in the symmetric group discovered by Krattenthaler and first proved by Thibon using noncommutative symmetric functions. We do so by proving a factorization of an element in the group ring of the symmetric group. By applying similar methods to the groups of signed permutations and colored permutations, we prove determinant formulas in these groups as conjectured by Krattenthaler.
This paper is motivated by the following question: what are the unavoidable induced subgraphs of graphs with large treewidth? Aboulker et al. made a conjecture which answers this question in graphs of bounded maximum degree, asserting that for all $k$ and $Delta$, every graph with maximum degree at most $Delta$ and sufficiently large treewidth contains either a subdivision of the $(ktimes k)$-wall or the line graph of a subdivision of the $(ktimes k)$-wall as an induced subgraph. We prove two theorems supporting this conjecture, as follows. 1. For $tgeq 2$, a $t$-theta is a graph consisting of two nonadjacent vertices and three internally disjoint paths between them, each of length at least $t$. A $t$-pyramid is a graph consisting of a vertex $v$, a triangle $B$ disjoint from $v$ and three paths starting at $v$ and disjoint otherwise, each joining $v$ to a vertex of $B$, and each of length at least $t$. We prove that for all $k,t$ and $Delta$, every graph with maximum degree at most $Delta$ and sufficiently large treewidth contains either a $t$-theta, or a $t$-pyramid, or the line graph of a subdivision of the $(ktimes k)$-wall as an induced subgraph. This affirmatively answers a question of Pilipczuk et al. asking whether every graph of bounded maximum degree and sufficiently large treewidth contains either a theta or a triangle as an induced subgraph (where a theta means a $t$-theta for some $tgeq 2$). 2. A subcubic subdivided caterpillar is a tree of maximum degree at most three whose all vertices of degree three lie on a path. We prove that for every $Delta$ and subcubic subdivided caterpillar $T$, every graph with maximum degree at most $Delta$ and sufficiently large treewidth contains either a subdivision of $T$ or the line graph of a subdivision of $T$ as an induced subgraph.
We find a formula for the number of permutations of $[n]$ that have exactly $s$ runs up and down. The formula is at once terminating, asymptotic, and exact.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
