Search

We present a new subclass of interval graphs that generalizes connected proper interval graphs. These graphs are characterized by vertex orderings called connected perfect elimination orderings (PEO), i.e., PEOs where consecutive vertices are adjacent. Alternatively, these graphs can also be characterized by special interval models and clique orderings. We present a linear-time recognition algorithm that uses PQ-trees. Furthermore, we study the behavior of multi-sweep graph searches on this graph class. This study also shows that Corneil's well-known LBFS-recognition algorithm for proper interval graphs can be generalized to a large family of graph searches. Finally, we show that a strong result on the existence of Hamiltonian paths and cycles in proper interval graphs can be generalized to semi-proper interval graphs. • Introduction of semi-proper interval graphs, a novel subclass of interval graphs generalizing connected proper interval graphs. • Linear-time recognition algorithm for semi-proper interval graphs. • Generalization of Corneil's LBFS recognition algorithm of proper interval graphs. • Generalization of Hamilton properties of proper interval graphs to semi-proper intervals. [ABSTRACT FROM AUTHOR]

The Hamiltonian cycle and path problems are fundamental in graph theory and useful in modelling real-life problems. Research in this area is directed toward designing better and better algorithms for general problems, but also toward defining new special cases for which exact polynomial-time algorithms exist. In the paper, such new classes of digraphs are proposed. The classes include, among others, quasi-adjoint graphs, which are a superclass of adjoints, directed line graphs, and graphs modelling a DNA sequencing problem. [ABSTRACT FROM AUTHOR]

Chen considered the existence of a Hamiltonian cycle containing a matching and avoiding some edges in an -cube . In this paper, we considered the existence of a Hamiltonian path and obtained the following result. For , let be a matching of , and let be a set of edges in with . Let and be two vertices of with different parities satisfying . If all vertices in have a degree of at least , then there exists a Hamiltonian path joining and passing through in , with the exception of two cases: (1) there exist two neighbors and of (or ) satisfying and (or ); (2) there exists a path of length 3 satisfying and or and . [ABSTRACT FROM AUTHOR]

Chen considered the existence of a Hamiltonian cycle containing a matching and avoiding some edges in an $ n $-cube $ Q_n $. In this paper, we considered the existence of a Hamiltonian path and obtained the following result. For $ n\geq4 $, let $ M $ be a matching of $ Q_n $, and let $ F $ be a set of edges in $ Q_n-M $ with $ |M\cup F|\leq2n-6 $. Let $ x $ and $ y $ be two vertices of $ Q_n $ with different parities satisfying $ xy\notin M $. If all vertices in $ Q_n-F $ have a degree of at least $ 2 $, then there exists a Hamiltonian path joining $ x $ and $ y $ passing through $ M $ in $ Q_n-F $, with the exception of two cases: (1) there exist two neighbors $ v $ and $ t $ of $ x $ (or $ y $) satisfying $ d_{Q_n-F}(v) = 2 $ and $ xt\in M $ (or $ yt\in M $); (2) there exists a path $ xvuy $ of length 3 satisfying $ d_{Q_n-F}(v) = 2 $ and $ uy\in M $ or $ d_{Q_n-F}(u) = 2 $ and $ xv\in M $.

Given a graph G , let S and T be two disjoint vertex subsets of equal size k in G. A many-to-many k -disjoint path cover of G joining S and T is a set of k vertex-disjoint paths between S and T that altogether cover every vertex of the graph. It is said to be paired if each vertex of S must be joined to a designated vertex of T , or unpaired otherwise. Let Γ n be a Cayley graph generated by a transposition tree with bipartition V 0 and V 1. Let S ⊆ V 0 and T ⊆ V 1 be two vertex subsets of equal size two. It is shown in this paper that Γ n has an unpaired many-to-many two-disjoint path cover joining S and T with at most n − 4 faulty edges, where n ≥ 4. The result is optimal with respect to the degree of Γ n. As applications, the edge fault-tolerant two-disjoint path covers for the star network, bubble-sort network and modified bubble-sort network are derived. [ABSTRACT FROM AUTHOR]

