Mathematics

Research

Jump to: Review

25 pages, 1622 KiB

Open AccessArticle

Modified and Improved Algorithm for Finding a Median Path with a Specific Length (ℓ) for a Tree Network

by Abdallah Aboutahoun, Salem Mahdi, Mahmoud El-Alem and Mohamed ALrashidi

Mathematics 2023, 11(16), 3585; https://doi.org/10.3390/math11163585 - 18 Aug 2023

Viewed by 1099

Abstract

The median path problem (min-sum criterion) is a common problem in graph theory and tree networks. This problem is open to study because its applications are growing and extending in different fields, such as providing insight for decision-makers when selecting the optimal location [...] Read more.

The median path problem (min-sum criterion) is a common problem in graph theory and tree networks. This problem is open to study because its applications are growing and extending in different fields, such as providing insight for decision-makers when selecting the optimal location for non-emergency services, including railroad lines, highways, pipelines, and transit routes. Also, the min-sum criterion can deal with several networks in different applications. The location problem has traditionally been concerned with the optimal location of a single-point facility at either a vertex or along an edge in a network. Recently, numerous investigators have investigated this classic problem and have studied the location of many facilities, such as paths, trees, and cycles. The concept of the median, which measures the centrality of a vertex in a graph, is extended to the paths in a graph. In this paper, we consider the problem of locating path-shaped facilities on a tree network. A new modified and improved algorithm for finding a median single path facility of a specified length in a tree network is proposed. The median criterion for optimality considers the sum of the distances from all vertices of the tree to the path facility. This problem under the median criterion is called the ℓ-core problem. The distance between any two vertices in the tree is equal to the length of the unique path connecting them. This location problem usually has applications in distributed database systems, pipelines, the design of public transportation routes, and communication networks. Full article

(This article belongs to the Special Issue Advances in Discrete Applied Mathematics and Graph Theory, 2nd Edition)

► Show Figures

Figure 1

16 pages, 376 KiB

Open AccessArticle

On 2-Rainbow Domination of Generalized Petersen Graphs P(ck,k)

by Simon Brezovnik, Darja Rupnik Poklukar and Janez Žerovnik

Mathematics 2023, 11(10), 2271; https://doi.org/10.3390/math11102271 - 12 May 2023

Cited by 3 | Viewed by 2154

Abstract

We obtain new results on the 2-rainbow domination number of generalized Petersen graphs

P (c k, k)

. Exact values are established for all infinite families where the general lower bound

\frac{4}{5} c k

is attained. In all other [...] Read more.

We obtain new results on the 2-rainbow domination number of generalized Petersen graphs

P (c k, k)

. Exact values are established for all infinite families where the general lower bound

\frac{4}{5} c k

is attained. In all other cases lower and upper bounds with small gaps are given. Full article

(This article belongs to the Special Issue Advances in Discrete Applied Mathematics and Graph Theory, 2nd Edition)

► Show Figures

Figure 1

14 pages, 455 KiB

Open AccessArticle

Degree-Based Entropy of Some Classes of Networks

by S. Nagarajan, Muhammad Imran, P. Mahesh Kumar, K. Pattabiraman and Muhammad Usman Ghani

Mathematics 2023, 11(4), 960; https://doi.org/10.3390/math11040960 - 13 Feb 2023

Cited by 6 | Viewed by 1377

Abstract

A topological index is a number that is connected to a chemical composition in order to correlate a substance’s chemical makeup with different physical characteristics, chemical reactivity, or biological activity. It is common to model drugs and other chemical substances as different forms, [...] Read more.

A topological index is a number that is connected to a chemical composition in order to correlate a substance’s chemical makeup with different physical characteristics, chemical reactivity, or biological activity. It is common to model drugs and other chemical substances as different forms, trees, and graphs. Certain physico-chemical features of chemical substances correlate better with degree-based topological invariants. Predictions concerning the dynamics of the continuing pandemic may be made with the use of the graphic theoretical approaches given here. In Networks, the degree entropy of the epidemic and related trees was computed. It highlights the essay’s originality while also implying that this piece has improved upon prior literature-based realizations. In this paper, we study an important degree-based invariant known as the inverse sum indeg invariant for a variety of graphs of biological interest networks, including the corona product of some interesting classes of graphs and the pandemic tree network, curtain tree network, and Cayley tree network. We also examine the inverse sum indeg invariant features for the molecular graphs that represent the molecules in the bicyclic chemical graphs. Full article

(This article belongs to the Special Issue Advances in Discrete Applied Mathematics and Graph Theory, 2nd Edition)

► Show Figures

Figure 1

