Next Article in Journal
An Intelligent Vision-Based Tracking Method for Underground Human Using Infrared Videos
Previous Article in Journal
New Obstructions to Warped Product Immersions in Complex Space Forms
Previous Article in Special Issue
Double Roman Domination in Generalized Petersen Graphs P(ck, k)
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Editorial

Graph Algorithms and Graph Theory-Symmetry Special Issue

Department of Computer Science, Université de Sherbrooke, Sherbrooke, QC J1K 2R1, Canada
Symmetry 2022, 14(8), 1748; https://doi.org/10.3390/sym14081748
Submission received: 12 August 2022 / Accepted: 16 August 2022 / Published: 22 August 2022
(This article belongs to the Special Issue Graph Algorithms and Graph Theory)
Understanding the structure of graphs and the interplay between their parameters is a fundamental question that has been actively researched over the last century. Indeed, graph theory has played a prominent role in discrete mathematics, but has also created connections with other areas such as topology, dynamical systems theory, and category theory. In addition, graphs are also known for their wide applications in other sciences, including computer science, biochemistry, electrical engineering, or social sciences. This Special Issue contains 11 papers that develop knowledge on structural and algorithmic graph theory from several angles. The range of topics covered in this issue include the structural graph parameters of domination, pancyclicity, zero forcing numbers, and connectivity, as well as algorithms for graph clustering, clique traversals, finding fuzzy paths, independent sets, and analyzing Petri nets.

1. Structural Graph Theory

In [1], Poklukar et al. study the double Roman domination number. Motivated by the task of organizing military supervision, this number assigns a rank in { 0 , 1 , 2 , 3 } to each vertex, such that each 0 rank vertex is adjacent to a rank 3 or two rank 2 vertices, and each 1 rank vertex is adjacent to a rank 2 or 3 vertex. The idea is that low-rank elements should be surrounded by enough high-rank neighbors in cases of need. The authors provide several bounds on the double Roman number of multiple variants of the generalized Petersen graph. Then, in [2], Muaengwaeng et al. provide new results on the pancyclicity of graphs, which ask whether a graph contains a cycle of all possible lengths. In many cases, conditions that are sufficient for Hamiltonicity are also sufficient for pancyclicity. The authors study a graph class, the n-generalized prisms over skirted graphs, that was recently shown to be Hamiltonian, and show that pancyclicity also holds.
In [3], Gomez et al. provide a complete characterization of graphs with zero-forcing number 2. These are graphs in which we can find a set S of two vertices, such that the following procedure ends with S containing every vertex. As long as some element of S has exactly one neighbor v outside of S, v can be added to S. The zero-forcing number of graphs was introduced 15 years ago, but the small zero-forcing number had not yet been understood. Nichiata then brings graph theory to geometry [4]. The author states the following theorem from the literature: if three circles of radius r intersect at a point and each pairwise intersect at another point, then there is another circle of radius r that contains these pairwise intersections. The author then asks the more general question: if objects x , y , and z have certain geometrical properties, does another object w exist with the same properties? Graph diagrams are then used to prove several extensions of the theorem. In [5], Santra et al. study semi-ring valued graphs, which depict order relationships between elements of a semi-ring, and are known for their highly symmetric structure. Several parameters of semi-ring graphs have been studied before, but the authors are the first to provide results on the connectivity of these graphs.

2. Algorithmic Graph Theory and Applications

In [6], Lee is motivated by network routing applications and studies the k-maximum clique traversal problem, which asks for a smallest set of vertices that contains k vertices of every maximum clique. As the authors show, although there is probably no fixed-parameter algorithm for this problem in terms of the size of the set, the problem is shown to be fixed-parameter-tractable under the treewidth parameter. Zhang et al. then propose an application of graph theory in robot motion control [7]. They describe how a robot assembled by joint and link modules can be modeled as a graph that is able to describe the set of all possible reconfigurations of the robot, as well as the paths to undertake to reach certain configurations. Then Klobučar and Manger [8] focus on the problem of finding a maximum weight independent set in a tree. This can be easily achieved through a classical dynamic programming procedure, but here the authors model the weights as intervals to introduce uncertainty. The objective then becomes one of finding the min–max regret, which is shown to be NP-hard but admits approximation algorithms. In a similar vein, Valdés et al. study the problem of finding the shortest paths in graphs with fuzzy cost functions on the edges [9]. A fuzzy extension of Dijkstra’a algorithm is proposed and its performance is assessed experimentally.
In [10], Rezig et al. study Petri nets, which are used to model the execution flow of programs using graph theory. The problem of deciding whether a certain configuration of the Petri net can be reached is crucial in order to verify whether a system cannot reach unwanted states. However, the problem is computationally demanding, and the authors propose an approach based on region separation of the Petri net, since smaller regions are easier to analyze. Finally, Bardu in [11] proposes a novel graph clustering approach designed specifically for the partitioning of texture images into similarity classes.
In conclusion, this issue should be of interest to either mathematicians interested in the structure and symmetry of graphs, to computer scientists who design graph algorithms, and to applied scientists who can model their problems of interest using graph theory.

