Research

11 pages, 374 KiB

Open AccessArticle

A Review of and Some Results for Ollivier–Ricci Network Curvature

by Nazanin Azarhooshang, Prithviraj Sengupta and Bhaskar DasGupta

Mathematics 2020, 8(9), 1416; https://0-doi-org.brum.beds.ac.uk/10.3390/math8091416 - 24 Aug 2020

Cited by 2 | Viewed by 2094

Characterizing topological properties and anomalous behaviors of higher-dimensional topological spaces via notions of curvatures is by now quite common in mainstream physics and mathematics, and it is therefore natural to try to extend these notions from the non-network domains in a suitable way [...] Read more.

Characterizing topological properties and anomalous behaviors of higher-dimensional topological spaces via notions of curvatures is by now quite common in mainstream physics and mathematics, and it is therefore natural to try to extend these notions from the non-network domains in a suitable way to the network science domain. In this article we discuss one such extension, namely Ollivier’s discretization of Ricci curvature. We first motivate, define and illustrate the Ollivier–Ricci Curvature. In the next section we provide some “not-previously-published” bounds on the exact and approximate computation of the curvature measure. In the penultimate section we review a method based on the linear sketching technique for efficient approximate computation of the Ollivier–Ricci network curvature. Finally in the last section we provide concluding remarks with pointers for further reading. Full article

(This article belongs to the Special Issue Distances and Domination in Graphs)

► Show Figures

Figure 1

14 pages, 282 KiB

Open AccessArticle

The Strong Resolving Graph and the Strong Metric Dimension of Cactus Graphs

by Dorota Kuziak

Mathematics 2020, 8(8), 1266; https://0-doi-org.brum.beds.ac.uk/10.3390/math8081266 - 02 Aug 2020

Viewed by 2544

Abstract

A vertex w of a connected graph G strongly resolves two distinct vertices

u, v \in V (G)

, if there is a shortest

u, w

path containing v, or a shortest

v, w

path containing u [...] Read more.

A vertex w of a connected graph G strongly resolves two distinct vertices

u, v \in V (G)

, if there is a shortest

u, w

path containing v, or a shortest

v, w

path containing u. A set S of vertices of G is a strong resolving set for G if every two distinct vertices of G are strongly resolved by a vertex of S. The smallest cardinality of a strong resolving set for G is called the strong metric dimension of G. To study the strong metric dimension of graphs, a very important role is played by a structure of graphs called the strong resolving graph In this work, we obtain the strong metric dimension of some families of cactus graphs, and along the way, we give several structural properties of the strong resolving graphs of the studied families of cactus graphs. Full article

(This article belongs to the Special Issue Distances and Domination in Graphs)

► Show Figures

Figure 1

13 pages, 291 KiB

Open AccessArticle

On a Relation between the Perfect Roman Domination and Perfect Domination Numbers of a Tree

by Zehui Shao, Saeed Kosari, Mustapha Chellali, Seyed Mahmoud Sheikholeslami and Marzieh Soroudi

Mathematics 2020, 8(6), 966; https://0-doi-org.brum.beds.ac.uk/10.3390/math8060966 - 12 Jun 2020

Cited by 4 | Viewed by 1630

Abstract

A dominating set in a graph G is a set of vertices

S \subseteq V (G)

such that any vertex of

V - S

is adjacent to at least one vertex of

S .

A dominating set S of G is [...] Read more.

A dominating set in a graph G is a set of vertices

S \subseteq V (G)

such that any vertex of

V - S

is adjacent to at least one vertex of

S .

A dominating set S of G is said to be a perfect dominating set if each vertex in

V - S

is adjacent to exactly one vertex in S. The minimum cardinality of a perfect dominating set is the perfect domination number

γ^{p} (G) .

A function

f : V (G) \to {0, 1, 2}

is a perfect Roman dominating function (PRDF) on G if every vertex

u \in V

for which

f (u) = 0

is adjacent to exactly one vertex v for which

f (v) = 2

. The weight of a PRDF is the sum of its function values over all vertices, and the minimum weight of a PRDF of G is the perfect Roman domination number

γ_{R}^{p} (G) .

In this paper, we prove that for any nontrivial tree T,

