Domination, Independence and Distances in Graphs

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

Deadline for manuscript submissions: closed (31 July 2023) | Viewed by 2774

Special Issue Editors

Department of Algorithms and Systems Modelling, Faculty of Electronics, Telecommunications and Informatics, Gdańsk Tech, 80-233 Gdańsk, Poland
Interests: graph theory; algorithmic graph theory
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,

Graph theory is a fascinating section of discrete mathematics. It can be used as a model of many real-life objects and relations between them, serving as a tool to solve many important problems in today’s world. One of the most known examples that use graph theory are telecommunications networks, biological networks, social networks, and many others. Graph algorithms, for example, can help us to find the shortest route between two places, or to place important elements in networks.

Some of the broadest studied parameters in graph theory, such as the domination number, the independence number, and their variants, are always in the spotlight of research, and a significant part of them is related to distance aspects. They have been extensively studied up to now, and there is a huge body of literature on them. The interest in those graph parameters can be justified by their application in both diverse theoretical fields and many practical aspects.

Since we consider that there are still lots of interesting new results to be discovered related to domination, independence, and distances in graphs, we invite authors to submit relevant contributions to this Special Issue of Mathematics entitled “Domination, Independence, and Distances in Graphs”.

Dr. Joanna Raczek
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

  • dominating sets in graphs
  • distances in graphs
  • convex sets in graphs
  • independence in graphs
  • chromatic number of a graph
  • graph algorithms
  • application of graph theory

Published Papers (2 papers)

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

Research

13 pages, 535 KiB  
Article
Sufficient Conditions of 6-Cycles Make Planar Graphs DP-4-Colorable
by Kittikorn Nakprasit, Watcharintorn Ruksasakchai and Pongpat Sittitrai
Mathematics 2022, 10(15), 2762; https://0-doi-org.brum.beds.ac.uk/10.3390/math10152762 - 04 Aug 2022
Viewed by 1109
Abstract
In simple graphs, DP-coloring is a generalization of list coloring and thus many results of DP-coloring generalize those of list coloring. Xu and Wu proved that every planar graph without 5-cycles adjacent simultaneously to 3-cycles and 4-cycles is 4-choosable. Later, Sittitrai and Nakprasit [...] Read more.
In simple graphs, DP-coloring is a generalization of list coloring and thus many results of DP-coloring generalize those of list coloring. Xu and Wu proved that every planar graph without 5-cycles adjacent simultaneously to 3-cycles and 4-cycles is 4-choosable. Later, Sittitrai and Nakprasit showed that if a planar graph has no pairwise adjacent 3-, 4-, and 5-cycles, then it is DP-4-colorable, which is a generalization of the result of Xu and Wu. In this paper, we extend the results on 3-, 4-, 5-, and 6-cycles by showing that every planar graph without 6-cycles simultaneously adjacent to 3-cycles, 4-cycles, and 5-cycles is DP-4-colorable, which is also a generalization of previous studies as follows: every planar graph G is DP-4-colorable if G has no 6-cycles adjacent to i-cycles where i{3,4,5}. Full article
(This article belongs to the Special Issue Domination, Independence and Distances in Graphs)
Show Figures

Figure 1

7 pages, 251 KiB  
Communication
A Note on Outer-Independent 2-Rainbow Domination in Graphs
by Abel Cabrera-Martínez
Mathematics 2022, 10(13), 2287; https://0-doi-org.brum.beds.ac.uk/10.3390/math10132287 - 30 Jun 2022
Cited by 1 | Viewed by 1007
Abstract
Let G be a graph with vertex set V(G) and f:V(G){,{1},{2},{1,2}} be a function. We say that [...] Read more.
Let G be a graph with vertex set V(G) and f:V(G){,{1},{2},{1,2}} be a function. We say that f is an outer-independent 2-rainbow dominating function on G if the following two conditions hold: (i)V={xV(G):f(x)=} is an independent set of G. (ii)uN(v)f(u)={1,2} for every vertex vV. The outer-independent 2-rainbow domination number of G, denoted by γr2oi(G), is the minimum weight ω(f)=xV(G)|f(x)| among all outer-independent 2-rainbow dominating functions f on G. In this note, we obtain new results on the previous domination parameter. Some of our results are tight bounds which improve the well-known bounds β(G)γr2oi(G)2β(G), where β(G) denotes the vertex cover number of G. Finally, we study the outer-independent 2-rainbow domination number of the join, lexicographic, and corona product graphs. In particular, we show that, for these three product graphs, the parameter achieves equality in the lower bound of the previous inequality chain. Full article
(This article belongs to the Special Issue Domination, Independence and Distances in Graphs)
Show Figures

Figure 1

Back to TopTop