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 this paper we obtain closed formulae for several parameters of generalized Sierpiński graphs S(G,t) in terms of parameters of the base graph G. In particular, we focus on the chromatic, vertex cover, clique and domination numbers.
A vertex w of a connected graph G strongly resolves two vertices u,v∈V(G), if there exists some shortest u−w path containing v or some shortest v−w path containing u. A set S of vertices is a strong metric generator for G if every pair of vertices of G is strongly resolved by some vertex of S. The smallest cardinality of a strong metric generator for G is called the strong metric dimension of G. In this paper we obtain several tight bounds or closed formulae for the strong metric dimension of the Cartesian sum of graphs in terms of the strong metric dimension, clique number or twins-free clique number of its factor graphs.
As a generalization of the concept of a metric basis, this article introduces the notion of k-metric basis in graphs. Given a connected graph G=(V,E), a set S⊆V is said to be a k-metric generator for G if the elements of any pair of different vertices of G are distinguished by at least k elements of S, i.e., for any two different vertices u,v∈V, there exist at least k vertices w1,w2,...,wk∈S such that dG(u,wi)=dG(v,wi) for every i∈{1,...,k}. A metric generator of minimum cardinality is called a k-metric basis and its cardinality the k-metric dimension of G. A connected graph G is k-metric dimensional if k is the largest integer such that there exists a k-metric basis for G. We give a necessary and sufficient condition for a graph to be k-metric dimensional and we obtain several results on the k-metric dimension.
For an ordered subset W={w1,w2,…wk} 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(v,w1),d(v,w2),…, d(v,wk)), 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 \emph{local metric basis} for G and its cardinality the \emph{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.
A set S of vertices of a graph G is a defensive k-alliance in G if every vertex of S has at least k more neighbors inside of S than outside. This is primarily an expository article surveying the principal known results on defensive alliances in graph. Its seven sections are: Introduction, Computational complexity and realizability, Defensive k-alliance number, Boundary defensive k-alliances, Defensive alliances in Cartesian product graphs, Partitioning a graph into defensive k-alliances, and Defensive k-alliance free sets.
The metric dimension is quite a well-studied graph parameter. Recently, the adjacency metric dimension and the local metric dimension have been introduced. We combine these variants and introduce the local adjacency metric dimension. We show that the (local) metric dimension of the corona product of a graph of order n and some non-trivial graph H equals n times the (local) adjacency metric dimension of H. This strong relation also enables us to infer computational hardness results for computing the (local) metric dimension, based on according hardness results for (local) adjacency metric dimension that we also provide. We also study combinatorial properties of the strong product of graphs and emphasize the role different types of twins play in determining in particular the adjacency metric dimension of a graph.
Let G be a connected graph. A vertex w {\em strongly resolves} a pair u,v of vertices of G if there exists some shortest u−w path containing v or some shortest v−w path containing u. A set W of vertices is a {\em strong resolving set} for G if every pair of vertices of G is strongly resolved by some vertex of W. The smallest cardinality of a strong resolving set for G is called the {\em strong metric dimension} of G. It is known that the problem of computing the strong metric dimension of a graph is NP-hard. In this paper we obtain closed formulae for the strong metric dimension of several families of Cartesian product graphs and direct product graphs.
Let G be a connected graph. A vertex w∈V(G) strongly resolves two vertices u,v∈V(G) if there exists some shortest u−w path containing v or some shortest v−w path containing u. A set S of vertices is a strong metric generator for G if every pair of vertices of G is strongly resolved by some vertex of S. The smallest cardinality of a strong metric generator for G is called the strong metric dimension of G. It is well known that the problem of computing this invariant is NP-hard. In this paper we study the problem of finding exact values or sharp bounds for the strong metric dimension of strong product graphs and express these in terms of invariants of the factor graphs.
Let G be a connected graph. A vertex w strongly resolves a pair u, v of vertices of G if there exists some shortest u−w path containing v or some shortest v−w path containing u. A set W of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of W. The smallest cardinality of a strong resolving set for G is called the strong metric dimension of G. It is known that the problem of computing this invariant is NP-hard. This suggests finding the strong metric dimension for special classes of graphs or obtaining good bounds on this invariant. In this paper we study the problem of finding exact values or sharp bounds for the strong metric dimension of rooted product of graphs and express these in terms of invariants of the factor graphs.
A global offensive alliance in a graph G is a set S of vertices with the property that every vertex not belonging to S has at least one more neighbor in S than it has outside of S. The global offensive alliance number of G, γo(G), is the minimum cardinality of a global offensive alliance in G. A set S of vertices of a graph G is a dominating set for G if every vertex not belonging to S has at least one neighbor in S. The domination number of G, γ(G), is the minimum cardinality of a dominating set of G. In this work we obtain closed formulas for the global offensive alliance number of several families of Cartesian product graphs, we also prove that γo(G□H)≥2γ(G)γo(H) for any graphs G and H and we show that if G has an efficient dominating set, then γo(G□H)≥γ(G)γo(H). Moreover, we present a Vizing-like conjecture for the global offensive alliance number and we prove it for several families of graphs.
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.