Computing the local metric dimension of a graph from the local metric dimension of primary subgraphs

For an ordered subset W= w₁, w₂,?…?w_k of vertices and a vertex u in a connected graph G, the representation of u with respect to W is the ordered k-tuple r(u|W)=(d(u, w₁), d(u, w₂),?…?, d(u, w_k)), where d(x, y) represents the distance between the vertices x and y. The set W is a local metric generator for G if every two adjacent vertices of G have distinct representations. A minimum local metric generator is called a local metric basis for G and its cardinality the local metric dimension of G. We show that the computation of the local metric dimension of a graph with cut vertices is reduced to the computation of the local metric dimension of the so-called primary subgraphs. The main results are applied to specific constructions including bouquets of graphs, rooted product graphs, corona product graphs, block graphs and chain of graphs.     

Computing the metric dimension of the categorial product of some graphs

A set of vertices W is a resolving set of a graph G if every two vertices of G have distinct representations of distances with respect to the set W. The number of vertices in a smallest resolving set is called the metric dimension. This invariant has extensive applications in robotics, since the metric dimension can represent the minimum number of landmarks, which uniquely determine the position of a robot moving in a graph space. Finding the metric dimension of a graph is a non-deterministic polynomial-time hard problem. We present exact values of the metric dimension of several networks, which can be obtained as categorial products of graphs.     

Strong product of factor-critical graphs

Strong product G ₁? G ₂ of two graphs G ₁ and G ₂ has a vertex set V(G ₁)×V(G ₂) and two vertices (u ₁, v ₁) and (u ₂, v ₂) are adjacent whenever u ₁=u ₂ and v ₁ is adjacent to v ₂ or u ₁ is adjacent to u ₂ and v ₁=v ₂, or u ₁ is adjacent to u ₂ and v ₁ is adjacent to v ₂. We investigate the factor-criticality of G ₁? G ₂ and obtain the following. Let G ₁ and G ₂ be connected m-factor-critical and n-factor-critical graphs, respectively. Then i. if m? 0, n=0, |V(G ₁)|? 2m+2 and |V(G ₂)|? 4, then G ₁? G ₂ is (2m+2)-factor-critical;

ii. if n=1, |V(G ₁)|? 2m+3 and either m? 3 or |V(G ₂)|? 5, then G ₁? G ₂ is (2m+4??)-factor-critical, where ?=0 if m is even, otherwise ?=1;

iii. if m+2 ? |V(G ₁)|? 2m+2, or n+2? |V(G ₂)|? 2n+2, then G ₁? G ₂ is mn-factor-critical;

iv. if |V(G ₁)|? 2m+3 and |V(G ₂)|? 2n+3, then G ₁? G ₂ is (mn?min{[3m/2]₂, [3n/2]₂})-factor-critical.

     

The differential of the strong product graphs

Let G=(V, E) be a graph of order n and let B(D) be the set of vertices in V ? D that have a neighbour in the set D. The differential of a set D is defined as ? (D)=|B(D)|?|D| and the differential of a graph to equal the maximum value of ?(D) for any subset D of V. In this paper we obtain several tight bounds for the differential of strong product graphs. In particular, we investigate the relationship between the differential of this type of product graphs and various parameters in the factors of the product.     

On the partition dimension of a class of circulant graphs

For a vertex v   of a connected graph G(V,E)$G(V,E)$ and a subset S of V, the distance between a vertex v and S   is defined by d(v,S)=min{d(v,x):x∈S}$d(v,S)=\min \{d(v,x):x\in S\}$. For an ordered k  -partition π={_S1,_S2…_Sk}$\pi =\{S_1,S_2\dots S_k\}$ of V, the partition representation of v with respect to π is the k  -vector r(v|π)=(d(v,_S1),d(v,_S2)…d(v,_Sk))$r(v|\pi )=(d(v,S_1),d(v,S_2)\dots d(v,S_k))$. The k-partition π is a resolving partition if the k  -vectors r(v|π)$r(v|\pi )$, v∈V(G)$v\in V(G)$ are distinct. The minimum k for which there is a resolving k-partition of V is the partition dimension of G. Salman et al. [1] in their paper which appeared in Acta Mathematica Sinica, English Series   proved that partition dimension of a class of circulant graph G(n,±{1,2})$G(n,\pm \{1,2\})$, for all even n?6$n?6$ is four. In this paper we prove that it is three.     