γ_{R}^{p} (T) \geq γ^{p} (T) + 1

and we characterize all trees attaining this bound. Full article

(This article belongs to the Special Issue Distances and Domination in Graphs)

► Show Figures

Figure 1

14 pages, 603 KiB

Open AccessArticle

Secure Total Domination in Rooted Product Graphs

by Abel Cabrera Martínez, Alejandro Estrada-Moreno and Juan A. Rodríguez-Velázquez

Mathematics 2020, 8(4), 600; https://0-doi-org.brum.beds.ac.uk/10.3390/math8040600 - 15 Apr 2020

Cited by 3 | Viewed by 2003

Abstract

In this article, we obtain general bounds and closed formulas for the secure total domination number of rooted product graphs. The results are expressed in terms of parameters of the factor graphs involved in the rooted product. Full article

(This article belongs to the Special Issue Distances and Domination in Graphs)

► Show Figures

Figure 1

14 pages, 397 KiB

Open AccessArticle

Efficient Open Domination in Digraph Products

by Dragana Božović and Iztok Peterin

Mathematics 2020, 8(4), 496; https://0-doi-org.brum.beds.ac.uk/10.3390/math8040496 - 02 Apr 2020

Viewed by 1906

Abstract

A digraph D is an efficient open domination digraph if there exists a subset S of

V (D)

for which the open out-neighborhoods centered in the vertices of S form a partition of

V (D)

. In this work [...] Read more.

A digraph D is an efficient open domination digraph if there exists a subset S of

V (D)

for which the open out-neighborhoods centered in the vertices of S form a partition of

V (D)

. In this work we deal with the efficient open domination digraphs among four standard products of digraphs. We present a method for constructing the efficient open domination Cartesian product of digraphs with one fixed factor. In particular, we characterize those for which the first factor has an underlying graph that is a path, a cycle or a star. We also characterize the efficient open domination strong product of digraphs that have factors whose underlying graphs are uni-cyclic graphs. The full characterizations of the efficient open domination direct and lexicographic product of digraphs are also given. Full article

(This article belongs to the Special Issue Distances and Domination in Graphs)

► Show Figures

Figure 1

8 pages, 255 KiB

Open AccessArticle

Further Results on the Total Roman Domination in Graphs

by Abel Cabrera Martínez, Suitberto Cabrera García and Andrés Carrión García

Mathematics 2020, 8(3), 349; https://0-doi-org.brum.beds.ac.uk/10.3390/math8030349 - 05 Mar 2020

Cited by 13 | Viewed by 2476

Abstract

Let G be a graph without isolated vertices. A function

f : V (G) \to {0, 1, 2}

is a total Roman dominating function on G if every vertex

v \in V (G)

for which [...] Read more.

Let G be a graph without isolated vertices. A function

f : V (G) \to {0, 1, 2}

is a total Roman dominating function on G if every vertex

v \in V (G)

for which

f (v) = 0

is adjacent to at least one vertex

u \in V (G)

such that

f (u) = 2

, and if the subgraph induced by the set

{v \in V (G) : f (v) \geq 1}

has no isolated vertices. The total Roman domination number of G, denoted

γ_{t R} (G)

, is the minimum weight

ω (f) = \sum_{v \in V (G)} f (v)

among all total Roman dominating functions f on G. In this article we obtain new tight lower and upper bounds for

γ_{t R} (G)

which improve the well-known bounds

2 γ (G) \leq γ_{t R} (G) \leq 3 γ (G)

, where

γ (G)

represents the classical domination number. In addition, we characterize the graphs that achieve equality in the previous lower bound and we give necessary conditions for the graphs which satisfy the equality in the upper bound above. Full article

(This article belongs to the Special Issue Distances and Domination in Graphs)

► Show Figures

Figure 1

14 pages, 317 KiB

Open AccessArticle

On the Total Outer k-Independent Domination Number of Graphs

by Abel Cabrera-Martínez, Juan Carlos Hernández-Gómez, Ernesto Parra-Inza and José María Sigarreta Almira

Mathematics 2020, 8(2), 194; https://0-doi-org.brum.beds.ac.uk/10.3390/math8020194 - 05 Feb 2020

Cited by 5 | Viewed by 2505

Abstract

