Graphs, Metrics and Models

A special issue of Mathematics (ISSN 2227-7390). This special issue belongs to the section "Mathematics and Computer Science".

Deadline for manuscript submissions: closed (30 November 2021) | Viewed by 23436

Special Issue Editors

Department of Mathematics, Universidad de Cádiz, 11202 Algeciras, Cadiz, Spain
Interests: graph theory; discrete mathematics; combinatorics; metric graph theory; domination in graphs
Special Issues, Collections and Topics in MDPI journals
Department of Statistics and Research Operations, Universidad de Cádiz, 11202 Algeciras, Cadiz, Spain
Interests: graph theory; discrete mathematics; combinatorics; metric graph theory; domination in graphs
Special Issues, Collections and Topics in MDPI journals

Special Issue Information

Dear Colleagues,

This Special Issue is addressed at studying the metric properties of graph structures and their possible applications in other branches of science. Graphs can represent us, and we can represent them. Atoms and molecules can be modeled by graphs, and people can be considered as points of a graph modeling human relationships. Perhaps the biggest graph at this moment in time is the World Wide Web, and every day, almost every human on Earth interacts with it. This interaction has allowed us to improve other kinds of relationships between humans, e.g., (virtual) social networks, and this Special Issue is in part motivated by the urgent need to collect good articles containing theoretical and applied results concerning the use of metrics in graphs, while modeling and measuring the properties of such social networks.

Metrics in graph structures have been frequently used in the sense of device detections. Investigations in this topic have been centered on recognizing elements in a graph to facilitate the identification of possible locations of intruders (fault in a computer network, spoiled device) in a graph. Such investigations bring together a wide range of graph models, with remarkable instances in navigation of robots in networks, pattern recognition and image processing, and recognition of chemical compounds. Very recently, a breaking point while researching metrics in graphs has been established by introducing a new strategy, the non-identification scheme, which is closely related to a privacy measure for social networks. This new parameter is the first attempt to quantify the security offered by social graphs against active attacks to its privacy.

This Special Issue focuses its goals on both branches of research on metrics in graphs: identification and the non-identification schemes. The specific objectives consider, on one side, the search for other new applications of metrics in graphs to other fields in science, mainly in the area of computer sciences. Secondly, the Special Issue aims to gather new theoretical techniques that improve those already established in this topic. In addition, any other research dealing with models on graph theory involving its metric properties is welcome as well.

Prof. Dr. Ismael González Yero
Prof. Dr. Dorota Kuziak
Guest Editors

Manuscript Submission Information

Manuscripts should be submitted online at www.mdpi.com by registering and logging in to this website. Once you are registered, click here to go to the submission form. Manuscripts can be submitted until the deadline. All submissions that pass pre-check are peer-reviewed. Accepted papers will be published continuously in the journal (as soon as accepted) and will be listed together on the special issue website. Research articles, review articles as well as short communications are invited. For planned papers, a title and short abstract (about 100 words) can be sent to the Editorial Office for announcement on this website.

Submitted manuscripts should not have been published previously, nor be under consideration for publication elsewhere (except conference proceedings papers). All manuscripts are thoroughly refereed through a single-blind peer-review process. A guide for authors and other relevant information for submission of manuscripts is available on the Instructions for Authors page. Mathematics is an international peer-reviewed open access semimonthly journal published by MDPI.

Please visit the Instructions for Authors page before submitting a manuscript. The Article Processing Charge (APC) for publication in this open access journal is 2600 CHF (Swiss Francs). Submitted papers should be well formatted and use good English. Authors may use MDPI's English editing service prior to publication or during author revisions.

Keywords

  • Metric properties of graphs
  • Metrics in graphs versus privacy in social networks
  • Models on metrics in graphs
  • Metric dimension invariants
  • Applications of metrics’ properties of graphs

Published Papers (14 papers)

Order results
Result details
Select all
Export citation of selected articles as:

Research