Linear-time algorithms for problems on planar graphs with fixed disk dimension

The disk dimension of a planar graph G is the least number k for which G embeds in the plane minus k open disks, with every vertex on the boundary of some disk. Useful properties of graphs with a given disk dimension are derived, leading to an algorithm to obtain an outerplanar subgraph of a graph with disk dimension k by removing at most 2k−2 vertices. This reduction is used to obtain linear-time exact and approximation algorithms on graphs with fixed disk dimension. In particular, a linear-time approximation algorithm is presented for the pathwidth problem.     

Fault diameter of product graphs

The (k−1)-fault diameter Dk(G) of a k-connected graph G is the maximum diameter of an induced subgraph by deleting at most k−1 vertices from G. This paper considers the fault diameter of the product graph G₁∗G₂ of two graphs G₁ and G₂ and proves that Dk₁+k₂(G₁∗G₂)?Dk₁(G₁)+Dk₂(G₂)+1 if G₁ is k₁-connected and G₂ is k₂-connected. This generalizes some known results such as Bani? and ?erovnik [I. Bani?, J. ?erovnik, Fault-diameter of Cartesian graph bundles, Inform. Process. Lett. 100 (2) (2006) 47-51].     

Edge-fault-tolerant pancyclicity and bipancyclicity of Cartesian product graphs with faulty edges

Let r≥ 4 be an even integer. Graph G is r-bipancyclic if it contains a cycle of every even length from r to $2\lfloor \frac{n(G)}{2}\rfloor$, where $n(G)$ is the number of vertices in G. A graph G is r-pancyclic if it contains a cycle of every length from r to $n(G)$, where $r\ge 3$. A graph is k-edge-fault Hamiltonian if, after deleting arbitrary k edges from the graph, the resulting graph remains Hamiltonian. The terms k-edge-fault r-bipancyclic and k-edge-fault r-pancyclic can be defined similarly. Given two graphs G and H, where $n(G)$, $n(H)\ge$ 9, let $k_1$, $k_2\ge 5$ be the minimum degrees of G and H, respectively. This study determined the edge-fault r-bipancyclic and edge-fault r-pancyclic of Cartesian product graph $G\times H$ with some conditions. These results were then used to evaluate the edge-fault pancyclicity (bipancyclicity) of ${\mathit{NQ}}_{m_r,\dots ,m_1}$ and ${\mathit{GQ}}_{m_r,\dots ,m_1}$.     

Strong matching preclusion for two-dimensional torus networks

The torus network is one of the most popular interconnection networks for massively parallel computing systems. The strong matching preclusion number of a graph is the minimum number of vertices and edges whose deletion results in a graph that has neither perfect matchings nor almost perfect matchings. In this paper, we establish the strong matching preclusion number and classify all optimal solutions for the two-dimensional torus network with an odd number of vertices.     

Strong matching preclusion of burnt pancake graphs

The strong matching preclusion number of a graph is the minimum number of vertices and edges whose deletion results in a graph that has neither perfect matchings nor almost perfect matchings. This is an extension of the matching preclusion problem that was introduced by Park and Ihm. The burnt pancake graph is a more complex variant of the pancake graph. In this paper, we examine the properties of burnt pancake graphs by finding its strong matching preclusion number and categorising all optimal solutions.     

On Clark and Suen bound-type results for k-domination and Roman domination of Cartesian product graphs

A set S of vertices of a graph G is a dominating set for G if every vertex of G is adjacent to at least one vertex of S. The domination number γ(G), of G, is the minimum cardinality of a dominating set in G. Moreover, if the maximum degree of G is Δ, then for every positive integer k≤Δ, the set S is a k-dominating set in G if every vertex outside of S is adjacent to at least k vertices of S. The k-domination number of G, denoted by γ _k (G), is the minimum cardinality of a k-dominating set in G. A map f: V→<texlscub>0, 1, 2</texlscub>is a Roman dominating function for G if for every vertex v with f(v)=0, there exists a vertex u∈N(v) such that f(u)=2. The weight of a Roman dominating function is f(V)=∑ _u∈V f(u). The Roman domination number γ_R(G), of G, is the minimum weight of a Roman dominating function on G. In this paper, we obtain that for any two graphs G and H, the k-domination number of the Cartesian product of G and H is bounded below by γ(G)γ _k (H)/2. Also, we obtain that the domination number of Cartesian product of G and H is bounded below by γ(G)γ_R(H)/3.     