Funding

This research received no external funding.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Not applicable

Conflicts of Interest

The author declares no conflict of interest.

References

  1. Rupnik Poklukar, D.; Žerovnik, J. Double Roman Domination in Generalized Petersen Graphs P (ck, k). Symmetry 2022, 14, 1121. [Google Scholar] [CrossRef]
  2. Muaengwaeng, A.; Boonklurb, R.; Singhun, S. Pancyclicity of the n-Generalized Prism over Skirted Graphs. Symmetry 2022, 14, 816. [Google Scholar] [CrossRef]
  3. Gomez, L.; Rubi, K.; Terrazas, J.; Narayan, D.A. All Graphs with a Failed Zero Forcing Number of Two. Symmetry 2021, 13, 2221. [Google Scholar] [CrossRef]
  4. Nichita, F.F. On the Johnson–Tzitzeica Theorem, Graph Theory, and Yang–Baxter Equations. Symmetry 2021, 13, 2070. [Google Scholar] [CrossRef]
  5. Santra, S.S.; Victor, P.; Chandramouleeswaran, M.; El-Nabulsi, R.A.; Khedher, K.M.; Govindan, V. Connectivity of Semiring Valued Graphs. Symmetry 2021, 13, 1227. [Google Scholar] [CrossRef]
  6. Lee, C.M. Remarks on Parameterized Complexity of Variations of the Maximum-Clique Transversal Problem on Graphs. Symmetry 2022, 14, 676. [Google Scholar] [CrossRef]
  7. Zhang, T.; Du, Q.; Yang, G.; Wang, C.; Chen, C.Y.; Zhang, C.; Chen, S.; Fang, Z. Assembly Configuration Representation and Kinematic Modeling for Modular Reconfigurable Robots Based on Graph Theory. Symmetry 2022, 14, 433. [Google Scholar] [CrossRef]
  8. Klobučar, A.; Manger, R. Solving Robust Weighted Independent Set Problems on Trees and under Interval Uncertainty. Symmetry 2021, 13, 2259. [Google Scholar] [CrossRef]
  9. Valdés, L.; Ariza, A.; Allende, S.M.; Triviño, A.; Joya, G. Search of the Shortest Path in a Communication Network with Fuzzy Cost Functions. Symmetry 2021, 13, 1534. [Google Scholar] [CrossRef]
  10. Rezig, S.; Rezg, N.; Hajej, Z. Online Activation and Deactivation of a Petri Net Supervisor. Symmetry 2021, 13, 2218. [Google Scholar] [CrossRef]
  11. Barbu, T. Automatic unsupervised texture recognition framework using anisotropic diffusion-based multi-scale analysis and weight-connected graph clustering. Symmetry 2021, 13, 925. [Google Scholar] [CrossRef]
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Share and Cite

MDPI and ACS Style

Lafond, M. Graph Algorithms and Graph Theory-Symmetry Special Issue. Symmetry 2022, 14, 1748. https://doi.org/10.3390/sym14081748

AMA Style

Lafond M. Graph Algorithms and Graph Theory-Symmetry Special Issue. Symmetry. 2022; 14(8):1748. https://doi.org/10.3390/sym14081748

Chicago/Turabian Style

Lafond, Manuel. 2022. "Graph Algorithms and Graph Theory-Symmetry Special Issue" Symmetry 14, no. 8: 1748. https://doi.org/10.3390/sym14081748

APA Style

Lafond, M. (2022). Graph Algorithms and Graph Theory-Symmetry Special Issue. Symmetry, 14(8), 1748. https://doi.org/10.3390/sym14081748

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop