Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe metric dimension of strong product graphs
274
0
0.0
(
0
)
Added by
Juan Alberto Rodriguez Velazquez
Publication date
2013
fields
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
A subset $S$ of vertices of a connected graph $G$ is a distance-equalizer set if for every two distinct vertices $x, y in V (G) setminus S$ there is a vertex $w in S$ such that the distances from $x$ and $y$ to $w$ are the same. The equidistant dimension of $G$ is the minimum cardinality of a distance-equalizer set of G. This paper is devoted to introduce this parameter and explore its properties and applications to other mathematical problems, not necessarily in the context of graph theory. Concretely, we first establish some bounds concerning the order, the maximum degree, the clique number, and the independence number, and characterize all graphs attaining some extremal values. We then study the equidistant dimension of several families of graphs (complete and complete multipartite graphs, bistars, paths, cycles, and Johnson graphs), proving that, in the case of paths and cycles, this parameter is related with 3-AP-free sets. Subsequently, we show the usefulness of distance-equalizer sets for constructing doubly resolving sets.
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.
We introduce the set $mathcal{G}^{rm SSP}$ of all simple graphs $G$ with the property that each symmetric matrix corresponding to a graph $G in mathcal{G}^{rm SSP}$ has the strong spectral property. We find several families of graphs in $mathcal{G}^{rm SSP}$ and, in particular, characterise the trees in $mathcal{G}^{rm SSP}$.
A graph $G$ is a $k$-prime product distance graph if its vertices can be labeled with distinct integers such that for any two adjacent vertices, the difference of their labels is the product of at most $k$ primes. A graph has prime product number $ppn(G)=k$ if it is a $k$-prime product graph but not a $(k-1)$-prime product graph. Similarly, $G$ is a prime $k$th-power graph (respectively, strict prime $k$th-power graph) if its vertices can be labeled with distinct integers such that for any two adjacent vertices, the difference of their labels is the $j$th power of a prime, for $j leq k$ (respectively, the $k$th power of a prime exactly). We prove that $ppn(K_n) = lceil log_2(n)rceil - 1$, and for a nonempty $k$-chromatic graph $G$, $ppn(G) = lceil log_2(k)rceil - 1$ or $ppn(G) = lceil log_2(k)rceil$. We determine $ppn(G)$ for all complete bipartite, 3-partite, and 4-partite graphs. We prove that $K_n$ is a prime $k$th-power graph if and only if $n < 7$, and we determine conditions on cycles and outerplanar graphs $G$ for which $G$ is a strict prime $k$th-power graph. We find connections between prime product and prime power distance graphs and the Twin Prime Conjecture, the Green-Tao Theorem, and Fermats Last Theorem.
The strong chromatic index of a graph $G$, denoted $chi_s(G)$, is the least number of colors needed to edge-color $G$ so that edges at distance at most two receive distinct colors. The strong list chromatic index, denoted $chi_{s,ell}(G)$, is the least integer $k$ such that if arbitrary lists of size $k$ are assigned to each edge then $G$ can be edge-colored from those lists where edges at distance at most two receive distinct colors. We use the discharging method, the Combinatorial Nullstellensatz, and computation to show that if $G$ is a subcubic planar graph with $operatorname{girth}(G) geq 41$ then $chi_{s,ell}(G) leq 5$, answering a question of Borodin and Ivanova [Precise upper bound for the strong edge chromatic number of sparse planar graphs, Discuss. Math. Graph Theory, 33(4), (2014) 759--770]. We further show that if $G$ is a subcubic planar graph and $operatorname{girth}(G) geq 30$, then $chi_s(G) leq 5$, improving a bound from the same paper. Finally, if $G$ is a planar graph with maximum degree at most four and $operatorname{girth}(G) geq 28$, then $chi_s(G) leq 7$, improving a more general bound of Wang and Zhao from [Odd graphs and its application on the strong edge coloring, arXiv:1412.8358] in this case.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