A moplex is a natural graph structure that arises when lifting Dirac's classical theorem from chordal graphs to general graphs. The notion is known to be closely related to lexicographic searches in graphs as well as to asteroidal triples, and has been applied in several algorithms related to graph classes, such as interval graphs, claw‐free, and diamond‐free graphs. However, while every noncomplete graph has at least two moplexes, little is known about structural properties of graphs with a bounded number of moplexes. The study of these graphs is, in part, motivated by the parallel between moplexes in general graphs and simplicial modules in chordal graphs: unlike in the moplex setting, properties of chordal graphs with a bounded number of simplicial modules are well understood. For instance, chordal graphs having at most two simplicial modules are intervals. In this work, we initiate an investigation of k $k$‐moplex graphs, which are defined as graphs containing at most k $k$ moplexes. Of particular interest is the smallest nontrivial case k=2 $k=2$, which forms a counterpart to the class of interval graphs. As our main structural result, we show that, when restricted to connected graphs, the class of 2‐moplex graphs is sandwiched between the classes of proper interval graphs and cocomparability graphs; moreover, both inclusions are tight for hereditary classes. From a complexity‐theoretic viewpoint, this leads to the natural question of whether the presence of at most two moplexes guarantees a sufficient amount of structure to efficiently solve problems that are known to be intractable on cocomparability graphs, but not on proper interval graphs. We develop new reductions that answer this question negatively for two prominent problems fitting this profile, namely, Graph Isomorphism and Max‐Cut. On the other hand, we prove that every connected 2‐moplex graph contains a Hamiltonian path, generalising the same property of connected proper interval graphs. Furthermore, for graphs with a higher number of moplexes, we lift the previously known result that graphs without asteroidal triples have at most two moplexes to the more general setting of larger asteroidal sets. [ABSTRACT FROM AUTHOR]

Embedding cycles into a network topology is crucial for a network simulation. In particular, embedding Hamiltonian cycles is a major requirement for designing good interconnection networks. A graph G is called r-spanning cyclable if, for any r distinct vertices v 1 , v 2 , ... , v r of G, there exist r cycles C 1 , C 2 , ... , C r in G such that v i is on C i for every i, and every vertex of G is on exactly one cycle C i . If r = 1 , this is the classical Hamiltonian problem. In this paper, we focus on the problem of embedding spanning disjoint cycles in bipartite k-ary n-cubes. Let k ≥ 4 be even and n ≥ 2 . It is shown that the n-dimensional bipartite k-ary n-cube Q n k is m-spanning cyclable with m ≤ 2 n − 1 . Considering the degree of Q n k , the result is optimal. [ABSTRACT FROM AUTHOR]

One of the well-known NP-hard optimization problems in graph theory is finding the longest path in a graph. This problem remains NP-hard for general grid graphs, and its complexity is open for grid graphs that have a limited number of holes. In this paper, we study this problem for odd-sized O -shaped grid graphs, i.e. a rectangular grid graph with a rectangular hole. We show that this problem can be solved in linear time. [ABSTRACT FROM AUTHOR]

The Hamiltonian path is a well-known NP-complete problem. This problem has been studied for solid supergrid graphs, in some special cases, and recently for 3-connected solid supergrid graphs. In this paper, we extend the previous result to general solid supergrid graphs, and present an O(n²)-time algorithm where n is the number of the vertices of the input graph. [ABSTRACT FROM AUTHOR]

