Research

12 pages, 330 KiB

Open AccessArticle

by Yangyang Zhou, Dongyang Zhao, Mingyuan Ma and Jin Xu

Mathematics 2022, 10(6), 998; https://0-doi-org.brum.beds.ac.uk/10.3390/math10060998 - 21 Mar 2022

Cited by 3 | Viewed by 3462

A domination coloring of a graph G is a proper vertex coloring of G, such that each vertex of G dominates at least one color class (possibly its own class), and each color class is dominated by at least one vertex. The [...] Read more.

χ_{d d} (G)

. In this paper, we study the complexity of the k-domination coloring problem by proving its NP-completeness for arbitrary graphs. We give basic results and properties of

χ_{d d} (G)

, including the bounds and characterization results, and further research

χ_{d d} (G)

of some special classes of graphs, such as the split graphs, the generalized Petersen graphs, corona products, and edge corona products. Several results on graphs with

χ_{d d} (G) = χ (G)

are presented. Moreover, an application of domination colorings in social networks is proposed. Full article

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

► Show Figures

Figure 1

10 pages, 474 KiB

Open AccessArticle

Total Coloring of Dumbbell Maximal Planar Graphs

by Yangyang Zhou, Dongyang Zhao, Mingyuan Ma and Jin Xu

Mathematics 2022, 10(6), 912; https://0-doi-org.brum.beds.ac.uk/10.3390/math10060912 - 13 Mar 2022

Viewed by 1433

Abstract

The Total Coloring Conjecture (TCC) states that every simple graph G is totally

(Δ + 2)

-colorable, where

Δ

denotes the maximum degree of G. In this paper, we prove that TCC holds for dumbbell maximal planar graphs. Especially, we [...] Read more.

The Total Coloring Conjecture (TCC) states that every simple graph G is totally

(Δ + 2)

-colorable, where

Δ

denotes the maximum degree of G. In this paper, we prove that TCC holds for dumbbell maximal planar graphs. Especially, we divide the dumbbell maximal planar graphs into three categories according to the maximum degree:

J_{9}

, I-dumbbell maximal planar graphs and II-dumbbell maximal planar graphs. We give the necessary and sufficient condition for I-dumbbell maximal planar graphs, and prove that any I-dumbbell maximal planar graph is totally 8-colorable. Moreover, a linear time algorithm is proposed to compute a total

(Δ + 2)

-coloring for any I-dumbbell maximal planar graph. Full article

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

► Show Figures

Figure 1

9 pages, 279 KiB

Open AccessArticle

A Proof of a Conjecture on Bipartite Ramsey Numbers B(2,2,3)

by Yaser Rowshan, Mostafa Gholami and Stanford Shateyi

Mathematics 2022, 10(5), 701; https://0-doi-org.brum.beds.ac.uk/10.3390/math10050701 - 23 Feb 2022

Cited by 2 | Viewed by 981

Abstract

The bipartite Ramsey number

B (n_{1}, n_{2}, \dots, n_{t})

is the least positive integer b, such that any coloring of the edges of

K_{b, b}

with t colors will result in a [...] Read more.

The bipartite Ramsey number

B (n_{1}, n_{2}, \dots, n_{t})

is the least positive integer b, such that any coloring of the edges of

K_{b, b}

with t colors will result in a monochromatic copy of

K_{n_{i}, n_{i}}

in the i-th color, for some i,

1 \leq i \leq t

. The values

B (2, 5) = 17

B (2, 2, 2, 2) = 19

and

B (2, 2, 2) = 11

have been computed in several previously published papers. In this paper, we obtain the exact values of the bipartite Ramsey number

B (2, 2, 3)

. In particular, we prove the conjecture on

B (2, 2, 3)

which was proposed in 2015—in fact, we prove that

B (2, 2, 3) = 17

. Full article

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

12 pages, 300 KiB

Open AccessArticle