15 pages, 316 KiB

Open AccessArticle

A New Alternative to Szeged, Mostar, and PI Polynomials—The SMP Polynomials

by Martin Knor and Niko Tratnik

Mathematics 2023, 11(4), 956; https://doi.org/10.3390/math11040956 - 13 Feb 2023

Cited by 4 | Viewed by 1586

Abstract

Szeged-like topological indices are well-studied distance-based molecular descriptors, which include, for example, the (edge-)Szeged index, the (edge-)Mostar index, and the (vertex-)PI index. For these indices, the corresponding polynomials were also defined, i.e., the (edge-)Szeged polynomial, the Mostar polynomial, the PI polynomial, etc. It [...] Read more.

Szeged-like topological indices are well-studied distance-based molecular descriptors, which include, for example, the (edge-)Szeged index, the (edge-)Mostar index, and the (vertex-)PI index. For these indices, the corresponding polynomials were also defined, i.e., the (edge-)Szeged polynomial, the Mostar polynomial, the PI polynomial, etc. It is well known that, by evaluating the first derivative of such a polynomial at

x = 1

, we obtain the related topological index. The aim of this paper is to introduce and investigate a new graph polynomial of two variables, which is called the SMP polynomial, such that all three vertex versions of the above-mentioned indices can be easily calculated using this polynomial. Moreover, we also define the edge-SMP polynomial, which is the edge version of the SMP polynomial. Various properties of the new polynomials are studied on some basic families of graphs, extremal problems are considered, and several open problems are stated. Then, we focus on the Cartesian product, and we show how the (edge-)SMP polynomial of the Cartesian product of n graphs can be calculated using the (weighted) SMP polynomials of its factors. Full article

(This article belongs to the Special Issue Advances in Discrete Applied Mathematics and Graph Theory, 2nd Edition)

► Show Figures

Figure 1

17 pages, 358 KiB

Open AccessArticle

Red–Blue k-Center Clustering with Distance Constraints

by Marzieh Eskandari, Bhavika B. Khare, Nirman Kumar and Bahram Sadeghi Bigham

Mathematics 2023, 11(3), 748; https://doi.org/10.3390/math11030748 - 2 Feb 2023

Viewed by 1435

Abstract

We consider a variant of the k-center clustering problem in

{I R}^{d}

, where the centers can be divided into two subsets—one, the red centers of size p, and the other, the blue centers of size q, such that [...] Read more.

We consider a variant of the k-center clustering problem in

{I R}^{d}

, where the centers can be divided into two subsets—one, the red centers of size p, and the other, the blue centers of size q, such that

p + q = k

, and each red center and each blue center must be a distance of at least some given

α \geq 0

apart. The aim is to minimize the covering radius. We provide a bi-criteria approximation algorithm for the problem and a polynomial time algorithm for the constrained problem where all centers must lie on a given line ℓ. Additionally, we present a polynomial time algorithm for the case where only the orientation of the line is fixed in the plane (

d = 2

), although the algorithm works even in

{I R}^{d}

by constraining the line to lie in a plane and with a fixed orientation. Full article

(This article belongs to the Special Issue Advances in Discrete Applied Mathematics and Graph Theory, 2nd Edition)

19 pages, 328 KiB

Open AccessArticle

A Combinatorial Approach to Study the Nordhaus–Guddum-Type Results for Steiner Degree Distance

by Hongfang Liu, Jinxia Liang, Yuhu Liu and Kinkar Chandra Das

Mathematics 2023, 11(3), 738; https://doi.org/10.3390/math11030738 - 1 Feb 2023

Viewed by 1501

Abstract

In 1994, Dobrynin and Kochetova introduced the concept of degree distance

DD (Γ)

of a connected graph

Γ

. Let

d_{Γ} (S)

be the Steiner k-distance of

S \subseteq V (Γ)

. The Steiner [...] Read more.

In 1994, Dobrynin and Kochetova introduced the concept of degree distance

DD (Γ)

of a connected graph

Γ

. Let

d_{Γ} (S)

be the Steiner k-distance of

S \subseteq V (Γ)

. The Steiner Wiener k-index or k-center Steiner Wiener index

{SW}_{k} (Γ)

of

Γ

is defined by

{SW}_{k} (Γ) = \sum_{\overset{S \subseteq V (Γ)}{| S | = k}} d_{Γ} (S) .

The k-center Steiner degree distance

{SDD}_{k} (Γ)

of a connected graph

Γ

is defined by

{SDD}_{k} (Γ) = \sum_{\overset{S \subseteq V (Γ)}{| S | = k}} [\sum_{v \in S} d e g_{Γ} (v)] d_{Γ} (S)

