Mathematics

Research

20 pages, 1087 KiB

Open AccessFeature PaperArticle

The Minimal Molecular Tree for the Exponential Randić Index

by Jayanta Bera and Kinkar Chandra Das

Mathematics 2024, 12(22), 3601; https://doi.org/10.3390/math12223601 - 18 Nov 2024

Viewed by 258

Topological indices are numerical parameters that provide a way to quantify the structural features of molecules using their graph representations. In chemical graph theory, these indices have been effectively employed to predict various physico-chemical properties of molecules. Among these, the Randić index stands [...] Read more.

Topological indices are numerical parameters that provide a way to quantify the structural features of molecules using their graph representations. In chemical graph theory, these indices have been effectively employed to predict various physico-chemical properties of molecules. Among these, the Randić index stands out as a classical and widely used molecular descriptor in chemistry and pharmacology. The Randić index

R (G)

for a given graph G is defined as

R (G) = \sum_{v_{i} v_{j} \in E (G)} \frac{1}{\sqrt{d (v_{i}) d (v_{j})}}

, where

d (v_{i})

represents the degree of vertex

v_{i}

and

E (G)

is the set of edges in the graph G. Given the Randić index’s strong discrimination ability in describing molecular structures, a variant known as the exponential Randić index was recently introduced. The exponential Randić index

E R (G)

for a graph G is defined as

E R (G) = \sum_{v_{i} v_{j} \in E (G)} e^{\frac{1}{\sqrt{d (v_{i}) d (v_{j})}}}

. This paper further explores and fully characterizes the minimal molecular trees in relation to the exponential Randić index. Moreover, the chemical relevance of the exponential Randić index is also investigated. Full article

(This article belongs to the Special Issue Graph Theory and Applications, 2nd Edition)

► Show Figures

Figure 1

15 pages, 591 KiB

Open AccessArticle

Closeness Centrality of Asymmetric Trees and Triangular Numbers

by Nytha Ramanathan, Eduardo Ramirez, Dorothy Suzuki-Burke and Darren A. Narayan

Mathematics 2024, 12(19), 2994; https://doi.org/10.3390/math12192994 - 26 Sep 2024

Viewed by 480

Abstract

The combinatorial problem in this paper is motivated by a variant of the famous traveling salesman problem where the salesman must return to the starting point after each delivery. The total length of a delivery route is related to a metric known as [...] Read more.

The combinatorial problem in this paper is motivated by a variant of the famous traveling salesman problem where the salesman must return to the starting point after each delivery. The total length of a delivery route is related to a metric known as closeness centrality. The closeness centrality of a vertex v in a graph G was defined in 1950 by Bavelas to be

C C (v) = \frac{| V (G) | - 1}{S D (v)}

, where

S D (v)

is the sum of the distances from v to each of the other vertices (which is one-half of the total distance in the delivery route). We provide a real-world example involving the Metro Atlanta Rapid Transit Authority rail network and identify stations whose

S D

values are nearly identical, meaning they have a similar proximity to other stations in the network. We then consider theoretical aspects involving asymmetric trees. For integer values of k, we considered the asymmetric tree with paths of lengths

k, 2 k, \dots, n k

that are incident to a center vertex. We investigated trees with different values of k, and for

k = 1

and

k = 2

, we established necessary and sufficient conditions for the existence of two vertices with identical

S D

values, which has a surprising connection to the triangular numbers. Additionally, we investigated asymmetric trees with paths incident to two vertices and found a sufficient condition for vertices to have equal

S D

values. This leads to new combinatorial proofs of identities arising from Pascal’s triangle. Full article

(This article belongs to the Special Issue Graph Theory and Applications, 2nd Edition)

► Show Figures

Figure 1

16 pages, 784 KiB

Open AccessArticle

Out-of-Distribution Node Detection Based on Graph Heat Kernel Diffusion

by Fangfang Li, Yangshuai Wang, Xinyu Du, Xiaohua Li and Ge Yu

Mathematics 2024, 12(18), 2942; https://doi.org/10.3390/math12182942 - 21 Sep 2024

Viewed by 880

Abstract

Over the past few years, there has been a surge in research attention towards tasks involving graph data, largely due to the impressive performance demonstrated by graph neural networks (GNNs) in handling such information. Currently, out-of-distribution (OOD) detection in graphs is a hot [...] Read more.

Over the past few years, there has been a surge in research attention towards tasks involving graph data, largely due to the impressive performance demonstrated by graph neural networks (GNNs) in handling such information. Currently, out-of-distribution (OOD) detection in graphs is a hot research topic. The goal of graph OOD detection is to identify nodes or new graphs that differ from the training data distribution, primarily in terms of attributes and structures. OOD detection is crucial for enhancing the stability, security, and robustness of models. In various applications, such as biological networks and financial fraud, graph OOD detection can help models identify anomalies or unforeseen situations, thereby enabling appropriate responses. In node-level OOD detection, existing models typically only consider first-order neighbors. This paper introduces graph diffusion to the OOD detection task for the first time, proposing the HOOD model, a graph diffusion-based OOD node detection algorithm. Specifically, the original graph is processed through graph diffusion to obtain a new graph that can directly capture high-order neighbor information, overcoming the limitation that message passing must go through first-order neighbors. The new graph is then sparsified using a top-k approach. Based on entropy information, regularization is employed to ensure the uncertainty of OOD nodes, thereby giving these nodes higher scores and enabling the model to effectively detect OOD nodes while ensuring the accuracy of in-distribution node classification. Experimental results demonstrate that the HOOD model outperforms existing methods in both node classification and OOD detection tasks on multiple benchmarks, highlighting its robustness and effectiveness. Full article

(This article belongs to the Special Issue Graph Theory and Applications, 2nd Edition)

► Show Figures

Figure 1

15 pages, 447 KiB

Open AccessArticle

Moran’s I for Multivariate Spatial Data

by Hiroshi Yamada

Mathematics 2024, 12(17), 2746; https://doi.org/10.3390/math12172746 - 4 Sep 2024

Viewed by 831

Abstract

Moran’s I is a spatial autocorrelation measure of univariate spatial data. Therefore, even if p spatial data exist, we can only obtain p values for Moran’s I. In other words, Moran’s I cannot measure the degree of spatial autocorrelation of multivariate spatial [...] Read more.

Moran’s I is a spatial autocorrelation measure of univariate spatial data. Therefore, even if p spatial data exist, we can only obtain p values for Moran’s I. In other words, Moran’s I cannot measure the degree of spatial autocorrelation of multivariate spatial data as a single value. This paper addresses this issue. That is, we extend Moran’s I so that it can measure the degree of spatial autocorrelation of multivariate spatial data as a single value. In addition, since the local version of Moran’s I has the same problem, we extend it as well. Then, we establish their properties, which are fundamental for applied work. Numerical illustrations of the theoretical results obtained in the paper are also provided. Full article

(This article belongs to the Special Issue Graph Theory and Applications, 2nd Edition)

► Show Figures

Figure 1

13 pages, 472 KiB

Open AccessArticle

Solving Mazes: A New Approach Based on Spectral Graph Theory

by Marta Martín-Nieto, Damián Castaño, Sergio Horta Muñoz and David Ruiz

Mathematics 2024, 12(15), 2305; https://doi.org/10.3390/math12152305 - 23 Jul 2024

Cited by 1 | Viewed by 650

Abstract

The use of graph theory for solving labyrinths and mazes is well known, understanding the possible paths as the connections between the nodes that represent the corners or bifurcations. This work presents a new idea: minimizing the length of the optimal path formulated [...] Read more.

