On the metric dimension of HDN

The concept of metric basis is useful for robot navigation. In graph G, a robot is aware of its current location by sending signals to obtain the distances between itself and the landmarks in G. Its position is determined uniquely in G if it knows its distances to sufficiently many landmarks. The metric basis of G is defined as the minimum set of landmarks such that all other vertices in G can be uniquely determined and the metric dimension of G is defined as the cardinality of the minimum set of landmarks. The major contribution of this paper is that we have partly solved the open problem proposed by Manuel et al. [9], by proving that the metric dimension of $\text{HDN1}(n)$ and $\text{HDN2}(n)$ are either 3 or 4. However, the problem of finding the exact metric dimension of HDN networks is still open.     

On minimum metric dimension of honeycomb networks

A minimum metric basis is a minimum set W of vertices of a graph G(V,E) such that for every pair of vertices u and v of G, there exists a vertex wW with the condition that the length of a shortest path from u to w is different from the length of a shortest path from v to w. The honeycomb and hexagonal networks are popular mesh-derived parallel architectures. Using the duality of these networks we determine minimum metric bases for hexagonal and honeycomb networks.     

On the metric dimension of incidence graphs

A resolving set for a graph $\Gamma$ is a collection of vertices $S$, chosen so that for each vertex $v$, the list of distances from $v$ to the members of $S$ uniquely specifies $v$. The metric dimension$\mu \left(\Gamma \right)$ is the smallest size of a resolving set for $\Gamma$. We consider the metric dimension of two families of incidence graphs: incidence graphs of symmetric designs, and incidence graphs of symmetric transversal designs (i.e. symmetric nets). These graphs are the bipartite distance-regular graphs of diameter 3, and the bipartite, antipodal distance-regular graphs of diameter 4, respectively. In each case, we use the probabilistic method in the manner used by Babai to obtain bounds on the metric dimension of strongly regular graphs, and are able to show that $\mu \left(\Gamma \right)=O(\sqrt{n}logn)$ (where $n$ is the number of vertices).     

Commutative rings whose zero-divisor graph is a proper refinement of a star graph

A graph is called a proper refinement of a star graph if it is a refinement of a star graph, but it is neither a star graph nor a complete graph. For a refinement of a star graph G with center c, let G _c ^* be the subgraph of G induced on the vertex set V (G)\ {c or end vertices adjacent to c}. In this paper, we study the isomorphic classification of some finite commutative local rings R by investigating their zero-divisor graphs G = Γ(R), which is a proper refinement of a star graph with exactly one center c. We determine all finite commutative local rings R such that G _c ^* has at least two connected components. We prove that the diameter of the induced graph G _c ^* is two if Z(R)² ≠ {0}, Z(R)³ = {0} and G _c ^* is connected. We determine the structure of R which has two distinct nonadjacent vertices α, β ∈ Z(R)* \ {c} such that the ideal [N(α) ∩ N(β)]∪ {0} is generated by only one element of Z(R)*\{c}. We also completely determine the correspondence between commutative rings and finite complete graphs K _n with some end vertices adjacent to a single vertex of K _n .     

Discrepancies between metric dimension and partition dimension of a connected graph

Let and be graphs where the set of vertices is the set of points of the integer lattice and the set of edges consists of all pairs of vertices whose city block and chessboard distances, respectively, are 1.In this paper it is shown that the partition dimensions of these graphs are 3 and 4, respectively, while their metric dimensions are not finite. Also, for every n3 there exists an induced subgraph of of order 3n-1 with metric dimension n and partition dimension 3. These examples will answer a question raised by Chartrand, Salehi and Zhang. Furthermore, graphs of order n9 having partition dimension n-2 are characterized, thus completing the characterization of graphs of order n having partition dimension 2, n, or n-1 given by Chartrand, Salehi and Zhang. The list of these graphs includes 23 members.     

The metric dimension of Cayley digraphs