10 pages, 1153 KiB  
Article
On Global Offensive Alliance in Zero-Divisor Graphs
by Raúl Juárez Morales, Gerardo Reyna Hernández, Omar Rosario Cayetano and Jesús Romero Valencia
Mathematics 2022, 10(3), 298; https://0-doi-org.brum.beds.ac.uk/10.3390/math10030298 - 19 Jan 2022
Cited by 2 | Viewed by 1092
Abstract
Let Γ(V,E) be a simple connected graph with more than one vertex, without loops or multiple edges. A nonempty subset SV is a global offensive alliance if every vertex vVS satisfies that [...] Read more.
Let Γ(V,E) be a simple connected graph with more than one vertex, without loops or multiple edges. A nonempty subset SV is a global offensive alliance if every vertex vVS satisfies that δS(v)δS¯(v)+1. The global offensive alliance numberγo(Γ) is defined as the minimum cardinality among all global offensive alliances. Let R be a finite commutative ring with identity. In this paper, we study the global offensive alliance number of the zero-divisor graph Γ(R). Full article
(This article belongs to the Special Issue Graphs, Metrics and Models)
Show Figures

Figure 1

24 pages, 1117 KiB  
Article
Graph-Based Siamese Network for Authorship Verification
by Daniel Embarcadero-Ruiz, Helena Gómez-Adorno, Alberto Embarcadero-Ruiz and Gerardo Sierra
Mathematics 2022, 10(2), 277; https://0-doi-org.brum.beds.ac.uk/10.3390/math10020277 - 17 Jan 2022
Cited by 5 | Viewed by 2082
Abstract
In this work, we propose a novel approach to solve the authorship identification task on a cross-topic and open-set scenario. Authorship verification is the task of determining whether or not two texts were written by the same author. We model the documents in [...] Read more.
In this work, we propose a novel approach to solve the authorship identification task on a cross-topic and open-set scenario. Authorship verification is the task of determining whether or not two texts were written by the same author. We model the documents in a graph representation and then a graph neural network extracts relevant features from these graph representations. We present three strategies to represent the texts as graphs based on the co-occurrence of the POS labels of words. We propose a Siamese Network architecture composed of graph convolutional networks along with pooling and classification layers. We present different variants of the architecture and discuss the performance of each one. To evaluate our approach we used a collection of fanfiction texts provided by the PAN@CLEF 2021 shared task in two settings: a “small” corpus and a “large” corpus. Our graph-based approach achieved average scores (AUC ROC, F1, Brier score, F0.5u, and C@1) between 90% and 92.83% when training on the “small” and “large” corpus, respectively. Our model obtain results comparable to those of the state of the art in this task and greater than traditional baselines. Full article
(This article belongs to the Special Issue Graphs, Metrics and Models)
Show Figures

Figure 1

14 pages, 312 KiB  
Article
The k-Metric Dimension of a Unicyclic Graph
by Alejandro Estrada-Moreno
Mathematics 2021, 9(21), 2789; https://0-doi-org.brum.beds.ac.uk/10.3390/math9212789 - 03 Nov 2021
Cited by 1 | Viewed by 1267
Abstract
Given a connected graph G=(V(G),E(G)), a set SV(G) is said to be a k-metric generator for G if any pair of different vertices in [...] Read more.
Given a connected graph G=(V(G),E(G)), a set SV(G) is said to be a k-metric generator for G if any pair of different vertices in V(G) is distinguished by at least k elements of S. A metric generator of minimum cardinality among all k-metric generators is called a k-metric basis and its cardinality is the k-metric dimension of G. We initially present a linear programming problem that describes the problem of finding the k-metric dimension and a k-metric basis of a graph G. Then we conducted a study on the k-metric dimension of a unicyclic graph. Full article
(This article belongs to the Special Issue Graphs, Metrics and Models)
Show Figures

Figure 1

17 pages, 382 KiB  
Article
A Restart Local Search for Solving Diversified Top-k Weight Clique Search Problem
by Jun Wu and Minghao Yin
Mathematics 2021, 9(21), 2674; https://0-doi-org.brum.beds.ac.uk/10.3390/math9212674 - 21 Oct 2021
Cited by 1 | Viewed by 1269
Abstract
Diversified top-k weight clique (DTKWC) search problem is an important generalization of the diversified top-k clique (DTKC) search problem with practical applications. The diversified top-k weight clique search problem aims to search k maximal cliques that can cover the maximum [...] Read more.
Diversified top-k weight clique (DTKWC) search problem is an important generalization of the diversified top-k clique (DTKC) search problem with practical applications. The diversified top-k weight clique search problem aims to search k maximal cliques that can cover the maximum weight in a vertex weighted graph. In this work, we propose a novel local search algorithm called TOPKWCLQ for the DTKWC search problem which mainly includes two strategies. First, a restart strategy is adopted, which repeated the construction and updating processes of the maximal weight clique set. Second, a scoring heuristic is designed by giving different priorities for maximal weight cliques in candidate set. Meanwhile, a constraint model of the DTKWC search problem is constructed such that the research concerns can be evaluated. Experimental results show that the proposed algorithm TOPKWCLQ outperforms than the comparison algorithm on large-scale real-world graphs. Full article
(This article belongs to the Special Issue Graphs, Metrics and Models)
Show Figures