Let G={G1,...,Gs} ${\bf{G}}=\{{G}_{1},\ldots ,{G}_{s}\}$ be a collection of not necessarily distinct n $n$‐vertex graphs with the same vertex set V $V$. We use G˜ $\tilde{{\bf{G}}}$ to denote an edge‐colored multigraph of G ${\bf{G}}$ with V(G˜)=V $V(\tilde{{\bf{G}}})=V$ and E(G˜) $E(\tilde{{\bf{G}}})$ a multiset consisting of E(G1),...,E(Gs) $E({G}_{1}),\ldots ,E({G}_{s})$, and the edge e $e$ of G˜ $\tilde{{\bf{G}}}$ is colored by i $i$ if e∈E(Gi) $e\in E({G}_{i})$. A graph H $H$ is rainbow in G ${\bf{G}}$ if any two edges of H $H$ belong to different graphs of G ${\bf{G}}$. We say that G ${\bf{G}}$ is rainbow vertex‐pancyclic if each vertex of V $V$ is contained in a rainbow cycle of G ${\bf{G}}$ with length ℓ $\ell $ for every integer ℓ∈[3,n] $\ell \in [3,n]$, and that G ${\bf{G}}$ is rainbow panconnected if for any pair of vertices u $u$ and v $v$ of V $V$ there exists a rainbow path of G ${\bf{G}}$ with length ℓ $\ell $ joining u $u$ and v $v$ for every integer ℓ∈[dG˜(u,v),n−1] $\ell \in [{d}_{\tilde{{\bf{G}}}}(u,v),n-1]$. In this paper, we study the existences of rainbow spanning trees and rainbow Hamiltonian paths in G ${\bf{G}}$ under the Ore‐type conditions. Moreover, we study the rainbow vertex‐pancyclicity and rainbow panconnectedness, as well as the existence of rainbow cliques in G ${\bf{G}}$ under the Dirac‐type conditions. We also give some examples to show the sharpness of our results. [ABSTRACT FROM AUTHOR]

The distributed computing or parallel computing system uses an interconnection network as a topology structure to connect a large number of processors. The disjoint paths of interconnection networks are related to parallel computing and the fault tolerance. l-path cover of graph G = (V (G) , E (G)) consists of (internally) disjoint paths P k s ( 1 ≤ k ≤ l ), where ∪ k = 1 l V (P k) = V (G) . The bubble-sort star graph is bipartite and has favorable reliability and fault tolerance which are critical for multiprocessor systems. We focus on the one-to-one 1-path cover, one-to-one (2 n - 3) -path cover, and many-to-many 2-path cover of the bubble-sort star graph B S n . More specifically, let V (B S n) = V e ∪ V o with V e ∩ V o = ∅ , for { u , x } ⊂ V e and { v , y } ⊂ V o , we prove that (1) B S n contains a 1-path cover, i.e., Hamiltonian path P uv , (2) B S n contains one-to-one (2 n - 3) -path cover P k s ( 1 ≤ k ≤ 2 n - 3 ) between u and v, and (3) B S n contains many-to-many 2-path cover P uv and P xy , where n ≥ 3 . Since B S n is (2 n - 3) -regular graph, the one-to-one (2 n - 3) -path cover is the maximal one-to-one path cover. [ABSTRACT FROM AUTHOR]

In this paper, we focus on Hamiltonian paths and Hamiltonian cycles passing through prescribed linear forests in n -dimensional star graph S n with fault-tolerant edges. Let F ⊆ E (S n) be a fault-tolerant edges set and L be a linear forest of S n − F , and | E (L) | + | F | ≤ n − 3. For any two vertices u and v in different partite sets, we prove that if { u , v } and L are compatible in S n , then there is a Hamiltonian path of S n − F between u and v , which passes through each edge of L. That is, S n is (n − 3) -edge fault-tolerant prescribed Hamiltonian laceable for n ≥ 4. And we show that there is a Hamiltonian cycle of S n − F passing through each edge of L , that is, S n is (n − 3) -edge fault-tolerant prescribed Hamiltonian for n ≥ 4. These results are optimal in the described sense. [ABSTRACT FROM AUTHOR]