More on Sombor Index of Graphs

by Wenjie Ning, Yuheng Song and Kun Wang

Mathematics 2022, 10(3), 301; https://0-doi-org.brum.beds.ac.uk/10.3390/math10030301 - 19 Jan 2022

Cited by 11 | Viewed by 2529

Abstract

Recently, a novel degree-based molecular structure descriptor, called Sombor index was introduced. Let

G = (V (G), E (G))

be a graph. Then, the Sombor index of G is defined as [...] Read more.

Recently, a novel degree-based molecular structure descriptor, called Sombor index was introduced. Let

G = (V (G), E (G))

be a graph. Then, the Sombor index of G is defined as

S O (G) = \sum_{u v \in E (G)} \sqrt{d_{G}^{2} (u) + d_{G}^{2} (v)}

. In this paper, we give some lemmas that can be used to compare the Sombor indices between two graphs. With these lemmas, we determine the graph with maximum

S O

among all cacti with n vertices and k cut edges. Furthermore, the unique graph with maximum

S O

among all cacti with n vertices and p pendant vertices is characterized. In addition, we find the extremal graphs with respect to

S O

among all quasi-unicyclic graphs. Full article

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

► Show Figures

Figure 1

19 pages, 360 KiB

Open AccessArticle

On the Double Roman Domination in Generalized Petersen Graphs P(5k,k)

by Darja Rupnik Poklukar and Janez Žerovnik

Mathematics 2022, 10(1), 119; https://0-doi-org.brum.beds.ac.uk/10.3390/math10010119 - 01 Jan 2022

Cited by 3 | Viewed by 1679

Abstract

A double Roman dominating function on a graph

G = (V, E)

is a function

f : V \to {0, 1, 2, 3}

satisfying the condition that every vertex u for which [...] Read more.

A double Roman dominating function on a graph

G = (V, E)

is a function

f : V \to {0, 1, 2, 3}

satisfying the condition that every vertex u for which

f (u) = 0

is adjacent to at least one vertex assigned 3 or at least two vertices assigned 2, and every vertex u with

f (u) = 1

is adjacent to at least one vertex assigned 2 or 3. The weight of f equals

w (f) = \sum_{v \in V} f (v)

. The double Roman domination number

γ_{d R} (G)

of a graph G equals the minimum weight of a double Roman dominating function of G. We obtain closed expressions for the double Roman domination number of generalized Petersen graphs

P (5 k, k)

. It is proven that

γ_{d R} (P (5 k, k)) = 8 k

for

k \equiv 2, 3 mod 5

and

8 k \leq γ_{d R} (P (5 k, k)) \leq 8 k + 2

for

k \equiv 0, 1, 4 mod 5

. We also improve the upper bounds for generalized Petersen graphs

P (20 k, k)

. Full article

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

► Show Figures

Figure 1

11 pages, 280 KiB

Open AccessArticle

On the Quasi-Total Roman Domination Number of Graphs

by Abel Cabrera Martínez, Juan C. Hernández-Gómez and José M. Sigarreta

Mathematics 2021, 9(21), 2823; https://0-doi-org.brum.beds.ac.uk/10.3390/math9212823 - 06 Nov 2021

Cited by 4 | Viewed by 1484

Abstract

Domination theory is a well-established topic in graph theory, as well as one of the most active research areas. Interest in this area is partly explained by its diversity of applications to real-world problems, such as facility location problems, computer and social networks, monitoring communication, coding theory, and algorithm design, among others. In the last two decades, the functions defined on graphs have attracted the attention of several researchers. The Roman-dominating functions and their variants are one of the main attractions. This paper is a contribution to the Roman domination theory in graphs. In particular, we provide some interesting properties and relationships between one of its variants: the quasi-total Roman domination in graphs. Full article

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

► Show Figures

Figure 1

12 pages, 272 KiB

Open AccessArticle

