BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
In a graph G, a vertex dominates itself and its neighbours. A subset S⊆V(G) is said to be a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality among all double dominating sets of G is the double domination number. In this article, we obtain tight bounds and closed formulas for the double domination number of lexicographic product graphs G∘H in terms of invariants of the factor graphs G and H.
In this article, we obtain closed formulae for the Italian domination number of rooted product graphs. As a particular case of the study, we derive the corresponding formulas for corona graphs, and we provide an alternative proof that the problem of computing the Italian domination number of a graph is NP-hard.
Let G=(V,E) be a simple connected graph and di be the degree of its ith vertex. In a recent paper [J. Math. Chem. 46 (2009) 1369-1376] the first geometric-arithmetic index of a graph G was defined as GA1=∑ij∈Edi+dj2didj. This graph invariant is useful for chemical proposes. The main use of GA1 is for designing so-called quantitative structure-activity relations and quantitative structure-property relations. In this paper we obtain new inequalities involving the geometric-arithmetic index GA1 and characterize the graphs which make the inequalities tight. In particular, we improve some known results, generalize other, and we relate GA1 to other well-known topological indices.
The metric dimension of a general metric space was defined in 1953, applied to the set of vertices of a graph metric in 1975, and developed further for metric spaces in 2013. It was then generalised in 2015 to the k-metric dimension of a graph for each positive integer k, where k=1 corresponds to the original definition. Here, we discuss the k-metric dimension of general metric spaces.
Let (X,d) be a metric space. A set S⊆X is said to be a k-metric generator for X if and only if for any pair of different points u,v∈X, there exist at least k points w1,w2,…wk∈S such that $d(u,w_i)\ne d(v,w_i),\; \mbox{\rm for all}\; i\in \{1, \ldots k\}.$ Let Rk(X) be the set of metric generators for X. The k-metric dimension dimk(X) of (X,d) is defined as dimk(X)=inf{∣S∣:S∈Rk(X)}. Here, we discuss the k-metric dimension of (V,dt), where V is the set of vertices of a simple graph G and the metric dt:V×V→N∪{0} is defined by dt(x,y)=min{d(x,y),t} from the geodesic distance d in G and a positive integer t. The case t≥D(G), where D(G) denotes the diameter of G, corresponds to the original theory of k-metric dimension and the case t=2 corresponds to the theory of k-adjacency dimension. Furthermore, this approach allows us to extend the theory of k-metric dimension to the general case of non-necessarily connected graphs.
A generator of a metric space is a set S of points in the space with the property that every point of the space is uniquely determined by its distances from the elements of S. Given a simple graph G=(V,E), we define the distance function dG,2:V×V→N∪{0}, as dG,2(x,y)=min{dG(x,y),2}, where dG(x,y) is the length of a shortest path between x and y and N is the set of positive integers. Then (V,dG,2) is a metric space. We say that a set S⊆V is a k-adjacency generator for G if for every two vertices x,y∈V, there exist at least k vertices w1,w2,...,wk∈S such that $$d_{G,2}(x,w_i)\ne d_{G,2}(y,w_i),\; \mbox{for every}\; i\in \{1,...,k\}.$$ A minimum cardinality k-adjacency generator is called a k-adjacency basis of G and its cardinality, the k-adjacency dimension of G. In this article we study the problem of finding the k-adjacency dimension of a graph. We give some necessary and sufficient conditions for the existence of a k-adjacency basis of an arbitrary graph G and we obtain general results on the k-adjacency dimension, including general bounds and closed formulae for some families of graphs. In particular, we obtain closed formulae for the k-adjacency dimension of join graphs G+H in terms of the k-adjacency dimension of G and H. These results concern the k-metric dimension, as join graphs have diameter two. As we can expect, the obtained results will become important tools for the study of the k-metric dimension of lexicographic product graphs and corona product graphs.
We show that the principal results of the article "The metric dimension of graph with pendant edges" [Journal of Combinatorial Mathematics and Combinatorial Computing, 65 (2008) 139--145] do not hold. In this paper we correct the results and we solve two open problems described in the above mentioned paper.
Given a set of vertices S={v1,v2,...,vk} of a connected graph G, the metric representation of a vertex v of G with respect to S is the vector r(v∣S)=(d(v,v1),d(v,v2),...,d(v,vk)), where d(v,vi), i∈{1,...,k} denotes the distance between v and vi. S is a resolving set for G if for every pair of vertices u,v of G, r(u∣S)=r(v∣S). The metric dimension of G, dim(G), is the minimum cardinality of any resolving set for G. Let G and H be two graphs of order n1 and n2, respectively. The corona product G⊙H is defined as the graph obtained from G and H by taking one copy of G and n1 copies of H and joining by an edge each vertex from the ith-copy of H with the ith-vertex of G. For any integer k≥2, we define the graph G⊙kH recursively from G⊙H as G⊙kH=(G⊙k−1H)⊙H. We give several results on the metric dimension of G⊙kH. For instance, we show that given two connected graphs G and H of order n1≥2 and n2≥2, respectively, if the diameter of H is at most two, then dim(G⊙kH)=n1(n2+1)k−1dim(H). Moreover, if n2≥7 and the diameter of H is greater than five or H is a cycle graph, then dim(G⊙kH)=n1(n2+1)k−1dim(K1⊙H).
A \emph{defensive} (\emph{offensive}) k-\emph{alliance} in Γ=(V,E) is a set S⊆V such that every v in S (in the boundary of S) has at least k more neighbors in S than it has in V∖S. A set X⊆V is \emph{defensive} (\emph{offensive}) k-\emph{alliance free,} if for all defensive (offensive) k-alliance S, S∖X=∅, i.e., X does not contain any defensive (offensive) k-alliance as a subset. A set Y⊆V is a \emph{defensive} (\emph{offensive}) k-\emph{alliance cover}, if for all defensive (offensive) k-alliance S, S∩Y=∅, i.e., Y contains at least one vertex from each defensive (offensive) k-alliance of Γ. In this paper we show several mathematical properties of defensive (offensive) k-alliance free sets and defensive (offensive) k-alliance cover sets, including tight bounds on the cardinality of defensive (offensive) k-alliance free (cover) sets.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.