The use of graph theory for solving labyrinths and mazes is well known, understanding the possible paths as the connections between the nodes that represent the corners or bifurcations. This work presents a new idea: minimizing the length of the optimal path formulated as a topology optimization problem. The maze is mapped with finite elements, and then, through the eigenvalues of the Laplacian matrix of the graph, a constraint is imposed over the connectivity between the input and the output. Several 2D examples are provided to support this approach, allowing for unequivocally finding the shortest path in mazes with multiple connections between entrance and exit, resulting in an nonheuristic algorithm. Full article

(This article belongs to the Special Issue Graph Theory and Applications, 2nd Edition)

► Show Figures

Figure 1

11 pages, 311 KiB

Open AccessArticle

A Matrix Approach to Vertex-Degree-Based Topological Indices

by Roberto Cruz, Carlos Espinal and Juan Rada

Mathematics 2024, 12(13), 2043; https://doi.org/10.3390/math12132043 - 30 Jun 2024

Cited by 1 | Viewed by 796

Abstract

A VDB (vertex-degree-based) topological index over a set of digraphs

H

is a function

φ : H \to R

, defined for each

H \in H

as [...] Read more.

A VDB (vertex-degree-based) topological index over a set of digraphs

H

is a function

φ : H \to R

, defined for each

H \in H

as

φ (H) = \frac{1}{2} \sum_{u v \in E} φ_{d_{u}^{+} d_{v}^{-}},

where E is the arc set of H,

d_{u}^{+}

and

d_{v}^{-}

denote the out-degree and in-degree of vertices u and v respectively, and

φ_{i j} = f (i, j)

for an appropriate real symmetric bivariate function f. It is our goal in this article to introduce a new approach where we base the concept of VDB topological index on the space of real matrices instead of the space of symmetric real functions of two variables. We represent a digraph H by the

p \times p

matrix

α (H)

, where

{[α (H)]}_{i j}

is the number of arcs

u v

such that

d_{u}^{+} = i

and

d_{v}^{-} = j

, and p is the maximum value of the in-degrees and out-degrees of H. By fixing a

p \times p

matrix

φ

, a VDB topological index of H is defined as the trace of the matrix

φ^{T} α (H)

. We show that this definition coincides with the previous one when

φ

is a symmetric matrix. This approach allows considering nonsymmetric matrices, which extends the concept of a VDB topological index to nonsymmetric bivariate functions. Full article

(This article belongs to the Special Issue Graph Theory and Applications, 2nd Edition)

► Show Figures

Figure 1

10 pages, 318 KiB

Open AccessArticle

On the Strong Secure Domination Number of a Graph

by Turki Alsuraiheed, J. Annaal Mercy, L. Benedict Michael Raj and Thangaraj Asir

Mathematics 2024, 12(11), 1666; https://doi.org/10.3390/math12111666 - 27 May 2024

Viewed by 661

Abstract

In this paper, we characterize trees with a strong secure domination number less than or equal to 4 and compute this parameter for certain classes of graphs. Also, we investigate bounds for the strong secure domination number of vertex gluing of two graphs. [...] Read more.

In this paper, we characterize trees with a strong secure domination number less than or equal to 4 and compute this parameter for certain classes of graphs. Also, we investigate bounds for the strong secure domination number of vertex gluing of two graphs. Full article

(This article belongs to the Special Issue Graph Theory and Applications, 2nd Edition)

► Show Figures

Figure 1

13 pages, 287 KiB

Open AccessArticle

Metric Dimension of Circulant Graphs with 5 Consecutive Generators

by Martin Knor, Riste Škrekovski and Tomáš Vetrík

Mathematics 2024, 12(9), 1384; https://doi.org/10.3390/math12091384 - 1 May 2024

Cited by 1 | Viewed by 1436

Abstract

The problem of finding the metric dimension of circulant graphs with t generators

1, 2, \dots, t

(and their inverses) has been extensively studied. The problem is solved for

t = 2, 3, 4

, and some exact [...] Read more.

The problem of finding the metric dimension of circulant graphs with t generators

1, 2, \dots, t

(and their inverses) has been extensively studied. The problem is solved for