Resolvability and the upper dimension of graphs

For an ordered set W = {w₁, w₂,…, w_k} of vertices and a vertex v in a connected graph G, the (metric) representation of v with respect to W is the k-vector r(v | W) = (d(v, w₁), d(v, w₂),…, d(v, w_k)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations. A new sharp lower bound for the dimension of a graph G in terms of its maximum degree is presented.

A resolving set of minimum cardinality is a basis for G and the number of vertices in a basis is its (metric) dimension dim(G). A resolving set S of G is a minimal resolving set if no proper subset of S is a resolving set. The maximum cardinality of a minimal resolving set is the upper dimension dim⁺(G). The resolving number res(G) of a connected graph G is the minimum k such that every k-set W of vertices of G is also a resolving set of G. Then 1 ≤ dim(G) ≤ dim⁺(G) ≤ res(G) ≤ n − 1 for every nontrivial connected graph G of order n. It is shown that dim⁺(G) = res(G) = n − 1 if and only if G = K_n, while dim⁺(G) = res(G) = 2 if and only if G is a path of order at least 4 or an odd cycle.

The resolving numbers and upper dimensions of some well-known graphs are determined. It is shown that for every pair a, b of integers with 2 ≤ a ≤ b, there exists a connected graph G with dim(G) = dim⁺(G) = a and res(G) = b. Also, for every positive integer N, there exists a connected graph G with res(G) − dim⁺(G) ≥ N and dim⁺(G) − dim(G) ≥ N.     

Equivalence of a behavioral distance and the gap metric

In this article it is shown that for the class of stable linear state space systems with a fixed MacMillan degree, the topology of the gap between the graphs of the systems is equivalent to the topology of the gap between the extended graphs of the systems.     

基于强正则蕴涵算子的加权模糊度量空间

在强正则蕴涵算子的统一框架下给出了加权正则度量的定义,建立了基于强正则蕴涵算子的加权正则模糊度量空间,并且研究了该模糊度量空间的性质,分析了常用的逻辑连接词所对应的映射关于加权正则度量的连续性,最后证明了基于Lukasiewicz蕴涵的加权正则模糊度量空间是最适宜于展开模糊推理的模糊度量空间。     

Stability of control systems and graphs of linear systems

New conditions for internal stability of a closed-loop control system are given in terms of the graphs of the multiplication operators induced by the transfer functions of the plant and the controller. These conditions can be given a geometrical interpretation. This relates closed-loop stability to the minimal angle between the graph space associated with the system and the graph space associated with the controller. The maximally stabilizing controller is defined as the controller that maximizes the minimum angle between the graph space associated with the system and the graph space associated with the controller. It is shown that this controller can be calculated as a Nehari extension of the coprime factors of the system.     

网络拓扑的超能整循环图构造

循环图是一类重要的网络拓扑结构图,在并行计算和分布计算中发挥重要作用。图[G]的能量[E(G)]定义为图的特征值的绝对值之和。具有[n]个顶点的图[G]称为超能图如果图[G]的能量[E(G)>2n-2]。一个图称为循环图,若它是循环群上的Cayley图,即它的邻接矩阵是一个循环矩阵;整循环图是指循环图的特征值全为整数。借助Ramanujans和,利用Euler函数和Mobius函数,讨论了整循环图的超能性。利用Cartesian积图给出了一个构造超能整循环图的方法。     

Local colourings of Cartesian product graphs

A local colouring of a graph G is a function c: V(G)→? such that for each S ? V(G), 2≤|S|≤3, there exist u, v∈S with |c(u)?c(v)| at least the number of edges in the subgraph induced by S. The maximum colour assigned by c is the value χ_?(c) of c, and the local chromatic number of G is χ_?(G)=min {χ_?(c): c is a local colouring of G}. In this note the local chromatic number is determined for Cartesian products G □ H, where G and GH are 3-colourable graphs. This result in part corrects an error from Omoomi and Pourmiri [On the local colourings of graphs, Ars Combin. 86 (2008), pp. 147–159]. It is also proved that if G and H are graphs such that χ(G)≤? χ_?(H)/2 ?, then χ_?(G □ H)≤χ_?(H)+1.