Local Inclusive Distance Vertex Irregular Graphs

by Kiki Ariyanti Sugeng, Denny Riama Silaban, Martin Bača and Andrea Semaničová-Feňovčíková

Mathematics 2021, 9(14), 1673; https://0-doi-org.brum.beds.ac.uk/10.3390/math9141673 - 16 Jul 2021

Cited by 2 | Viewed by 1908

Abstract

Let

G = (V, E)

be a simple graph. A vertex labeling

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

is defined to be a local inclusive (respectively, non-inclusive) d-distance vertex [...] Read more.

Let

G = (V, E)

be a simple graph. A vertex labeling

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

is defined to be a local inclusive (respectively, non-inclusive) d-distance vertex irregular labeling of a graph G if for any two adjacent vertices

x, y \in V (G)

their weights are distinct, where the weight of a vertex

x \in V (G)

is the sum of all labels of vertices whose distance from x is at most d (respectively, at most d but at least 1). The minimum k for which there exists a local inclusive (respectively, non-inclusive) d-distance vertex irregular labeling of G is called the local inclusive (respectively, non-inclusive) d-distance vertex irregularity strength of G. In this paper, we present several basic results on the local inclusive d-distance vertex irregularity strength for

d = 1

and determine the precise values of the corresponding graph invariant for certain families of graphs. Full article

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

► Show Figures

Figure 1

11 pages, 945 KiB

Open AccessArticle

Free Cells in Hyperspaces of Graphs

by José Ángel Juárez Morales, Gerardo Reyna Hernández, Jesús Romero Valencia and Omar Rosario Cayetano

Mathematics 2021, 9(14), 1627; https://0-doi-org.brum.beds.ac.uk/10.3390/math9141627 - 10 Jul 2021

Viewed by 1390

Abstract

Often for understanding a structure, other closely related structures with the former are associated. An example of this is the study of hyperspaces. In this paper, we give necessary and sufficient conditions for the existence of finitely-dimensional maximal free cells in the hyperspace [...] Read more.

C (G)

of a dendrite G; then, we give necessary and sufficient conditions so that the aforementioned result can be applied when G is a dendroid. Furthermore, we prove that the arc is the unique arcwise connected, compact, and metric space X for which the anchored hyperspace

C_{p} (X)

is an arc for some

p \in X

. Full article

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

► Show Figures

Figure 1

12 pages, 247 KiB

Open AccessArticle

Local Antimagic Chromatic Number for Copies of Graphs

by Martin Bača, Andrea Semaničová-Feňovčíková and Tao-Ming Wang

Mathematics 2021, 9(11), 1230; https://0-doi-org.brum.beds.ac.uk/10.3390/math9111230 - 27 May 2021

Cited by 9 | Viewed by 2186

Abstract

An edge labeling of a graph

G = (V, E)

using every label from the set

{1, 2, \dots, | E (G) |}

exactly once is a local antimagic labeling if the vertex-weights [...] Read more.

An edge labeling of a graph

G = (V, E)

using every label from the set

{1, 2, \dots, | E (G) |}

exactly once is a local antimagic labeling if the vertex-weights are distinct for every pair of neighboring vertices, where a vertex-weight is the sum of labels of all edges incident with that vertex. Any local antimagic labeling induces a proper vertex coloring of G where the color of a vertex is its vertex-weight. This naturally leads to the concept of a local antimagic chromatic number. The local antimagic chromatic number is defined to be the minimum number of colors taken over all colorings of G induced by local antimagic labelings of G. In this paper, we estimate the bounds of the local antimagic chromatic number for disjoint union of multiple copies of a graph. Full article

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

17 pages, 275 KiB

Open AccessArticle

Inequalities on the Generalized ABC Index

by Paul Bosch, Edil D. Molina, José M. Rodríguez and José M. Sigarreta

Mathematics 2021, 9(10), 1151; https://0-doi-org.brum.beds.ac.uk/10.3390/math9101151 - 20 May 2021