Figure 1

10 pages, 276 KiB  
Article
On the Maximal Shortest Paths Cover Number
by Iztok Peterin and Gabriel Semanišin
Mathematics 2021, 9(14), 1592; https://0-doi-org.brum.beds.ac.uk/10.3390/math9141592 - 07 Jul 2021
Cited by 4 | Viewed by 1582
Abstract
A shortest path P of a graph G is maximal if P is not contained as a subpath in any other shortest path. A set SV(G) is a maximal shortest paths cover if every maximal shortest path of [...] Read more.
A shortest path P of a graph G is maximal if P is not contained as a subpath in any other shortest path. A set SV(G) is a maximal shortest paths cover if every maximal shortest path of G contains a vertex of S. The minimum cardinality of a maximal shortest paths cover is called the maximal shortest paths cover number and is denoted by ξ(G). We show that it is NP-hard to determine ξ(G). We establish a connection between ξ(G) and several other graph parameters. We present a linear time algorithm that computes exact value for ξ(T) of a tree T. Full article
(This article belongs to the Special Issue Graphs, Metrics and Models)
Show Figures

Figure 1

12 pages, 1421 KiB  
Article
Computing Open Locating-Dominating Number of Some Rotationally-Symmetric Graphs
by Hassan Raza
Mathematics 2021, 9(12), 1415; https://0-doi-org.brum.beds.ac.uk/10.3390/math9121415 - 18 Jun 2021
Cited by 2 | Viewed by 1535
Abstract
Location detection is studied for many scenarios, such as pointing out the flaws in multiprocessors, invaders in buildings and facilities, and utilizing wireless sensor networks for monitoring environmental processes. The system or structure can be illustrated as a graph in each of these [...] Read more.
Location detection is studied for many scenarios, such as pointing out the flaws in multiprocessors, invaders in buildings and facilities, and utilizing wireless sensor networks for monitoring environmental processes. The system or structure can be illustrated as a graph in each of these applications. Sensors strategically placed at a subset of vertices can determine and identify irregularities within the network. The open locating-dominating set S of a graph G=(V,E) is the set of vertices that dominates G, and for any i,j V(G) N(i)SN(j)S is satisfied. The set S is called the OLD-set of G. The cardinality of the set S is called open locating-dominating number and denoted by γold(G). In this paper, we computed exact values of the prism and prism-related graphs, and also the exact values of convex polytopes of Rn and Hn. The upper bound is determined for other classes of convex polytopes. The graphs considered here are well-known from the literature. Full article
(This article belongs to the Special Issue Graphs, Metrics and Models)
Show Figures

Figure 1

18 pages, 2447 KiB  
Article
Bounds of Fractional Metric Dimension and Applications with Grid-Related Networks
by Ali H. Alkhaldi, Muhammad Kamran Aslam, Muhammad Javaid and Abdulaziz Mohammed Alanazi
Mathematics 2021, 9(12), 1383; https://0-doi-org.brum.beds.ac.uk/10.3390/math9121383 - 15 Jun 2021
Cited by 8 | Viewed by 1634
Abstract
Metric dimension of networks is a distance based parameter that is used to rectify the distance related problems in robotics, navigation and chemical strata. The fractional metric dimension is the latest developed weighted version of metric dimension and a generalization of the concept [...] Read more.
Metric dimension of networks is a distance based parameter that is used to rectify the distance related problems in robotics, navigation and chemical strata. The fractional metric dimension is the latest developed weighted version of metric dimension and a generalization of the concept of local fractional metric dimension. Computing the fractional metric dimension for all the connected networks is an NP-hard problem. In this note, we find the sharp bounds of the fractional metric dimensions of all the connected networks under certain conditions. Moreover, we have calculated the fractional metric dimension of grid-like networks, called triangular and polaroid grids, with the aid of the aforementioned criteria. Moreover, we analyse the bounded and unboundedness of the fractional metric dimensions of the aforesaid networks with the help of 2D as well as 3D plots. Full article
(This article belongs to the Special Issue Graphs, Metrics and Models)
Show Figures

Figure 1

10 pages, 400 KiB  
Article
Isolation Number versus Domination Number of Trees
by Magdalena Lemańska, María José Souto-Salorio, Adriana Dapena and Francisco J. Vazquez-Araujo
Mathematics 2021, 9(12), 1325; https://0-doi-org.brum.beds.ac.uk/10.3390/math9121325 - 09 Jun 2021
Cited by 2 | Viewed by 2144
Abstract
If G=(VG,EG) is a graph of order n, we call SVG an isolating set if the graph induced by VGNG[S] contains no edges. The [...] Read more.
If G=(VG,EG) is a graph of order n, we call SVG an isolating set if the graph induced by VGNG[S] contains no edges. The minimum cardinality of an isolating set of G is called the isolation number of G, and it is denoted by ι(G). It is known that ι(G)n3 and the bound is sharp. A subset SVG is called dominating in G if NG[S]=VG. The minimum cardinality of a dominating set of G is the domination number, and it is denoted by γ(G). In this paper, we analyze a family of trees T where ι(T)=γ(T), and we prove that ι(T)=n3 implies ι(T)=γ(T). Moreover, we give different equivalent characterizations of such graphs and we propose simple algorithms to build these trees from the connections of stars. Full article
(This article belongs to the Special Issue Graphs, Metrics and Models)
Show Figures

Figure 1

10 pages, 252 KiB  
Article
On the Paired-Domination Subdivision Number of Trees
by Shouliu Wei, Guoliang Hao, Seyed Mahmoud Sheikholeslami, Rana Khoeilar and Hossein Karami
Mathematics 2021, 9(10), 1135; https://0-doi-org.brum.beds.ac.uk/10.3390/math9101135 - 17 May 2021
Cited by 3 | Viewed by 1224
Abstract
A paired-dominating set of a graph G without isolated vertices is a dominating set of vertices whose induced subgraph has perfect matching. The minimum cardinality of a paired-dominating set of G is called the paired-domination number γpr(G) of G [...] Read more.
A paired-dominating set of a graph G without isolated vertices is a dominating set of vertices whose induced subgraph has perfect matching. The minimum cardinality of a paired-dominating set of G is called the paired-domination number γpr(G) of G. The paired-domination subdivision number sdγpr(G) of G is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the paired-domination number. Here, we show that, for each tree TP5 of order n ≥ 3 and each edge eE(T), sdγpr(T) + sdγpr(T + e) ≤ n + 2. Full article
(This article belongs to the Special Issue Graphs, Metrics and Models)
Show Figures

Figure 1

9 pages, 267 KiB  
Article
On the Paired-Domination Subdivision Number of a Graph
by Guoliang Hao, Seyed Mahmoud Sheikholeslami, Mustapha Chellali, Rana Khoeilar and Hossein Karami
Mathematics 2021, 9(4), 439; https://0-doi-org.brum.beds.ac.uk/10.3390/math9040439 - 23 Feb 2021
Cited by 4 | Viewed by 1465
Abstract
In order to increase the paired-domination number of a graph G, the minimum number of edges that must be subdivided (where each edge in G can be subdivided no more than once) is called the paired-domination subdivision number [...] Read more.
In order to increase the paired-domination number of a graph G, the minimum number of edges that must be subdivided (where each edge in G can be subdivided no more than once) is called the paired-domination subdivision number sdγpr(G) of G. It is well known that sdγpr(G+e) can be smaller or larger than sdγpr(G) for some edge eE(G). In this note, we show that, if G is an isolated-free graph different from mK2, then, for every edge eE(G), sdγpr(G+e)sdγpr(G)+2Δ(G). Full article
(This article belongs to the Special Issue Graphs, Metrics and Models)
Show Figures

Figure 1

10 pages, 323 KiB  
Article
An Improved Nordhaus–Gaddum-Type Theorem for 2-Rainbow Independent Domination Number
by Enqiang Zhu
Mathematics 2021, 9(4), 402; https://0-doi-org.brum.beds.ac.uk/10.3390/math9040402 - 18 Feb 2021
Viewed by 1379
Abstract
For a graph G, its k-rainbow independent domination number, written as γrik(G), is defined as the cardinality of a minimum set consisting of k vertex-disjoint independent sets [...] Read more.
For a graph G, its k-rainbow independent domination number, written as γrik(G), is defined as the cardinality of a minimum set consisting of k vertex-disjoint independent sets V1,V2,,Vk such that every vertex in V0=V(G)\(i=1kVi) has a neighbor in Vi for all i{1,2,,k}. This domination invariant was proposed by Kraner Šumenjak, Rall and Tepeh (in Applied Mathematics and Computation 333(15), 2018: 353–361), which aims to compute the independent domination number of GKk (the generalized prism) via studying the problem of integer labeling on G. They proved a Nordhaus–Gaddum-type theorem: 5γri2(G)+γri2(G¯)n+3 for any n-order graph G with n3, in which G¯ denotes the complement of G. This work improves their result and shows that if GC5, then 5γri2(G)+γri2(G¯)n+2. Full article
(This article belongs to the Special Issue Graphs, Metrics and Models)
9 pages, 568 KiB  
Article
Total Domination on Some Graph Operators
by José M. Sigarreta
Mathematics 2021, 9(3), 241; https://0-doi-org.brum.beds.ac.uk/10.3390/math9030241 - 26 Jan 2021
Cited by 11 | Viewed by 2555
Abstract
Let G=(V,E) be a graph; a set DV is a total dominating set if every vertex vV has, at least, one neighbor in D. The total domination number [...] Read more.
Let G=(V,E) be a graph; a set DV is a total dominating set if every vertex vV has, at least, one neighbor in D. The total domination number γt(G) is the minimum cardinality among all total dominating sets. Given an arbitrary graph G, we consider some operators on this graph; S(G),R(G), and Q(G), and we give bounds or the exact value of the total domination number of these new graphs using some parameters in the original graph G. Full article
(This article belongs to the Special Issue Graphs, Metrics and Models)
Show Figures

Figure 1

9 pages, 277 KiB  
Article
A Note on the Paired-Domination Subdivision Number of Trees
by Xiaoli Qiang, Saeed Kosari, Zehui Shao, Seyed Mahmoud Sheikholeslami, Mustapha Chellali and Hossein Karami
Mathematics 2021, 9(2), 181; https://0-doi-org.brum.beds.ac.uk/10.3390/math9020181 - 18 Jan 2021
Cited by 7 | Viewed by 1466
Abstract
For a graph G with no isolated vertex, let γpr(G) and sdγpr(G) denote the paired-domination and paired-domination subdivision numbers, respectively. In this note, we show that if T is a tree of [...] Read more.
For a graph G with no isolated vertex, let γpr(G) and sdγpr(G) denote the paired-domination and paired-domination subdivision numbers, respectively. In this note, we show that if T is a tree of order n4 different from a healthy spider (subdivided star), then sdγpr(T)min{γpr(T)2+1,n2}, improving the (n1)-upper bound that was recently proven. Full article
(This article belongs to the Special Issue Graphs, Metrics and Models)
Show Figures

Figure 1

29 pages, 595 KiB  
Article
On BC-Subtrees in Multi-Fan and Multi-Wheel Graphs
by Yu Yang, Long Li, Wenhu Wang and Hua Wang
Mathematics 2021, 9(1), 36; https://0-doi-org.brum.beds.ac.uk/10.3390/math9010036 - 25 Dec 2020
Viewed by 1345
Abstract
The BC-subtree (a subtree in which any two leaves are at even distance apart) number index is the total number of non-empty BC-subtrees of a graph, and is defined as a counting-based topological index that incorporates the leaf distance constraint. In this paper, [...] Read more.
The BC-subtree (a subtree in which any two leaves are at even distance apart) number index is the total number of non-empty BC-subtrees of a graph, and is defined as a counting-based topological index that incorporates the leaf distance constraint. In this paper, we provide recursive formulas for computing the BC-subtree generating functions of multi-fan and multi-wheel graphs. As an application, we obtain the BC-subtree numbers of multi-fan graphs, r multi-fan graphs, multi-wheel (wheel) graphs, and discuss the change of the BC-subtree numbers between different multi-fan or multi-wheel graphs. We also consider the behavior of the BC-subtree number in these structures through the study of extremal problems and BC-subtree density. Our study offers a new perspective on understanding new structural properties of cyclic graphs. Full article
(This article belongs to the Special Issue Graphs, Metrics and Models)
Show Figures

Figure 1

Back to TopTop