Fuzzy Topological Topographic Mapping (FTTM) is a mathematical model that consists of a set of homeomorphic topological spaces designed to solve the neuro magnetic inverse problem. A sequence of FTTM, denoted as F T T M n , is an extension of FTTM that is arranged in a symmetrical form. The special characteristic of FTTM, namely the homeomorphisms between its components, allows the generation of new FTTM. Later, the F T T M n can also be viewed as a graph. Previously, a group of researchers defined an assembly graph and utilized it to model a DNA recombination process. Some researchers then used this to introduce the concept of tangled cords for assembly graphs. In this paper, the tangled cord for F T T M 4 is used to calculate the Eulerian paths. Furthermore, it is utilized to determine the least upper bound of the Hamiltonian paths of its assembly graph. Hence, this study verifies the conjecture made by Burns et al. [ABSTRACT FROM AUTHOR]

Connected Square Network Graphs (CSNG) in the study of Selcuk (2022) and Selcuk and Tankul (2022) is reconsidered in this paper. Although (CSNG) is a 2-dimensional mesh structure, the most important feature of this graph is that it is a hypercube variant. For this reason, this study focuses on development algorithms that find solutions to various problems for (CSNG) with the help of hypercube. Firstly, an efficient algorithm that finds the Hamiltonian path is given. Further, two different algorithms that perform the mapping of labels in graph and the unicast routing are given. Furthermore, the parallel process for mapping and unicast routing is discussed. Finally, guidelines are given for broadcasting algorithms.

Steganography is used at a large scale in various security systems. It is the science and art of hiding secret information into data. Various steganography schemes have been proposed over the years, but most of them are not promising enough to provide a large capacity of embedding and visually prevent the image's degradation. Histograms can reveal the existence of secret information, and it is also an essential issue in the security of the data. In this Paper, the main objective is to reduce the bit-flip cost count and maximize the PSNR value to reduce the image distortion and keep the data secure by using secret keys while embedding. In this proposed paper, the genetic algorithm (GA) is employed to select the best chromosome that has the minimum bit-flip cost count and maximum PSNR. Data security is achieved by the secret key generated from Hamiltonian path for embedding and retrieving of data. The proposed technique is robust against steganographic attacks and even if presence of data is observed it not possible to guess the embedding pattern. The result section demonstrates that the proposed technique outperform the existing techniques by increasing the PSNR significantly by approx 7 percent that lead to the increase in PSNR value up to 41.8dB for three bit per pixel embedding. [ABSTRACT FROM AUTHOR]

For a connected graph, a path containing all vertices is known as a Hamiltonian path. For general graphs, there is no known necessary and sufficient condition for the existence of Hamiltonian paths and the complexity of finding a Hamiltonian path in general graphs is NP-Complete. We present a necessary and sufficient condition for the existence of Hamiltonian paths in 2-trees. Using our characterization, we also present a linear-time algorithm for the existence of Hamiltonian paths in 2-trees. Our characterization is based on a deep understanding of the structure of 2-trees and the combinatorics presented here may be used in other combinatorial problems restricted to 2-trees. [ABSTRACT FROM AUTHOR]

The Hamiltonian path and cycle problems are well-known NP-complete problems. A given graph is Hamiltonian-connected if there exists a Hamiltonian path between any two vertices and is Hamiltonian if it has a Hamiltonian cycle. In this paper, we show that every 3-connected solid supergrid graph is Hamiltonian-connected and every 2-connected solid supergrid graph is Hamiltonian, and give linear-time algorithms for computing Hamiltonian cycles and paths in these graphs. [ABSTRACT FROM AUTHOR]

We prove that a tournament T $T$ and its converse −T $-T$ contain the same number of oriented Hamiltonian paths and the same number of oriented Hamiltonian cycles, of any given type, as a generalization of Rosenfeld's result proved for antidirected paths. [ABSTRACT FROM AUTHOR]

Inception module is one of the most used variants in convolutional neural networks. It has a large portfolio of success cases in computer vision. In the past years, diverse inception flavours, differing in the number of branches, the size and the number of the kernels, have appeared in the scientific literature. They are proposed based on the expertise of the practitioners without any optimization process. In this work, an implementation of population-based incremental learning is proposed for automatic optimization of the hyperparameters of the inception module. This hyperparameters optimization undertakes classification of the MNIST database of handwritten digit images. This problem is widely used as a benchmark in classification, and therefore, the learned best configurations for the Inception module will be of wide use in the deep learning community. In order to reduce the carbon footprint of the optimization process, policies for reducing the redundant evaluations have been undertaken. As a consequence of this work, an evaluation of configurations of the inception module and a mechanism for optimizing hyperparameters in deep learning architectures are stated. [ABSTRACT FROM AUTHOR]