, where

d e g_{Γ} (v)

is the degree of the vertex v in

Γ

. In this paper, we consider the Nordhaus–Gaddum-type results for

{SW}_{k} (Γ)

and

{SDD}_{k} (Γ)

. Upper bounds on

{SW}_{k} (Γ) + {SW}_{k} (\bar{Γ})

and

{SW}_{k} (Γ) \cdot {SW}_{k} (\bar{Γ})

are obtained for a connected graph

Γ

and compared with previous bounds. We present sharp upper and lower bounds of

{SDD}_{k} (Γ) + {SDD}_{k} (\bar{Γ})

and

{SDD}_{k} (Γ) \cdot {SDD}_{k} (\bar{Γ})

for a connected graph

Γ

of order n with maximum degree

Δ

and minimum degree

δ

. Some graph classes attaining these bounds are also given. Full article

(This article belongs to the Special Issue Advances in Discrete Applied Mathematics and Graph Theory, 2nd Edition)

► Show Figures

Figure 1

14 pages, 444 KiB

Open AccessArticle

Smoothness of Graph Energy in Chemical Graphs

by Katja Zemljič and Petra Žigert Pleteršek

Mathematics 2023, 11(3), 552; https://doi.org/10.3390/math11030552 - 20 Jan 2023

Cited by 3 | Viewed by 2477

Abstract

The energy of a graph G as a chemical concept leading to HMO theory was introduced by Hückel in 1931 and developed into a mathematical interpretation many years later when Gutman in 1978 gave his famous definition of the graph energy as the [...] Read more.

The energy of a graph G as a chemical concept leading to HMO theory was introduced by Hückel in 1931 and developed into a mathematical interpretation many years later when Gutman in 1978 gave his famous definition of the graph energy as the sum of the absolute values of the eigenvalues of the adjacency matrix of G. One of the general requirements for any topological index is that similar molecules have close TI values, which is called smoothness. To explore this property, we consider two variants of structure sensitivity and abruptness as introduced by Furtula et al. in 2013 and 2019, for hydrocarbons with up to 20 carbon atoms. Finally, we investigate the relationships between graph energies of acyclic hydrocarbons compared to their cyclic versions. Full article

(This article belongs to the Special Issue Advances in Discrete Applied Mathematics and Graph Theory, 2nd Edition)

► Show Figures

Figure 1

24 pages, 1293 KiB

Open AccessArticle

Mathematical Properties of a Novel Graph-Theoretic Irregularity Index with Potential Applicability in QSPR Modeling

by Sakander Hayat, Amina Arif, Laiq Zada, Asad Khan and Yubin Zhong

Mathematics 2022, 10(22), 4377; https://doi.org/10.3390/math10224377 - 21 Nov 2022

Cited by 7 | Viewed by 1768

Abstract

Irregularity indices are graph-theoretic parameters designed to quantify the irregularity in a graph. In this paper, we study the practical applicability of irregularity indices in QSPR modeling of the physicochemical and quantum-theoretic properties of compounds. Our comparative testing shows that the recently introduced [...] Read more.

Irregularity indices are graph-theoretic parameters designed to quantify the irregularity in a graph. In this paper, we study the practical applicability of irregularity indices in QSPR modeling of the physicochemical and quantum-theoretic properties of compounds. Our comparative testing shows that the recently introduced

I R A

index has significant priority in applicability over other irregularity indices. In particular, we show that the correlation potential of the

I R A

index with certain physicochemical and quantum-theoretic properties such as the enthalpy of formation, boiling point, and

π

-electron energies is significant. Our QSPR modeling suggests that the regression models with the aforementioned characteristics such as strong curve fitting are, in fact, linear. Considering this the motivation, the

I R A

index was studied further, and we provide analytically explicit expressions of the

I R A

index for certain graph operations and compositions. We conclude the paper by reporting the conclusions, implications, limitations, and future scope of the current study. Full article

(This article belongs to the Special Issue Advances in Discrete Applied Mathematics and Graph Theory, 2nd Edition)

► Show Figures

Figure 1

9 pages, 252 KiB

Open AccessArticle

Spectra of Complemented Triangulation Graphs

by Jia Wei and Jing Wang

Mathematics 2022, 10(17), 3168; https://doi.org/10.3390/math10173168 - 2 Sep 2022

Viewed by 1137

Abstract

The complemented triangulation graph of a graph G, denoted by

CT (G)

, is defined as the graph obtained from G by adding, for each edge

u v

of G, a new vertex whose neighbours are the vertices of [...] Read more.

The complemented triangulation graph of a graph G, denoted by