A set of vertices of a graph G is a total dominating set if every vertex of G is adjacent to at least one vertex in such a set. We say that a total dominating set D is a total outer k-independent [...] Read more.

A set of vertices of a graph G is a total dominating set if every vertex of G is adjacent to at least one vertex in such a set. We say that a total dominating set D is a total outer k-independent dominating set of G if the maximum degree of the subgraph induced by the vertices that are not in D is less or equal to

k - 1

. The minimum cardinality among all total outer k-independent dominating sets is the total outer k-independent domination number of G. In this article, we introduce this parameter and begin with the study of its combinatorial and computational properties. For instance, we give several closed relationships between this novel parameter and other ones related to domination and independence in graphs. In addition, we give several Nordhaus–Gaddum type results. Finally, we prove that computing the total outer k-independent domination number of a graph G is an NP-hard problem. Full article

(This article belongs to the Special Issue Distances and Domination in Graphs)

► Show Figures

Figure 1

11 pages, 286 KiB

Open AccessArticle

The Simultaneous Strong Resolving Graph and the Simultaneous Strong Metric Dimension of Graph Families

by Ismael González Yero

Mathematics 2020, 8(1), 125; https://0-doi-org.brum.beds.ac.uk/10.3390/math8010125 - 14 Jan 2020

Cited by 1 | Viewed by 1761

Abstract

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 [...] Read more.

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 \in V (G)

are strongly resolved by a vertex

w \in 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 \subset V

is an SSMG for

F

, if such set S is a strong metric generator for every graph

G \in 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. Full article

(This article belongs to the Special Issue Distances and Domination in Graphs)

13 pages, 854 KiB

Open AccessArticle

Removing Twins in Graphs to Break Symmetries

by Antonio González and María Luz Puertas

Mathematics 2019, 7(11), 1111; https://0-doi-org.brum.beds.ac.uk/10.3390/math7111111 - 15 Nov 2019

Cited by 6 | Viewed by 3655

Abstract

Determining vertex subsets are known tools to provide information about automorphism groups of graphs and, consequently about symmetries of graphs. In this paper, we provide both lower and upper bounds of the minimum size of such vertex subsets, called the determining number of [...] Read more.

Determining vertex subsets are known tools to provide information about automorphism groups of graphs and, consequently about symmetries of graphs. In this paper, we provide both lower and upper bounds of the minimum size of such vertex subsets, called the determining number of the graph. These bounds, which are performed for arbitrary graphs, allow us to compute the determining number in two different graph families such are cographs and unit interval graphs. Full article

(This article belongs to the Special Issue Distances and Domination in Graphs)

► Show Figures

Figure 1

17 pages, 503 KiB

Open AccessArticle

Independent Domination Stable Trees and Unicyclic Graphs

by Pu Wu, Huiqin Jiang, Sakineh Nazari-Moghaddam, Seyed Mahmoud Sheikholeslami, Zehui Shao and Lutz Volkmann

Mathematics 2019, 7(9), 820; https://0-doi-org.brum.beds.ac.uk/10.3390/math7090820 - 05 Sep 2019

Cited by 1 | Viewed by 2364

Abstract

A set

S \subseteq V (G)

in a graph G is a dominating set if S dominates all vertices in G, where we say a vertex dominates each vertex in its closed neighbourhood. A set is independent if it is [...] Read more.

A set

S \subseteq V (G)

in a graph G is a dominating set if S dominates all vertices in G, where we say a vertex dominates each vertex in its closed neighbourhood. A set is independent if it is pairwise non-adjacent. The minimum cardinality of an independent dominating set on a graph G is called the independent domination number

i (G)

. A graph G is ID-stable if the independent domination number of G is not changed when any vertex is removed. In this paper, we study basic properties of ID-stable graphs and we characterize all ID-stable trees and unicyclic graphs. In addition, we establish bounds on the order of ID-stable trees. Full article

(This article belongs to the Special Issue Distances and Domination in Graphs)

► Show Figures

Figure 1

Journal Menu

Journal Browser

Distances and Domination in Graphs

Share This Special Issue

Special Issue Editor

Special Issue Information

Keywords

Published Papers (10 papers)

Research

Further Information

Guidelines

MDPI Initiatives

Follow MDPI