Given a graph G , let S and T be two vertex-disjoint subsets of equal size k of G. A k -disjoint path cover of G corresponding to S and T is the union of k vertex-disjoint paths among S and T that spans G. If every vertex of S should be joined to a prescribed vertex in T , it is defined to be paired, otherwise it is unpaired. Let S T n be a star graph with bipartition V 0 and V 1. Let S ⊆ V 0 and T ⊆ V 1 be two vertex subsets of equal size k. It is shown in this paper that S T n admits an unpaired k -disjoint path cover between S and T , where k ≤ n − 2 and n ≥ 4. In view of the degree of S T n , this result is optimal. • The existence of disjoint path cover is closely related to the hamiltonicity of a graph. • This paper investigates the disjoint path cover problem of star graphs. • It is shown in this paper that an n -dimensional star graph S T n is unpaired k -disjoint path coverable, where n ≥ 4 and k ≤ n − 2. [ABSTRACT FROM AUTHOR]

Given a set S of n colored points of m colors inside a simple polygon P, each point within the polygon has a specific color that is not necessarily unique, i.e., they may exhibit the same color. The study aims to find a simple path that traverses at least one point of each color using a set of S points contained within a simple polygon P. Two results are presented in this study. First, we demonstrate that finding such simple paths inside a simple polygon is an N P - c o m p l e t e problem. Moreover, we provide a polynomial-time algorithm that computes the simple path when P is an orthogonal spiral simple polygon, and our objective is to locate a simple Hamiltonian path L using all points of S inside P. Our algorithm has a time complexity of O (r + r n 4) , where r is the number of reflex vertices in P and n is the number of points in S. [ABSTRACT FROM AUTHOR]

Data center network plays an important role in improving the performance of cloud computing. Hamiltonian properties and Hamiltonian connectivity have important applications in communication network. The existence of Hamiltonian path can make the network more efficient communication. HCN and BCN networks are two important data center networks with nice routing performance and excellent scalability. In this paper, we study the Hamiltonian properties and disjoint path covers of these two networks. Firstly, we prove that HCN(n, h) is Hamiltonian-connected with n ≥ 4 and h ≥ 0 . Secondly, we prove that BCN (α , β , h , γ) is Hamiltonian-connected with h < γ , α ≥ 4 , β ≥ 1 , h ≥ 0 , γ ≥ 0 . Finally, we design Hamiltonian path construction algorithms for HCN and BCN networks. Simulation experiments verify the construction process of Hamiltonian path. Moreover, the running time of the routing algorithm designed in this study is compared with the classical shortest path multicast tree algorithm DijkstraSPT, and its running time is lower than that of the algorithm DijkstraSPT by about 5ms on different server nodes, which shows that the routing algorithm designed in this study according to HCN and BCN structure operate efficiently. [ABSTRACT FROM AUTHOR]

A subgraph H = (V , E ′) of a graph G = (V , E) is non-separating if G \ E ′ , that is, the graph obtained from G by deleting the edges in E ′ , is connected. Analogously we say that a subdigraph X = (V , A ′) of a digraph D = (V , A) is non-separating if D \ A ′ is strongly connected. We study non-separating spanning trees and out-branchings in digraphs of independence number 2. Our main results are that every 2-arc-strong digraph D of independence number α (D) = 2 and minimum in-degree at least 5 and every 2-arc-strong oriented graph with α (D) = 2 and minimum in-degree at least 3 has a non-separating out-branching and minimum in-degree 2 is not enough. We also prove a number of other results, including that every 2-arc-strong digraph D with α (D) ≤ 2 and at least 14 vertices has a non-separating spanning tree and that every graph G with δ (G) ≥ 4 and α (G) = 2 has a non-separating Hamiltonian path. [ABSTRACT FROM AUTHOR]