t = 2, 3, 4

, and some exact values and bounds are known also for

t = 5

. We solve all the open cases for

t = 5

. Full article

(This article belongs to the Special Issue Graph Theory and Applications, 2nd Edition)

► Show Figures

Figure 1

17 pages, 912 KiB

Open AccessArticle

Semi-Local Integration Measure for Directed Graphs

by Tajana Ban Kirigin and Sanda Bujačić Babić

Mathematics 2024, 12(7), 1087; https://doi.org/10.3390/math12071087 - 4 Apr 2024

Viewed by 950

Abstract

Directed and weighted graphs can be used for many real-world applications to model and analyse the quality and structure of communication within the system, the distribution and flow of information, and various resources, dependencies, resilience, etc. On social media platforms, for example, highly [...] Read more.

Directed and weighted graphs can be used for many real-world applications to model and analyse the quality and structure of communication within the system, the distribution and flow of information, and various resources, dependencies, resilience, etc. On social media platforms, for example, highly networked members, so-called influencers, disseminate information, opinions and trends to their followers, who in turn increase the popularity of the influencers through likes and comments. Both types of interaction have a major influence on discussions and activities in the social network. To identify the nodes with the highest integration and interconnectivity within the neighbourhood subnetwork, we introduce the Directed Semi-Local Integration (

D S L I

) centrality measure for directed and weighted graphs. This centrality measure evaluates the integration of nodes assessed by the presence of connection, the strength of links, the organisation and optimisation of inbound and outbound interconnectivity, and the redundancy in the local subnetwork, and provides a stronger differentiation of the importance of nodes than standard centrality measures. Thus,

D S L I

has the potential to be used for analysing the degree of integration for the uptake and dissemination of resources in complex networks in many different contexts. Full article

(This article belongs to the Special Issue Graph Theory and Applications, 2nd Edition)

► Show Figures

Figure 1

18 pages, 628 KiB

Open AccessArticle

An Effective Fuzzy Clustering of Crime Reports Embedded by a Universal Sentence Encoder Model

by Aparna Pramanik, Asit Kumar Das, Danilo Pelusi and Janmenjoy Nayak

Mathematics 2023, 11(3), 611; https://doi.org/10.3390/math11030611 - 26 Jan 2023

Cited by 4 | Viewed by 1640

Abstract

Crime reports clustering is crucial for identifying and preventing criminal activities that frequently happened in society. In the proposed work, named entities in a report are recognized to extract the crime-related phrases and subsequently, the phrases are preprocessed by applying stopword removal and [...] Read more.

Crime reports clustering is crucial for identifying and preventing criminal activities that frequently happened in society. In the proposed work, named entities in a report are recognized to extract the crime-related phrases and subsequently, the phrases are preprocessed by applying stopword removal and lemmatization operations. Next, the module of the universal encoder model, called the transformer, is applied to extract phrases of the report to get a sentence embedding for each associated sentence, aggregation of which finally provides the vector representation of that report. An innovative and efficient graph-based clustering algorithm consisting of splitting and merging operations has been proposed to get the cluster of crime reports. The proposed clustering algorithm generates overlapping clusters, which indicates the existence of reports of multiple crime types. The fuzzy theory has been used to provide a score to the report for expressing its membership into different clusters, and accordingly, the reports are labelled by multiple categories. The efficiency of the proposed method has been assessed by taking into account different datasets and comparing them with other state-of-the-art approaches with the help of various performance measure metrics. Full article

(This article belongs to the Special Issue Graph Theory and Applications, 2nd Edition)

► Show Figures

Figure 1

Journal Menu

Journal Browser

Graph Theory and Applications, 2nd Edition

Share This Special Issue

Special Issue Editor

Special Issue Information

Keywords

Benefits of Publishing in a Special Issue

Related Special Issue

Published Papers (10 papers)

Research

Further Information

Guidelines

MDPI Initiatives

Follow MDPI