A vertex x in a digraph D is said to resolve a pair u, v of vertices of D if the distance from u to x does not equal the distance from v to x. A set S of vertices of D is a resolving set for D if every pair of vertices of D is resolved by some vertex of S. The smallest cardinality of a resolving set for D, denoted by dim(D), is called the metric dimension for D. Sharp upper and lower bounds for the metric dimension of the Cayley digraphs Cay(Δ:Γ), where Γ is the group Z_n1⊕Z_n2⊕?⊕Z_nm and Δ is the canonical set of generators, are established. The exact value for the metric dimension of Cay({(0,1),(1,0)}:Z_n⊕Z_m) is found. Moreover, the metric dimension of the Cayley digraph of the dihedral group D_n of order 2n with a minimum set of generators is established. The metric dimension of a (di)graph is formulated as an integer programme. The corresponding linear programming formulation naturally gives rise to a fractional version of the metric dimension of a (di)graph. The fractional dual implies an integer dual for the metric dimension of a (di)graph which is referred to as the metric independence of the (di)graph. The metric independence of a (di)graph is the maximum number of pairs of vertices such that no two pairs are resolved by the same vertex. The metric independence of the n-cube and the Cayley digraph Cay(Δ:D_n), where Δ is a minimum set of generators for D_n, are established.     

On the Constant Metric Dimension of Generalized Petersen Graphs P（n, 4）

In this paper,we consider the family of generalized Petersen graphs P(n,4).We prove that the metric dimension of P(n,4) is 3 when n ≡ 0(mod 4),and is 4 when n = 4k + 3(k is even).For n ≡ 1,2(mod 4) and n = 4k + 3(k is odd),we prove that the metric dimension of P(n,4) is bounded above by 4.This shows that each graph of the family of generalized Petersen graphs P(n,4)has constant metric dimension.     

The structure of zero-divisor semigroups with graph K n ○K 2

This paper determines all commutative zero divisor semigroups whose zero divisor graph is a complete graph (finite or infinite), or a complete graph (finite or infinite) with one additional end vertex, and gives formulas for the numbers of all such semigroups with n elements. The research of T. Wu is supported by the National Natural Science Foundation of China (Grant No. 10671122) and the Natural Science Foundation of Shanghai (Grant No. 06ZR14049).     

On endomorphism-regularity of zero-divisor graphs

The paper studies the following question: Given a ring R, when does the zero-divisor graph Γ(R) have a regular endomorphism monoid? We prove if R contains at least one nontrivial idempotent, then Γ(R) has a regular endomorphism monoid if and only if R is isomorphic to one of the following rings: Z₂×Z₂×Z₂; Z₂×Z₄; Z₂×(Z₂[x]/(x²)); F₁×F₂, where F₁,F₂ are fields. In addition, we determine all positive integers n for which Γ(Z_n) has the property.     

Sub-semigroups determined by the zero-divisor graph

In this paper we study sub-semigroups of a finite or an infinite zero-divisor semigroup S determined by properties of the zero-divisor graph Γ(S). We use these sub-semigroups to study the correspondence between zero-divisor semigroups and zero-divisor graphs. In particular, we discover a class of sub-semigroups of reduced semigroups and we study properties of sub-semigroups of finite or infinite semilattices with the least element. As an application, we provide a characterization of the graphs which are zero-divisor graphs of Boolean rings. We also study how local property of Γ(S) affects global property of the semigroup S, and we discover some interesting applications. In particular, we find that no finite or infinite two-star graph has a corresponding nil semigroup.     

The fractional metric dimension of permutation graphs