The paper is devoted to the construction of mathematical models for problems on the shortest cycles and paths, that pass through a given number of nodes of a directed graph. Such cycles and paths are called k-node, where 1

In this paper, we have used two different proof techniques to show the Hamilton-connectedness of graphs. By using the vertex connectivity and Hamiltoniancity of graphs, we construct an infinite family of Hamilton-connected convex polytope line graphs whose underlying family of convex polytopes is not Hamilton-connected. By definition, we constructed two more infinite families of Hamilton-connected convex polytopes. As a by-product of our results, we compute exact values of the detour index of the families of Hamilton-connected convex polytopes. Finally, we classify the Platonic solids according to their Hamilton-connectedness and Hamilton-laceability properties.

Wireless sensor networks (WSNs) have been imperative means for the collection of information in various fields. Integration of WSN with the latest technology like unmanned aerial vehicles (UAVs) can increase the overall performance of the WSN by increasing the sensor coverage or reducing the latency. However, for full coverage of the sensors to avoid data loss, to reduce the time required to deliver the data to sink and to minimize the calculation of the total path length, overall trajectory optimization is required. In order to solve these challenges, in this work, trajectory of the UAV is considered as a hamiltonian path that covers all the cluster heads in the WSN. The proposed scheme is able to calculate path in polynomial time which is otherwise considered to be NP-Hard. Moreover, data of sensor nodes is sent directly to the UAV thereby eliminating the need of any routing protocol. Simulation results show that the coverage of nodes is improved along with minimized data loss in comparison with single-hop and multi-hop routing protocols of WSN. [ABSTRACT FROM AUTHOR]

Nowadays, the process of message encryption is the most important thing to secure our messages and communication between people. Message encryption methods are rapidly increasing currently due to the growth and evolution of the internet and network communications. Sharing information, personal messages, images, or data from one person to another over unsecured channels opens the door for attack, or hacking. To reduce this terminology and to provide better security, cryptographic or encryption techniques play an essential role. We have many kinds of symmetric enciphering techniques like the Caesar Cipher, Atbash Cipher, Hill Cipher, etc., In this paper, we are going to give the enciphering technique with the help of a complete graph, an adjacency matrix, and a generated self-invertible key matrix to encrypt and decrypt the given messages to produce a complicated ciphertext. Since we are using the self-invertible matrix as a key matrix, the inverse of this key matrix is always existing, and while we are decrypting the ciphertext, we do not need to compute the inverse of the key matrix. It helps us to reduce the computational complexity involved in the process of finding the inverse of a key matrix. [ABSTRACT FROM AUTHOR]

A graph is called Hamilton-connected if there exists a Hamiltonian path between every pair of its vertices. Determining whether or not a graph is Hamilton-connected is an NP-complete problem. In this paper, we present two methods to show Hamilton-connectivity in graphs. The first method uses the vertex connectivity and Hamiltoniancity of graphs, and, the second is the definition-based constructive method which constructs Hamiltonian paths between every pair of vertices. By employing these proof techniques, we show that the line graphs of the generalized Petersen, anti-prism and wheel graphs are Hamilton-connected. Combining it with some existing results, it shows that some of these families of Hamilton-connected line graphs have their underlying graph families non-Hamilton-connected. This, in turn, shows that the underlying graph of a Hamilton-connected line graph is not necessarily Hamilton-connected. As side results, the detour index being also an NP-complete problem, has been calculated for the families of Hamilton-connected line graphs. Finally, by computer we generate all the Hamilton-connected graphs on ≤ 7 vertices and all the Hamilton-laceable graphs on ≤ 10 vertices. Our research contributes towards our proposed conjecture that almost all graphs are Hamilton-connected. [ABSTRACT FROM AUTHOR]