Cited by 4 | Viewed by 1544

Abstract

In this work, we obtained new results relating the generalized atom-bond connectivity index with the general Randić index. Some of these inequalities for

A B C_{α}

improved, when

α = 1 / 2

, known results on the

A B C

index. [...] Read more.

In this work, we obtained new results relating the generalized atom-bond connectivity index with the general Randić index. Some of these inequalities for

A B C_{α}

improved, when

α = 1 / 2

, known results on the

A B C

index. Moreover, in order to obtain our results, we proved a kind of converse Hölder inequality, which is interesting on its own. Full article

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

12 pages, 311 KiB

Open AccessArticle

The Size, Multipartite Ramsey Numbers for nK₂ Versus Path–Path and Cycle

by Yaser Rowshan, Mostafa Gholami and Stanford Shateyi

Mathematics 2021, 9(7), 764; https://0-doi-org.brum.beds.ac.uk/10.3390/math9070764 - 01 Apr 2021

Cited by 6 | Viewed by 1856

Abstract

For given graphs

G_{1}, G_{2}, \dots, G_{n}

and any integer j, the size of the multipartite Ramsey number

m_{j} (G_{1}, G_{2}, \dots, G_{n})

is the smallest positive [...] Read more.

For given graphs

G_{1}, G_{2}, \dots, G_{n}

and any integer j, the size of the multipartite Ramsey number

m_{j} (G_{1}, G_{2}, \dots, G_{n})

is the smallest positive integer t such that any n-coloring of the edges of

K_{j \times t}

contains a monochromatic copy of

G_{i}

in color i for some i,

1 \leq i \leq n

, where

K_{j \times t}

denotes the complete multipartite graph having j classes with t vertices per each class. In this paper, we computed the size of the multipartite Ramsey numbers

m_{j} (K_{1, 2}, P_{4}, n K_{2})

for any

j, n \geq 2

and

m_{j} (n K_{2}, C_{7})

, for any

j \leq 4

and

n \geq 2

. Full article

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

► Show Figures

Figure 1

7 pages, 839 KiB

Open AccessArticle

Total Roman {3}-Domination: The Complexity and Linear-Time Algorithm for Trees

by Xinyue Liu, Huiqin Jiang, Pu Wu and Zehui Shao

Mathematics 2021, 9(3), 293; https://0-doi-org.brum.beds.ac.uk/10.3390/math9030293 - 02 Feb 2021

Cited by 1 | Viewed by 1631

Abstract

For a simple graph

G = (V, E)

with no isolated vertices, a total Roman {3}-dominating function(TR3DF) on G is a function

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

having the [...] Read more.

For a simple graph

G = (V, E)

with no isolated vertices, a total Roman {3}-dominating function(TR3DF) on G is a function

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

having the property that (i)

\sum_{w \in N (v)} f (w) \geq 3

f (v) = 0

; (ii)

\sum_{w \in N (v)} f (w) \geq 2

f (v) = 1

; and (iii) every vertex v with

f (v) \neq 0

has a neighbor u with

f (u) \neq 0

for every vertex

v \in V (G)

. The weight of a TR3DF f is the sum

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

and the minimum weight of a total Roman {3}-dominating function on G is called the total Roman {3}-domination number denoted by

γ_{t {R 3}} (G)

. In this paper, we show that the total Roman {3}-domination problem is NP-complete for planar graphs and chordal bipartite graphs. Finally, we present a linear-time algorithm to compute the value of

γ_{t {R 3}}

for trees. Full article

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

► Show Figures

Figure 1

Journal Menu

Journal Browser

Advances in Discrete Applied Mathematics and Graph Theory

Share This Special Issue

Special Issue Editors

Special Issue Information

Keywords

Published Papers (12 papers)

Research

Further Information

Guidelines

MDPI Initiatives

Follow MDPI