Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMetric and Edge Metric Dimension of Zigzag Edge Coronoid Fused with Starphene
69
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $Gamma=(V,E)$ be a simple connected graph. $d(alpha,epsilon)=min{d(alpha, w), d(alpha, d}$ computes the distance between a vertex $alpha in V(Gamma)$ and an edge $epsilon=wdin E(Gamma)$. A single vertex $alpha$ is said to recognize (resolve) two different edges $epsilon_{1}$ and $epsilon_{2}$ from $E(Gamma)$ if $d(alpha, epsilon_{2}) eq d(alpha, epsilon_{1}}$. A subset of distinct ordered vertices $U_{E}subseteq V(Gamma)$ is said to be an edge metric generator for $Gamma$ if every pair of distinct edges from $Gamma$ are recognized by some element of $U_{E}$. An edge metric generator with a minimum number of elements in it, is called an edge metric basis for $Gamma$. Then, the cardinality of this edge metric basis of $Gamma$, is called the edge metric dimension of $Gamma$, denoted by $edim(Gamma)$. The concept of studying chemical structures using graph theory terminologies is both appealing and practical. It enables chemical researchers to more precisely and easily examine various chemical topologies and networks. In this article, we investigate a fascinating cluster of organic chemistry as a result of this motivation. We consider a zigzag edge coronoid fused with starphene and find its minimum vertex and edge metric generators.
rate research
Read More
For an ordered subset $S = {s_1, s_2,dots s_k}$ of vertices and a vertex $u$ in a connected graph $G$, the metric representation of $u$ with respect to $S$ is the ordered $k$-tuple $ r(u|S)=(d_G(v,s_1), d_G(v,s_2),dots,$ $d_G(v,s_k))$, where $d_G(x,y)$ represents the distance between the vertices $x$ and $y$. The set $S$ is a metric generator for $G$ if every two different vertices of $G$ have distinct metric representations. A minimum metric generator is called a metric basis for $G$ and its cardinality, $dim(G)$, the metric dimension of $G$. It is well known that the problem of finding the metric dimension of a graph is NP-Hard. In this paper we obtain closed formulae and tight bounds for the metric dimension of strong product graphs.
A graphene nanoribbon with zigzag edges has a gapped magnetic ground state with an antiferromagnetic inter-edge superexchange interaction. We present a theory based on asymptotic properties of the Dirac-model ribbon wavefunction which predicts $W^{-2}$ and $W^{-1}$ ribbon-width dependencies for the superexchange interaction strength and the charge gap respectively. We find that, unlike the case of conventional atomic scale superexchange, opposite spin-orientations on opposite edges of the ribbon are favored by both kinetic and interaction energies.
A set of vertices $W$ in a graph $G$ is called resolving if for any two distinct $x,yin V(G)$, there is $vin W$ such that ${rm dist}_G(v,x) eq{rm dist}_G(v,y)$, where ${rm dist}_G(u,v)$ denotes the length of a shortest path between $u$ and $v$ in the graph $G$. The metric dimension ${rm md}(G)$ of $G$ is the minimum cardinality of a resolving set. The Metric Dimension problem, i.e. deciding whether ${rm md}(G)le k$, is NP-complete even for interval graphs (Foucaud et al., 2017). We study Metric Dimension (for arbitrary graphs) from the lens of parameterized complexity. The problem parameterized by $k$ was proved to be $W[2]$-hard by Hartung and Nichterlein (2013) and we study the dual parameterization, i.e., the problem of whether ${rm md}(G)le n- k,$ where $n$ is the order of $G$. We prove that the dual parameterization admits (a) a kernel with at most $3k^4$ vertices and (b) an algorithm of runtime $O^*(4^{k+o(k)}).$ Hartung and Nichterlein (2013) also observed that Metric Dimension is fixed-parameter tractable when parameterized by the vertex cover number $vc(G)$ of the input graph. We complement this observation by showing that it does not admit a polynomial kernel even when parameterized by $vc(G) + k$. Our reduction also gives evidence for non-existence of polynomial Turing kernels.
A graph is edge-primitive if its automorphism group acts primitively on the edge set, and 2-arc-transitive if its automorphism group acts transitively on the set of 2-arcs. In this paper, we present a classification for those edge-primitive graphs which are 2-arc-transitive and have soluble edge-stabilizers.
A classic theorem of Euclidean geometry asserts that any noncollinear set of $n$ points in the plane determines at least $n$ distinct lines. Chen and Chvatal conjectured that this holds for an arbitrary finite metric space, with a certain natural definition of lines in a metric space. We prove that in any metric space with $n$ points, either there is a line containing all the points or there are at least $Omega(sqrt{n})$ lines. This is the first polynomial lower bound on the number of lines in general finite metric spaces. In the more general setting of pseudometric betweenness, we prove a corresponding bound of $Omega(n^{2/5})$ lines. When the metric space is induced by a connected graph, we prove that either there is a line containing all the points or there are $Omega(n^{4/7})$ lines, improving the previous $Omega(n^{2/7})$ bound. We also prove that the number of lines in an $n$-point metric space is at least $n / 5w$, where $w$ is the number of different distances in the space, and we give an $Omega(n^{4/3})$ lower bound on the number of lines in metric spaces induced by graphs with constant diameter, as well as spaces where all the positive distances are from {1, 2, 3}.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