Let H be a graph. A decomposition of H is a set of edge-disjoint subgraphs of H whose union is H. A Hamiltonian path (respectively, cycle) of H is a path (respectively, cycle) that contains every vertex of H exactly once. A k-star, denoted by Sk, is a star with k edges. In this paper, we give necessary and sufficient conditions for decomposing the complete graph into α copies of Hamiltonian path (cycle) and β copies of S3.

We study three classical graph problems – Hamiltonian path, minimum spanning tree, and minimum perfect matching on geometric graphs induced by bichromatic (red and blue) points. These problems have been widely studied for points in the Euclidean plane, and many of them are NP -hard. In this work, we consider these problems for collinear points. We show that almost all of these problems can be solved in linear time in this setting. [ABSTRACT FROM AUTHOR]

Moplexes are natural graph structures that arise when lifting Dirac's classical theorem from chordal graphs to general graphs. The notion is known to be closely related to lexicographic searches in graphs as well as to asteroidal triples, and has been applied in several algorithms related to graph classes such as interval graphs, claw-free, and diamond-free graphs. However, while every non-complete graph has at least two moplexes, little is known about structural properties of graphs with a bounded number of moplexes. The study of these graphs is, among others, motivated by the parallel between moplexes in general graphs and simplicial modules in chordal graphs: unlike in the moplex setting, properties of chordal graphs with a bounded number of simplicial modules are well understood. For instance, chordal graphs having at most two simplicial modules are interval. In this work we initiate an investigation of k-moplex graphs, which are defined as graphs containing at most k moplexes. Of particular interest is the smallest nontrivial case, k = 2, which forms a counterpart to the class of interval graphs. As our main structural result, we show that the class of connected 2-moplex graphs is sandwiched between the classes of proper interval graphs and cocomparability graphs; moreover, both inclusions are tight for hereditary classes. From a complexity theoretic viewpoint, this leads to the natural question of whether the presence of at most two moplexes guarantees a sufficient amount of structure to efficiently solve problems that are known to be intractable on cocomparability graphs, but not on proper interval graphs. We develop new reductions that answer this question negatively for two prominent problems fitting this profile, namely Graph Isomorphism and Max-Cut. Furthermore, for graphs with a higher number of moplexes, we lift the previously known result that graphs without asteroidal triples have at most two moplexes to the more general setting of larger asteroidal sets. We also discuss sufficient conditions for the existence of Hamiltonian paths in 2-moplex graphs as well as connections with avoidable vertices. [ABSTRACT FROM AUTHOR]

In this paper, we construct an algorithm for converting an acyclic digraph that defines the structure of a complex system into a class of cyclically equivalent vertices by adding several additional edges to the digraph. This addition of the digraph makes it possible to introduce negative feedbacks and, consequently, to stabilize the functioning of the complex system under consideration and so to increase its reliability.To do this, the original digraph is transformed into a bipartite undirected graph, in which only the input and output vertices and the edges between them remain. In the constructed bipartite undirected graph, we search for the minimal edge cover and restore the orientation of the edges in it. Next, we construct an algorithm for adding new edges, based on the search for Hamiltonian (or Eulerian) paths and turning the minimum edge cover into a class of cyclically equivalent vertices. The minimal number of edges to be added is not larger than the number of edges in the minimum edge cover. [ABSTRACT FROM AUTHOR]

A method has been developed for finding the shortest Hamiltonian path in an arbitrary graph based on the rank approach, which provides high efficiency and a significant reduction in the error in solving the problem of organizing the process of managing multiple transactions and queries when they are implemented in network databases. In many cases, existing solutions do not provide the necessary results in terms of access time and accuracy of the found solution. Using the developed method allows minimizing the idle time of computing devices, reducing the volume and time of data transfer from one device to another, increases overall scalability, minimizes data access time, etc. An important advantage of the proposed method is to reduce the number of elementary operations and the number of vectors being processed the queue of the operations of the request, which leads to a significant reduction in time to implement the procedures for the formation of echer di operations in the requests. Methods of graph theory were used in this paper. The effectiveness of the task solution was evaluated using a systems approach, system analysis and the theory of operations research. Processing of experimental data obtained during the work was carried out in accordance with the provisions of mathematical statistics.

