This page has only limited features, please log in for full access.
For a graph G=(V(G),E(G)), an Italian dominating function (ID function) of G is a function f:V(G)→{0,1,2} such that for each vertex v∈V(G) with f(v)=0, f(N(v))≥2, that is, either there is a vertex u∈N(v) with f(u)=2 or there are two vertices x,y∈N(v) with f(x)=f(y)=1. A function f:V(G)→{0,1,2} is a covering Italian dominating function (CID function) of G if f is an ID function and {v∈V(G)∣f(v)≠0} is a vertex cover set. The covering Italian domination number (CID number) γcI(G) is the minimum weight taken over all CID functions of G. In this paper, we study the CID number in graphs. We show that the problem of computing this parameter is NP-hard even when restricted to some well-known families of graphs, and find some bounds on this parameter. We characterize the family of graphs for which their CID numbers attain the upper bound twice their vertex cover number as well as all claw-free graphs whose CID numbers attain the lower bound half of their orders. We also give the characterizations of some families of graphs with small CID numbers.
Abdollah Khodkar; Doost Ali Mojdeh; Babak Samadi; Ismael G. Yero. Covering Italian domination in graphs. Discrete Applied Mathematics 2021, 304, 324 -331.
AMA StyleAbdollah Khodkar, Doost Ali Mojdeh, Babak Samadi, Ismael G. Yero. Covering Italian domination in graphs. Discrete Applied Mathematics. 2021; 304 ():324-331.
Chicago/Turabian StyleAbdollah Khodkar; Doost Ali Mojdeh; Babak Samadi; Ismael G. Yero. 2021. "Covering Italian domination in graphs." Discrete Applied Mathematics 304, no. : 324-331.
Let G be a graph. The Steiner distance of \(W\subseteq V(G)\) is the minimum size of a connected subgraph of G containing W. Such a subgraph is necessarily a tree called a Steiner W-tree. The set \(A\subseteq V(G)\) is a k-Steiner general position set if \(V(T_B)\cap A = B\) holds for every set \(B\subseteq A\) of cardinality k, and for every Steiner B-tree \(T_B\). The k-Steiner general position number \(\mathrm{sgp}_k(G)\) of G is the cardinality of a largest k-Steiner general position set in G. Steiner cliques are introduced and used to bound \(\mathrm{sgp}_k(G)\) from below. The k-Steiner general position number is determined for trees, cycles and joins of graphs. Lower bounds are presented for split graphs, infinite grids and lexicographic products. The lower bound for the latter product leads to an exact formula for the general position number of an arbitrary lexicographic product.
Sandi Klavžar; Dorota Kuziak; Iztok Peterin; Ismael G. Yero. A Steiner general position problem in graph theory. Computational and Applied Mathematics 2021, 40, 1 -15.
AMA StyleSandi Klavžar, Dorota Kuziak, Iztok Peterin, Ismael G. Yero. A Steiner general position problem in graph theory. Computational and Applied Mathematics. 2021; 40 (6):1-15.
Chicago/Turabian StyleSandi Klavžar; Dorota Kuziak; Iztok Peterin; Ismael G. Yero. 2021. "A Steiner general position problem in graph theory." Computational and Applied Mathematics 40, no. 6: 1-15.
An outer independent (double) Roman dominating function is a (double) Roman dominating function f for which the set of vertices assigned 0 under f is independent. The outer independent (double) Roman domination number (\(\gamma _{oidR}(G)\)) \(\gamma _{oiR}(G)\) is the minimum weight taken over all outer independent (double) Roman dominating functions of G. A vertex cover number \(\beta (G)\) is the minimum size of any vertex cover sets of a graph G. In this work, we present some contributions to the study of outer independent double Roman domination in graphs. Characterizations of the families of all connected graphs with small outer independent double Roman domination numbers, and tight lower and upper bounds on this parameter are given. We also prove that the decision problem associated with \(\gamma _{oidR}(G)\) is NP-complete even when restricted to planar graphs with maximum degree at most four. We moreover prove that \(2\beta (T)+1\le \gamma _{oidR}(T)\le 3\beta (T)\) for any tree T, and show that each integer between the lower and upper bounds is realizable. Finally, we give an exact formula for this parameter concerning the corona graphs.
Doost Ali Mojdeh; Babak Samadi; Zehui Shao; Ismael G. Yero. On the Outer Independent Double Roman Domination Number. Bulletin of the Iranian Mathematical Society 2021, 1 -15.
AMA StyleDoost Ali Mojdeh, Babak Samadi, Zehui Shao, Ismael G. Yero. On the Outer Independent Double Roman Domination Number. Bulletin of the Iranian Mathematical Society. 2021; ():1-15.
Chicago/Turabian StyleDoost Ali Mojdeh; Babak Samadi; Zehui Shao; Ismael G. Yero. 2021. "On the Outer Independent Double Roman Domination Number." Bulletin of the Iranian Mathematical Society , no. : 1-15.
This research proposes a didactic strategy to enrich the assimilation processes of the change of variable theorem in solving the definite integral. The theoretical foundations that support it are based on the contributions of social constructivism, problem solving, and treatment of theorems. The practical validation of the strategy is carried out with students of the Higher Technical Level in Applied Mathematics at the Autonomous University of Guerrero.
Armando Carballo; Edgardo Locia Espinoza; José Sigarreta Almira; Ismael Yero. Approach to the Formulation of the Variable Change Theorem. Education Sciences 2021, 11, 357 .
AMA StyleArmando Carballo, Edgardo Locia Espinoza, José Sigarreta Almira, Ismael Yero. Approach to the Formulation of the Variable Change Theorem. Education Sciences. 2021; 11 (7):357.
Chicago/Turabian StyleArmando Carballo; Edgardo Locia Espinoza; José Sigarreta Almira; Ismael Yero. 2021. "Approach to the Formulation of the Variable Change Theorem." Education Sciences 11, no. 7: 357.
The general position number $$\mathrm{gp}(G)$$ gp ( G ) of a connected graph G is the cardinality of a largest set S of vertices such that no three distinct vertices from S lie on a common geodesic; such sets are refereed to as gp-sets of G. The general position number of cylinders $$P_r\,\square \,C_s$$ P r □ C s is deduced. It is proved that $$\mathrm{gp}(C_r\,\square \,C_s)\in \{6,7\}$$ gp ( C r □ C s ) ∈ { 6 , 7 } whenever $$r\ge s \ge 3$$ r ≥ s ≥ 3 , $$s\ne 4$$ s ≠ 4 , and $$r\ge 6$$ r ≥ 6 . A probabilistic lower bound on the general position number of Cartesian graph powers is achieved. Along the way a formula for the number of gp-sets in $$P_r\,\square \,P_s$$ P r □ P s , where $$r,s\ge 2$$ r , s ≥ 2 , is also determined.
Sandi Klavžar; Balázs Patkós; Gregor Rus; Ismael G. Yero. On General Position Sets in Cartesian Products. Results in Mathematics 2021, 76, 1 -21.
AMA StyleSandi Klavžar, Balázs Patkós, Gregor Rus, Ismael G. Yero. On General Position Sets in Cartesian Products. Results in Mathematics. 2021; 76 (3):1-21.
Chicago/Turabian StyleSandi Klavžar; Balázs Patkós; Gregor Rus; Ismael G. Yero. 2021. "On General Position Sets in Cartesian Products." Results in Mathematics 76, no. 3: 1-21.
For a given graph G, the metric and edge metric dimensions of G, dim(G) and edim(G), are the cardinalities of the smallest possible subsets of vertices in V(G) such that they uniquely identify the vertices and the edges of G, respectively, by means of distances. It is already known that metric and edge metric dimensions are not in general comparable. Infinite families of graphs with pendant vertices in which the edge metric dimension is smaller than the metric dimension are already known. In this article, we construct a 2-connected graph G such that dim(G)=a and edim(G)=b for every pair of integers a,b, where 4≤b
Martin Knor; Riste Škrekovski; Ismael G. Yero. A note on the metric and edge metric dimensions of 2-connected graphs. Discrete Applied Mathematics 2021, 1 .
AMA StyleMartin Knor, Riste Škrekovski, Ismael G. Yero. A note on the metric and edge metric dimensions of 2-connected graphs. Discrete Applied Mathematics. 2021; ():1.
Chicago/Turabian StyleMartin Knor; Riste Škrekovski; Ismael G. Yero. 2021. "A note on the metric and edge metric dimensions of 2-connected graphs." Discrete Applied Mathematics , no. : 1.
Given a connected graph G, the metric (resp. edge metric) dimension of G is the cardinality of the smallest ordered set of vertices that uniquely identifies every pair of distinct vertices (resp. edges) of G by means of distance vectors to such a set. In this work, we settle three open problems on (edge) metric dimension of graphs. Specifically, we show that for every r,t≥2 with r≠t, there is n0, such that for every n≥n0 there exists a graph G of order n with metric dimension r and edge metric dimension t, which among other consequences, shows the existence of infinitely many graph whose edge metric dimension is strictly smaller than its metric dimension. In addition, we also prove that it is not possible to bound the edge metric dimension of a graph G by some constant factor of the metric dimension of G.
Martin Knor; Snježana Majstorović; Aoden Teo Masa Toshi; Riste Škrekovski; Ismael G. Yero. Graphs with the edge metric dimension smaller than the metric dimension. Applied Mathematics and Computation 2021, 401, 126076 .
AMA StyleMartin Knor, Snježana Majstorović, Aoden Teo Masa Toshi, Riste Škrekovski, Ismael G. Yero. Graphs with the edge metric dimension smaller than the metric dimension. Applied Mathematics and Computation. 2021; 401 ():126076.
Chicago/Turabian StyleMartin Knor; Snježana Majstorović; Aoden Teo Masa Toshi; Riste Škrekovski; Ismael G. Yero. 2021. "Graphs with the edge metric dimension smaller than the metric dimension." Applied Mathematics and Computation 401, no. : 126076.
Let G be a graph and let S⊆V(G). The set S is a double outer-independent dominating set of G if |N[v]∩S|≥2 for all v∈V(G), and V(G)∖S is independent. Similarly, S is a 2-outer-independent dominating set, if every vertex from V(G)∖S has at least two neighbors in S and V(G)∖S is independent. Finally, S is a total outer-independent dominating set if every vertex from V(G) has a neighbor in S and the complement of S is an independent set. The double, total or 2-outer-independent domination number of G is the smallest possible cardinality of any double, total or 2-outer-independent dominating set of G, respectively. In this paper, the 2-outer-independent, the total outer-independent and the double outer-independent domination numbers of graphs are investigated. We prove some Nordhaus–Gaddum type inequalities, derive their computational complexities and present several bounds for them.
Doost Ali Mojdeh; Iztok Peterin; Babak Samadi; Ismael G. Yero. On three outer-independent domination related parameters in graphs. Discrete Applied Mathematics 2021, 294, 115 -124.
AMA StyleDoost Ali Mojdeh, Iztok Peterin, Babak Samadi, Ismael G. Yero. On three outer-independent domination related parameters in graphs. Discrete Applied Mathematics. 2021; 294 ():115-124.
Chicago/Turabian StyleDoost Ali Mojdeh; Iztok Peterin; Babak Samadi; Ismael G. Yero. 2021. "On three outer-independent domination related parameters in graphs." Discrete Applied Mathematics 294, no. : 115-124.
The total and strong version of the Roman domination number (for graphs) is introduced in this research, and the study of its mathematical properties is therefore initiated. We establish upper bounds for such a parameter, and relate it with several parameters concerning vertex domination in graphs. In addition, among other results, we show that for any tree T of order \(n(T)\ge 3\), maximum degree \(\Delta (T)\) and s(T) support vertices, the total strong Roman domination number is bounded below by \(\left\lceil \frac{n(T)+s(T)}{\Delta (T)}\right\rceil +1\).
S. Nazari-Moghaddam; M. Soroudi; S. M. Sheikholeslami; I. G. Yero. On the total and strong version for Roman dominating functions in graphs. Aequationes mathematicae 2021, 1 -22.
AMA StyleS. Nazari-Moghaddam, M. Soroudi, S. M. Sheikholeslami, I. G. Yero. On the total and strong version for Roman dominating functions in graphs. Aequationes mathematicae. 2021; ():1-22.
Chicago/Turabian StyleS. Nazari-Moghaddam; M. Soroudi; S. M. Sheikholeslami; I. G. Yero. 2021. "On the total and strong version for Roman dominating functions in graphs." Aequationes mathematicae , no. : 1-22.
A set of vertices W of a graph G is a resolving set if every vertex of G is uniquely determined by its vector of distances to W. In this paper, the Maker–Breaker resolving game is introduced. The game is played on a graph G by Resolver and Spoiler who alternately select a vertex of G not yet chosen. Resolver wins if at some point the vertices chosen by him form a resolving set of G, whereas Spoiler wins if the Resolver cannot form a resolving set of G. The outcome of the game is denoted by o(G), and \(R_{\mathrm{MB}}(G)\) (resp. \(S_{\mathrm{MB}}(G)\)) denotes the minimum number of moves of Resolver (resp. Spoiler) to win when Resolver has the first move. The corresponding invariants for the game when Spoiler has the first move are denoted by \(R'_{\mathrm{MB}}(G)\) and \(S'_\mathrm{MB}(G)\). Invariants \(R_{\mathrm{MB}}(G)\), \(R'_{\mathrm{MB}}(G)\), \(S_\mathrm{MB}(G)\), and \(S'_{\mathrm{MB}}(G)\) are compared among themselves and with the metric dimension \(\mathrm{dim}(G)\). A large class of graphs G is constructed for which \(R_{\mathrm{MB}}(G) > \mathrm{dim}(G)\) holds. The effect of twin equivalence classes and pairing resolving sets on the Maker–Breaker resolving game is described. As an application, o(G), as well as \(R_{\mathrm{MB}}(G)\) and \(R'_{\mathrm{MB}}(G)\) (or \(S_{\mathrm{MB}}(G)\) and \(S'_{\mathrm{MB}}(G)\)), is determined for several graph classes, including trees, complete multi-partite graphs, grid graphs, and torus grid graphs.
Cong X. Kang; Sandi Klavžar; Ismael G. Yero; Eunjeong Yi. Maker–Breaker Resolving Game. Bulletin of the Malaysian Mathematical Sciences Society 2020, 44, 2081 -2099.
AMA StyleCong X. Kang, Sandi Klavžar, Ismael G. Yero, Eunjeong Yi. Maker–Breaker Resolving Game. Bulletin of the Malaysian Mathematical Sciences Society. 2020; 44 (4):2081-2099.
Chicago/Turabian StyleCong X. Kang; Sandi Klavžar; Ismael G. Yero; Eunjeong Yi. 2020. "Maker–Breaker Resolving Game." Bulletin of the Malaysian Mathematical Sciences Society 44, no. 4: 2081-2099.
Given a graph G without isolated vertices, a total Roman dominating function for G is a function f:V(G)→{0,1,2} such that every vertex u with f(u)=0 is adjacent to a vertex v with f(v)=2, and the set of vertices with positive labels induces a graph of minimum degree at least one. The total Roman domination number γtR(G) of G is the smallest possible value of ∑v∈V(G)f(v) among all total Roman dominating functions f. The total Roman domination number of the direct product G×H of the graphs G and H is studied in this work. Specifically, several relationships, in the shape of upper and lower bounds, between γtR(G×H) and some classical domination parameters for the factors are given. Characterizations of the direct product graphs G×H achieving small values (≤7) for γtR(G×H) are presented, and exact values for γtR(G×H) are deduced, while considering various specific direct product classes.
Abel Cabrera Martínez; Dorota Kuziak; Iztok Peterin; Ismael G. Yero. Dominating the Direct Product of Two Graphs through Total Roman Strategies. Mathematics 2020, 8, 1438 .
AMA StyleAbel Cabrera Martínez, Dorota Kuziak, Iztok Peterin, Ismael G. Yero. Dominating the Direct Product of Two Graphs through Total Roman Strategies. Mathematics. 2020; 8 (9):1438.
Chicago/Turabian StyleAbel Cabrera Martínez; Dorota Kuziak; Iztok Peterin; Ismael G. Yero. 2020. "Dominating the Direct Product of Two Graphs through Total Roman Strategies." Mathematics 8, no. 9: 1438.
In this paper we define the global defensive k-alliance (number) in a digraph D, and give several bounds on this parameter with characterizations of all digraphs attaining the bounds. In particular, for the case k = −1, we give a lower (an upper) bound on this parameter for directed trees (rooted trees). Moreover, the characterization of all directed trees (rooted trees) for which the equality holds is given. Finally, we show that the problem of finding the global defensive k-alliance number of a digraph is NP-hard for any suitable non-negative value of k, and in contrast with it, we also show that finding a minimum global defensive (−1)-alliance for any rooted tree is polynomial-time solvable.
Doost Ali Mojdeh; Babak Samadi; Ismael Gonzalez Yero. Global defensive k-alliances in directed graphs: combinatorial and computational issues. RAIRO - Operations Research 2020, 54, 1027 -1040.
AMA StyleDoost Ali Mojdeh, Babak Samadi, Ismael Gonzalez Yero. Global defensive k-alliances in directed graphs: combinatorial and computational issues. RAIRO - Operations Research. 2020; 54 (4):1027-1040.
Chicago/Turabian StyleDoost Ali Mojdeh; Babak Samadi; Ismael Gonzalez Yero. 2020. "Global defensive k-alliances in directed graphs: combinatorial and computational issues." RAIRO - Operations Research 54, no. 4: 1027-1040.
Given a graph G, we consider γr(G), γ{R2}(G), γr2(G) and γR(G) as the weak Roman domination number, the Roman {2}-domination number, the 2-rainbow domination number and the Roman domination number of G, respectively. It is known that γr(G)≤γ{R2}(G)≤γr2(G)≤γR(G) holds for any graph G. In connection with this, constructive characterizations of the trees T that satisfy the equalities above that are related with the weak Roman domination number are given in this work. That is, the trees T for which γr(T)=γ{R2}(T), γr(T)=γr2(T) and γr(T)=γR(T) are described.
Abel Cabrera-Martínez; Ismael G. Yero. Constructive characterizations concerning weak Roman domination in trees. Discrete Applied Mathematics 2020, 284, 384 -390.
AMA StyleAbel Cabrera-Martínez, Ismael G. Yero. Constructive characterizations concerning weak Roman domination in trees. Discrete Applied Mathematics. 2020; 284 ():384-390.
Chicago/Turabian StyleAbel Cabrera-Martínez; Ismael G. Yero. 2020. "Constructive characterizations concerning weak Roman domination in trees." Discrete Applied Mathematics 284, no. : 384-390.
We consider in this work a new approach to study the simultaneous strong metric dimension of graphs families, while introducing the simultaneous version of the strong resolving graph. In concordance, we consider here connected graphs G whose vertex sets are represented as V ( G ) , and the following terminology. Two vertices u , v ∈ V ( G ) are strongly resolved by a vertex w ∈ V ( G ) , if there is a shortest w − v path containing u or a shortest w − u containing v. A set A of vertices of the graph G is said to be a strong metric generator for G if every two vertices of G are strongly resolved by some vertex of A. The smallest possible cardinality of any strong metric generator (SSMG) for the graph G is taken as the strong metric dimension of the graph G. Given a family F of graphs defined over a common vertex set V, a set S ⊂ V is an SSMG for F , if such set S is a strong metric generator for every graph G ∈ F . The simultaneous strong metric dimension of F is the minimum cardinality of any strong metric generator for F , and is denoted by Sd s ( F ) . The notion of simultaneous strong resolving graph of a graph family F is introduced in this work, and its usefulness in the study of Sd s ( F ) is described. That is, it is proved that computing Sd s ( F ) is equivalent to computing the vertex cover number of the simultaneous strong resolving graph of F . Several consequences (computational and combinatorial) of such relationship are then deduced. Among them, we remark for instance that we have proved the NP-hardness of computing the simultaneous strong metric dimension of families of paths, which is an improvement (with respect to the increasing difficulty of the problem) on the results known from the literature.
Ismael González González Yero. The Simultaneous Strong Resolving Graph and the Simultaneous Strong Metric Dimension of Graph Families. Mathematics 2020, 8, 125 .
AMA StyleIsmael González González Yero. The Simultaneous Strong Resolving Graph and the Simultaneous Strong Metric Dimension of Graph Families. Mathematics. 2020; 8 (1):125.
Chicago/Turabian StyleIsmael González González Yero. 2020. "The Simultaneous Strong Resolving Graph and the Simultaneous Strong Metric Dimension of Graph Families." Mathematics 8, no. 1: 125.
A set W of vertices of a connected graph G strongly resolves two different vertices x, y ∉ W if either d G (x, W) = d G (x, y) + d G (y, W) or d G (y, W) = d G (y, x) + d G (x, W), where d G (x, W) = min{d(x,w): w ∈ W} and d(x,w) represents the length of a shortest x − w path. An ordered vertex partition Π = {U 1, U 2,…,U k } of a graph G is a strong resolving partition for G, if every two different vertices of G belonging to the same set of the partition are strongly resolved by some other set of Π. The minimum cardinality of any strong resolving partition for G is the strong partition dimension of G. In this article, we obtain several bounds and closed formulae for the strong partition dimension of some families of graphs and give some realization results relating the strong partition dimension, the strong metric dimension and the order of graphs.
Dorota Kuziak; Ismael Gonzalez Yero. Further new results on strong resolving partitions for graphs. Open Mathematics 2020, 18, 237 -248.
AMA StyleDorota Kuziak, Ismael Gonzalez Yero. Further new results on strong resolving partitions for graphs. Open Mathematics. 2020; 18 (1):237-248.
Chicago/Turabian StyleDorota Kuziak; Ismael Gonzalez Yero. 2020. "Further new results on strong resolving partitions for graphs." Open Mathematics 18, no. 1: 237-248.
Given a graph G = (V, E), a function f: V → {0, 1, 2} is a total Roman {2}-dominating function if
Suitberto Cabrera García; Abel Cabrera Martínez; Frank A. Hernández Mira; Ismael G. Yero. Total Roman {2}-domination in graphs. Quaestiones Mathematicae 2019, 44, 411 -434.
AMA StyleSuitberto Cabrera García, Abel Cabrera Martínez, Frank A. Hernández Mira, Ismael G. Yero. Total Roman {2}-domination in graphs. Quaestiones Mathematicae. 2019; 44 (3):411-434.
Chicago/Turabian StyleSuitberto Cabrera García; Abel Cabrera Martínez; Frank A. Hernández Mira; Ismael G. Yero. 2019. "Total Roman {2}-domination in graphs." Quaestiones Mathematicae 44, no. 3: 411-434.
The general position number gp(G) of a connected graph G is the cardinality of a largest set S of vertices such that no three pairwise distinct vertices from S lie on a common geodesic. It is proved that gp(G) ≥ ω(GSR), where GSR is the strong resolving graph of G, and ω(GSR) is its clique number. That the bound is sharp is demonstrated with numerous constructions including for instance direct products of complete graphs and different families of strong products, of generalized lexicographic products, and of rooted product graphs. For the strong product it is proved that gp(G ⊠ H) ≥ gp(G)gp(H), and asked whether the equality holds for arbitrary connected graphs G and H. It is proved that the answer is in particular positive for strong products with a complete factor, for strong products of complete bipartite graphs, and for certain strong cylinders.
Sandi Klavžar; Ismael G. Yero. The general position problem and strong resolving graphs. Open Mathematics 2019, 17, 1126 -1135.
AMA StyleSandi Klavžar, Ismael G. Yero. The general position problem and strong resolving graphs. Open Mathematics. 2019; 17 (1):1126-1135.
Chicago/Turabian StyleSandi Klavžar; Ismael G. Yero. 2019. "The general position problem and strong resolving graphs." Open Mathematics 17, no. 1: 1126-1135.
A quasi-total Roman dominating function on a graph \(G=(V, E)\) is a function \(f : V \rightarrow \{0,1,2\}\) satisfying the following: Every vertex u for which \(f(u) = 0\) is adjacent to at least one vertex v for which \(f(v) =2\), and If x is an isolated vertex in the subgraph induced by the set of vertices labeled with 1 and 2, then \(f(x)=1\). The weight of a quasi-total Roman dominating function is the value \(\omega (f)=f(V)=\sum _{u\in V} f(u)\). The minimum weight of a quasi-total Roman dominating function on a graph G is called the quasi-total Roman domination number of G. We introduce the quasi-total Roman domination number of graphs in this article, and begin the study of its combinatorial and computational properties.
Suitberto Cabrera García; Abel Cabrera; Ismael G. Yero. Quasi-total Roman Domination in Graphs. Results in Mathematics 2019, 74, 173 .
AMA StyleSuitberto Cabrera García, Abel Cabrera, Ismael G. Yero. Quasi-total Roman Domination in Graphs. Results in Mathematics. 2019; 74 (4):173.
Chicago/Turabian StyleSuitberto Cabrera García; Abel Cabrera; Ismael G. Yero. 2019. "Quasi-total Roman Domination in Graphs." Results in Mathematics 74, no. 4: 173.
The characterisation of vertices in a network, in relation to other peers, has been used as a primitive in many computational procedures, such as node localisation and (de-)anonymisation. This article focuses on a characterisation type known as the multiset metric representation. Formally, given a graph G and a subset of vertices S={w1,…,wt}⊆V(G), the multiset representationof a vertex u ∈ V(G) with respect to S is the multiset m(u|S)={|dG(u,w1),…,dG(u,wt)|}. A subset of vertices S such that m(u|S)=m(v|S)⇔u=v for every u, v ∈ V(G)∖S is said to be a multiset resolving set, and the cardinality of the smallest such set is the outer multiset dimension. We study the general behaviour of the outer multiset dimension, and determine its exact value for several graph families. We also show that computing the outer multiset dimension of arbitrary graphs is NP-hard, and provide methods for efficiently handling particular cases.
Reynaldo Gil-Pons; Yunior Ramírez-Cruz; Rolando Trujillo-Rasua; Ismael G. Yero. Distance-based vertex identification in graphs: The outer multiset dimension. Applied Mathematics and Computation 2019, 363, 124612 .
AMA StyleReynaldo Gil-Pons, Yunior Ramírez-Cruz, Rolando Trujillo-Rasua, Ismael G. Yero. Distance-based vertex identification in graphs: The outer multiset dimension. Applied Mathematics and Computation. 2019; 363 ():124612.
Chicago/Turabian StyleReynaldo Gil-Pons; Yunior Ramírez-Cruz; Rolando Trujillo-Rasua; Ismael G. Yero. 2019. "Distance-based vertex identification in graphs: The outer multiset dimension." Applied Mathematics and Computation 363, no. : 124612.
Let \(G=(V, E)\) be a connected graph. Given a vertex \(v\in V\) and an edge \(e=uw\in E\), the distance between v and e is defined as \(d_G(e,v)=\min \{d_G(u,v),d_G(w,v)\}\). A nonempty set \(S\subset V\) is an edge metric generator for G if for any two edges \(e_1,e_2\in E\) there is a vertex \(w\in S\) such that \(d_G(w,e_1)\ne d_G(w,e_2)\). The minimum cardinality of any edge metric generator for a graph G is the edge metric dimension of G. The edge metric dimension of the join, lexicographic, and corona product of graphs is studied in this article.
Iztok Peterin; Ismael G. Yero. Edge Metric Dimension of Some Graph Operations. Bulletin of the Malaysian Mathematical Sciences Society 2019, 43, 2465 -2477.
AMA StyleIztok Peterin, Ismael G. Yero. Edge Metric Dimension of Some Graph Operations. Bulletin of the Malaysian Mathematical Sciences Society. 2019; 43 (3):2465-2477.
Chicago/Turabian StyleIztok Peterin; Ismael G. Yero. 2019. "Edge Metric Dimension of Some Graph Operations." Bulletin of the Malaysian Mathematical Sciences Society 43, no. 3: 2465-2477.