CT (G)

, is defined as the graph obtained from G by adding, for each edge

u v

of G, a new vertex whose neighbours are the vertices of G other than u and v. In this paper, we first obtain the A-spectra, the L-spectra, and the Q-spectra of the complemented triangulation graphs of regular graphs. By using the results, we construct infinitely many pairs of A-cospectral graphs, L-cospectral graphs, and Q-cospectral graphs. We also obtain the number of spanning trees and the Kirchhoff index of the complemented triangulation graphs of regular graphs. Full article

(This article belongs to the Special Issue Advances in Discrete Applied Mathematics and Graph Theory, 2nd Edition)

► Show Figures

Figure 1

14 pages, 314 KiB

Open AccessArticle

Generalized Randić Estrada Indices of Graphs

by Eber Lenes, Exequiel Mallea-Zepeda, Luis Medina and Jonnathan Rodríguez

Mathematics 2022, 10(16), 2932; https://doi.org/10.3390/math10162932 - 14 Aug 2022

Viewed by 1531

Abstract

Let G be a simple undirected graph on n vertices. V. Nikiforov studied hybrids of

A_{G}

and

D_{G}

and defined the matrix

A_{α}^{G}

for every real

α \in [0, 1]

as [...] Read more.

Let G be a simple undirected graph on n vertices. V. Nikiforov studied hybrids of

A_{G}

and

D_{G}

and defined the matrix

A_{α}^{G}

for every real

α \in [0, 1]

as

A_{α}^{G} = α D_{G} + (1 - α) A_{G} .

In this paper, we define the generalized Randić matrix for graph G, and we introduce and establish bounds for the Estrada index of this new matrix. Furthermore, we find the smallest value of

α

for which the generalized Randić matrix is positive semidefinite. Finally, we present the solution to the problem proposed by V. Nikiforov. The problem consists of the following: for a given simple undirected graph G, determine the smallest value of

α

for which

A_{α}^{G}

is positive semidefinite. Full article

(This article belongs to the Special Issue Advances in Discrete Applied Mathematics and Graph Theory, 2nd Edition)

13 pages, 832 KiB

Open AccessArticle

Acyclic Chromatic Index of 1-Planar Graphs

by Wanshun Yang, Yiqiao Wang, Weifan Wang, Juan Liu, Stephen Finbow and Ping Wang

Mathematics 2022, 10(15), 2787; https://doi.org/10.3390/math10152787 - 5 Aug 2022

Viewed by 1632

Abstract

The acyclic chromatic index

χ_{a}^{'} (G)

of a graph G is the smallest k for which G is a proper edge colorable using k colors. A 1-planar graph is a graph that can be drawn in plane such that [...] Read more.

The acyclic chromatic index

χ_{a}^{'} (G)

of a graph G is the smallest k for which G is a proper edge colorable using k colors. A 1-planar graph is a graph that can be drawn in plane such that every edge is crossed by at most one other edge. In this paper, we prove that every 1-planar graph G has

χ_{a}^{'} (G) \leq Δ + 36

, where

Δ

denotes the maximum degree of G. This strengthens a result that if G is a triangle-free 1-planar graph, then

χ_{a}^{'} (G) \leq Δ + 16

. Full article

(This article belongs to the Special Issue Advances in Discrete Applied Mathematics and Graph Theory, 2nd Edition)

► Show Figures

Figure 1

Review

Jump to: Research

20 pages, 394 KiB

Open AccessReview

Double Roman Domination: A Survey

by Darja Rupnik Poklukar and Janez Žerovnik

Mathematics 2023, 11(2), 351; https://doi.org/10.3390/math11020351 - 9 Jan 2023

Cited by 6 | Viewed by 2965

Abstract

Since 2016, when the first paper of the double Roman domination appeared, the topic has received considerable attention in the literature. We survey known results on double Roman domination and some variations of the double Roman domination, and a list of open questions [...] Read more.

Since 2016, when the first paper of the double Roman domination appeared, the topic has received considerable attention in the literature. We survey known results on double Roman domination and some variations of the double Roman domination, and a list of open questions and conjectures is provided. Full article

(This article belongs to the Special Issue Advances in Discrete Applied Mathematics and Graph Theory, 2nd Edition)

Journal Menu

Journal Browser

Advances in Discrete Applied Mathematics and Graph Theory, 2nd Edition

Share This Special Issue

Special Issue Editors

Special Issue Information

Keywords

Benefits of Publishing in a Special Issue

Related Special Issue

Published Papers (12 papers)

Research

Review

Further Information

Guidelines

MDPI Initiatives

Follow MDPI