The foundation of information society is computer interconnection network, and the key of information exchange is communication algorithm. Finding interconnection networks with simple routing algorithm and high fault-tolerant performance is the premise of realizing various communication algorithms and protocols. Nowadays, people can build complex interconnection networks by using very large scale integration (VLSI) technology. Locally exchanged twisted cubes, denoted by (s + t + 1)-dimensional LeTQs,t, which combines the merits of the exchanged hypercube and the locally twisted cube. It has been proved that the LeTQs,t has many excellent properties for interconnection networks, such as fewer edges, lower overhead and smaller diameter. Embeddability is an important indicator to measure the performance of interconnection networks. We mainly study the fault tolerant Hamiltonian properties of a faulty locally exchanged twisted cube, LeTQs,t − (fv + fe), with faulty vertices fv and faulty edges fe. Firstly, we prove that an LeTQs,t can tolerate up to s − 1 faulty vertices and edges when embedding a Hamiltonian cycle, for s ⩾ 2, t ⩾ 3, and s ⩽ t. Furthermore, we also prove another result that there is a Hamiltonian path between any two distinct fault-free vertices in a faulty LeTQs,t with up to (s − 2) faulty vertices and edges. That is, we show that LeTQs,t is (s − 1)-Hamiltonian and (s − 2)-Hamiltonian-connected. The results are proved to be optimal in this paper with at most (s − 1)-fault-tolerant Hamiltonicity and (s − 2) fault-tolerant Hamiltonian connectivity of LeTQs,t. [ABSTRACT FROM AUTHOR]

Phylogenetic networks are a generalization of phylogenetic trees allowing for the representation of non-treelike evolutionary events such as hybridization. Typically, such networks have been analyzed based on their 'level', i.e. based on the complexity of their 2-edge-connected components. However, recently the question of how 'treelike' a phylogenetic network is has become the center of attention in various studies. This led to the introduction of tree-based networks , i.e. networks that can be constructed from a phylogenetic tree, called the base tree , by adding additional edges. While the concept of tree-basedness was originally introduced for rooted phylogenetic networks, it has recently also been considered for unrooted networks. In the present study, we compare and contrast findings obtained for unrooted binary tree-based networks to unrooted non-binary networks. In particular, while it is known that up to level 4 all unrooted binary networks are tree-based, we show that in the case of non-binary networks, this result only holds up to level 3. [ABSTRACT FROM AUTHOR]

In this paper there are presented fuzzy numbers, ELECTRE II method, and graphs theory notions which are used to develop an F# application to rank alternatives in multi-criteria decision-making problems. A usage example is shown in Section 8. The source code of the application can be found here. [ABSTRACT FROM AUTHOR]

Let D = (V,A) be a digraph; if there is at least one arc between every pair of distinct vertices of D, then D is a semicomplete digraph. A digraph D is locally semicomplete if for every vertex x, the out-neighbours of x induce a semicomplete digraph and the in-neighbours of x induce a semicomplete digraph. A locally semicomplete digraph without 2-cycle is a local tournament. In 2012, Bang-Jensen and Huang [J. Combin Theory Ser. B 102 (2012) 701–714] concluded that every 2-arc-strong locally semicomplete digraph which is not the second power of an even cycle has two arc-disjoint strong spanning subdigraphs, and proposed the conjecture that every 3-strong local tournament has two arc-disjoint Hamiltonian cycles. According to Bang-Jensen, Guo, Gutin and Volkmann, locally semicomplete digraphs have three subclasses: the round decomposable; the non-round decomposable which are not semicomplete; the non-round decomposable which are semicomplete. In this paper, we prove that every 3-strong round decomposable locally semicomplete digraph has two arc-disjoint Hamiltonian cycles, which implies that the conjecture holds for the round decomposable local tournaments. Also, we characterize the 2-strong round decomposable local tournaments each of which contains a Hamiltonian path P and a Hamiltonian cycle arc-disjoint from P.