Let G =(V(G), E(G)) be a graph with vertex set V(G) and edge set E(G). For two distinct vertices x and y of a graph G, let RG{x, y} denote the set of vertices z such that the distance from x to z is not equa l to the distance from y to z in G. For a function g defined on V(G) and for U■V(G), let g(U) =∑s∈Ug(s). A real-valued function g : V(G) → [0, 1] is a resolving function of G if g(RG{x, y}) ≥ 1 for any two distinct vertices x, y ∈ V(G). The fractional metric dimension dimf(G)of a graph G is min{g(V(G)) : g is a resolving function of G}. Let G1 and G2 be disjoint copies of a graph G, and let σ : V(G1) → V(G2) be a bijection. Then, a permutation graph Gσ =(V, E) has the vertex set V = V(G1) ∪ V(G2) and the edge set E = E(G1) ∪ E(G2) ∪ {uv | v = σ(u)}. First,we determine dimf(T) for any tree T. We show that 1 dimf(Gσ) ≤1/2(|V(G)| + |S(G)|) for any connected graph G of order at least 3, where S(G) denotes the set of support vertices of G. We also show that, for any ε 0, there exists a permutation graph Gσ such that dimf(Gσ)- 1 ε. We give examples showing that neither is there a function h1 such that dimf(G) h1(dimf(Gσ)) for all pairs(G, σ), nor is there a function h2 such that h2(dimf(G)) dimf(Gσ) for all pairs(G, σ). Furthermore,we investigate dimf(Gσ) when G is a complete k-partite graph or a cycle.     

On strong metric dimension of graphs and their complements

A vertex x in a graph G strongly resolves a pair of vertices v, w if there exists a shortest x-w path containing v or a shortest x-v path containing w in G. A set of vertices S■V(G) is a strong resolving set of G if every pair of distinct vertices of G is strongly resolved by some vertex in S. The strong metric dimension of G, denoted by sdim(G), is the minimum cardinality over all strong resolving sets of G. For a connected graph G of order n≥2, we characterize G such that sdim(G) equals 1, n-1, or n-2, respectively. We give a Nordhaus-Gaddum-type result for the strong metric dimension of a graph and its complement: for a graph G and its complement G, each of order n≥4 and connected, we show that 2≤sdim(G)+sdim(G)≤2( n-2). It is readily seen that sdim(G)+sdim(G)=2 if and only if n=4; we show that, when G is a tree or a unicyclic graph, sdim(G)+sdim(G)=2(n 2) if and only if n=5 and G ～=G ～=C5, the cycle on five vertices. For connected graphs G and G of order n≥5, we show that 3≤sdim(G)+sdim(G)≤2(n-3) if G is a tree; we also show that 4≤sdim(G)+sdim(G)≤2(n-3) if G is a unicyclic graph of order n≥6. Furthermore, we characterize graphs G satisfying sdim(G)+sdim(G)=2(n-3) when G is a tree or a unicyclic graph.     

Topological graph dimension

In the invited chapter Discrete Spatial Models of the book Handbook of Spatial Logics, we have introduced the concept of dimension for graphs, which is inspired by Evako’s idea of dimension of graphs [A.V. Evako, R. Kopperman, Y.V. Mukhin, Dimensional properties of graphs and digital spaces, J. Math. Imaging Vision 6 (1996) 109-119]. Our definition is analogous to that of (small inductive) dimension in topology. Besides the expected properties of isomorphism-invariance and monotonicity with respect to subgraph inclusion, it has the following distinctive features:

•

Local aspect. That is, dimension at a vertex is basic, and the dimension of a graph is obtained as the sup over its vertices.

•

Dimension of a strong product G×H is dim(G)+dim(H) (for non-empty graphs G,H).

In this paper we present a short account of the basic theory, with several new applications and results.     

On the diameter and girth of a zero-divisor graph

For a commutative ring R with zero-divisors Z(R), the zero-divisor graph of R is Γ(R)=Z(R)−{0}, with distinct vertices x and y adjacent if and only if xy=0. In this paper, we characterize when either or . We then use these results to investigate the diameter and girth for the zero-divisor graphs of polynomial rings, power series rings, and idealizations.