Search

A series-parallel graph is a graph that does not contain a complete graph with four vertices as a minor. A new explicit simpler formula for the number of labeled series-parallel biconnected graphs with a given number of vertices is obtained. [ABSTRACT FROM AUTHOR]

A series-parallel graph is a graph that does not contain a complete graph with four vertices as a minor. An explicit formula for the number of labeled series-parallel tricyclic graphs with a given number of vertices is obtained, and the corresponding asymptotics for the number of such graphs with a large number of vertices is found. We prove that under a uniform probability distribution, the probability that the labeled tricyclic graph is a series-parallel graph is asymptotically equal to 13/15. [ABSTRACT FROM AUTHOR]

Cryptography is a pivotal application of graph theory in ensuring secure communication systems. Modern cryptography is deeply rooted in mathematical theory and computer science practices. It is widely recognized that encryption and decryption processes are primarily outcomes of mathematical research. Given the increasing importance of safeguarding secret information or messages from potential intruders, it is imperative to develop effective technical tools for this purpose. These intruders are often well-versed in the latest technological advancements that could breach security. To address this, our study focuses on the efficacious combinatorial technique of graph networks using efficient domination and total magic labeling. The introduction of a graph network based on total magic labeling can significantly influence the network's performance. This research introduces a novel combinatorial method for encrypting and decrypting confidential numbers by leveraging an efficient dominant notion and labeled graph. [ABSTRACT FROM AUTHOR]

A bi-block graph is a connected graph in which all blocks are complete bipartite graphs. Labeled bi-block graphs and bridgeless bi-block graphs are enumerated exactly and asymptotically by the number of vertices. It is proved that almost all labeled connected bi-block graphs have no bridges. In addition, planar bi-block graphs are enumerated, and an asymptotic estimate is found for the number of such graphs. [ABSTRACT FROM AUTHOR]

Advances in computing resources have enabled the processing of vast amounts of data. However, identifying trends in such data remains challenging for humans, especially in fields like medicine and social networks. These challenges make it difficult to process, analyze, and visualize the data. In this context, graph summarization has emerged as an effective framework aiming to facilitate the identification of structure and meaning in data. The problem of graph summarization has been studied in the literature and many approaches for static contexts are proposed to summarize the graph. These approaches provide a compressed version of the graph that removes many details while retaining its essential structure. However, they are computationally prohibitive and do not scale to large graphs in terms of both structure and content. Additionally, there is no framework providing summarization of mixed sources with the goal of creating a dynamic, syntactic, and semantic data summary. In this paper, our key contribution is focused on modeling data graphs, summarizing data from multiple sources using a schema-driven approach, and visualizing the graph summary version according to the needs of each user. We demonstrate this approach through a case study on the use of the E-health domain. [ABSTRACT FROM AUTHOR]

Given a directed graph E and a labeling L, one forms the labeled graph algebra by taking a weakly left-resolving labeled space (E, L, B) and considering a generating family of partial isometries and projections. In this paper, we discuss details in the formulation of the algebras, provide examples, and formulate a process that describes the algebra given the graph and a labelling. [ABSTRACT FROM AUTHOR]

For an additive submonoid M of R ≥ 0 , the weight of a finite M -labeled directed graph is the sum of all of its edge labels, while the content is the product of the labels. Having fixed M and a directed tree E, we prove a general result on the shape of finite, acyclic, M -labeled directed graphs Γ of weight N ∈ M maximizing the sum of the contents of all copies E ⊂ Γ . This specializes to recover a result of Hajac and the author’s on the maximal number of length-k paths in an acyclic directed graph with N edges. It also applies to prove a conjecture by the same authors on the maximal sum of entries of A k for a nilpotent R ≥ 0 -valued square matrix A whose entries add up to N. Finally, we apply the same techniques to obtain the maximal number of stars with α arms in a directed graph with N edges. [ABSTRACT FROM AUTHOR]

Patients with lesions in the posterior cingulate gyrus (PCG), including the retrosplenial cortex (RSC) and posterior cingulate cortex (PCC), cannot navigate in familiar environments, nor draw routes on a 2D map of the familiar environments. This suggests that the topographical knowledge of the environments (i.e., cognitive map) to find the right route to a goal is represented in the PCG, and the patients lack such knowledge. However, theoretical backgrounds in neuronal levels for these symptoms in primates are unclear. Recent behavioral studies suggest that human spatial knowledge is constructed based on a labeled graph that consists of topological connections (edges) between places (nodes), where local metric information, such as distances between nodes (edge weights) and angles between edges (node labels), are incorporated. We hypothesize that the population neural activity in the PCG may represent such knowledge based on a labeled graph to encode routes in both 3D environments and 2D maps. Since no previous data are available to test the hypothesis, we recorded PCG neuronal activity from a monkey during performance of virtual navigation and map drawing-like tasks. The results indicated that most PCG neurons responded differentially to spatial parameters of the environments, including the place, head direction, and reward delivery at specific reward areas. The labeled graph-based analyses of the data suggest that the population activity of the PCG neurons represents the distance traveled, locations, movement direction, and navigation routes in the 3D and 2D virtual environments. These results support the hypothesis and provide a neuronal basis for the labeled graph-based representation of a familiar environment, consistent with PCG functions inferred from the human clinicopathological studies.

We derive an asymptotic formula for the number of labeled connected series-parallel -cyclic graphs of a large order with a fixed number . With a uniform probability distribution, we find the probability that a random labeled connected -vertex -cyclic graph with a fixed as is a series-parallel graph. In addition, we determine the probability that, with a uniform probability distribution, a random labeled connected series-parallel -vertex -cyclic graph with a fixed as is a cactus. [ABSTRACT FROM AUTHOR]

Cryptography is a pivotal application of graph theory in ensuring secure communication systems. Modern cryptography is deeply rooted in mathematical theory and computer science practices. It is widely recognized that encryption and decryption processes are primarily outcomes of mathematical research. Given the increasing importance of safeguarding secret information or messages from potential intruders, it is imperative to develop effective technical tools for this purpose. These intruders are often well-versed in the latest technological advancements that could breach security. To address this, our study focuses on the efficacious combinatorial technique of graph networks using efficient domination and total magic labeling. The introduction of a graph network based on total magic labeling can significantly influence the network’s performance. This research introduces a novel combinatorial method for encrypting and decrypting confidential numbers by leveraging an efficient dominant notion and labeled graph.

The software tools most suitable for visualization of multidimensional graphs are considered. Comparing of the tools by different criteria is presented. The most convenient software for visualization of multidimensional graphs was chosen.

We deduce the asymptotics for the number of labeled connected series-parallel -cyclic graphs with large order and fixed number . We prove that almost all labeled series-parallel -cyclic connected graphs without bridges for fixed are blocks. [ABSTRACT FROM AUTHOR]

We deduce an explicit formula for the number of labeled series-parallel -cyclic -vertex -connected graphs and find the corresponding asymptotics for a large number of vertices and a fixed . Under the uniform probability distribution, an asymptotic formula is obtained for the probability that a random -vertex -cyclic -connected graph with a large number of vertices and a fixed is a series-parallel graph. [ABSTRACT FROM AUTHOR]

We obtain an explicit formula for the number of labeled connected outerplanar k-cyclic n-vertex bridgeless graphs. We find asymptotics for the number of those graphs for a large number of vertices and fixed k. As a consequence, we prove that, for k fixed, almost all labeled connected outerplanar k-cyclic graphs have bridges. [ABSTRACT FROM AUTHOR]

Subgraph and supergraph search methods are promising techniques for the development of new drugs. For example, the chemical structure of favipiravir—an antiviral treatment for influenza—resembles the structure of some components of RNA. Represented as graphs, such compounds are similar to a subgraph of favipiravir. However, the existing supergraph search methods can only discover compounds that match exactly. We propose a novel problem, called similar supergraph search, and design an efficient algorithm to solve it. The problem is to identify all graphs in a database that are similar to any subgraph of a query graph, where similarity is defined as edit distance. Our algorithm represents the set of candidate subgraphs by a code tree, which it uses to efficiently compute edit distance. With a distance threshold of zero, our algorithm is equivalent to an existing efficient algorithm for exact supergraph search. Our experiments show that the computation time increased exponentially as the distance threshold increased, but increased sublinearly with the number of graphs in the database.

Abstract We investigate two Bruhat (partial) orders on graphs with vertices labeled 1 , 2 , ... , n and with a specified degree sequence R , equivalently, symmetric (0 , 1) -matrices with zero trace and a specified row sum vector R (adjacency matrices of such graphs). One is motivated by the classical Bruhat order on permutations while the other one, more restrictive, is defined by a switch of a pair of disjoint edges. In the Bruhat order, one seeks to concentrate the edges of a graph with a given degree sequence among the vertices with smallest labels, thereby producing a minimal graph in this order. We begin with a discussion of graphs whose isomorphism class does not change under a switch. Then we are interested in when the two Bruhat orders are identical. For labeled graphs of regular degree k , we show that the two orders are identical for k ≤ 2 but not for k = 3. [ABSTRACT FROM AUTHOR]

The second Riddell relation relates the generating functions for the number of labeled connected graphs and the number of labeled blocks. We consider the conditions under which this relation is true for a subclass of connected graphs.Under these conditions, the formulas are valid that express the number of graphs from a subclass of labeled connected graphs trough the generating function of their blocks. By way of application, we obtain expressions for the numbers of labeled connected and 2-connected series-parallel graphs. [ABSTRACT FROM AUTHOR]

A k-cyclic graph is a graph with cyclomatic number k. An explicit formula for the number of labeled connected outerplanar k-cyclic graphs with a given number of vertices is obtained. In addition, such graphs with fixed cyclomatic number k and a large number of vertices are asymptotically enumerated. As a consequence, it is found that, for fixed k, almost all labeled connected outerplanar k-cyclic graphs with a large number of vertices are cacti. [ABSTRACT FROM AUTHOR]

A neighborhood total dominating set, abbreviated for NTD-set D, is a vertex set of G such that D is a dominating set with an extra property: the subgraph induced by the open neighborhood of D has no isolated vertex. The neighborhood total domination number, denoted by γnt(G), is the minimum cardinality of a NTD-set in G. In this paper, we prove that NTD problem is NP-complete for bipartite graphs and split graphs. Then we give a linear-time algorithm to determine γnt(T) for a given tree T. Finally, we characterize a constructive property of (γnt,2γ)-trees and provide a constructive characterization for (ρ,γnt)-graphs, where γ and ρ are domination number and packing number for the given graph, respectively. [ABSTRACT FROM AUTHOR]

Topological behavior, such as chaos, irreducibility, and mixing of a one-sided shift of finite type, is well elucidated. Meanwhile, the investigation of multidimensional shifts, for instance, textile systems, is difficult and only a few results have been obtained so far. This paper studies shifts defined on infinite trees, which are called tree-shifts. Infinite trees have a natural structure of one-sided symbolic dynamical systems equipped with multiple shift maps and constitute an intermediate class between one-sided shifts and multidimensional shifts. We have shown not only an irreducible tree-shift of finite type but also a mixing tree-shift that is chaotic in the sense of Devaney. Furthermore, the graph and labeled graph representations of tree-shifts are revealed so that the verification of irreducibility and mixing of a tree-shift is equivalent to determining the irreducibility and mixing of matrices, respectively. This extends the classical results of one-sided symbolic dynamics. A necessary and sufficient condition for the irreducibility and mixing of tree-shifts of finite type is demonstrated. Most important of all, the examination can be done in finite steps with an upper bound. [ABSTRACT FROM AUTHOR]

The concept of labeled stratified graph (LSG) introduces some method of knowledge representation. The inference process developed for this structures uses the paths of the stratified graphs, an order between the elementary arcs of a path and some results of universal algebras. The order is defined by considering a structured path instead of a regular path. The application described in this paper interprets the symbolic elements of a LSG with natural language constructions. In this manner we obtained a mechanism for generation coherent texts in a natural language (for this approach, Romanian). The generation method is based on labeled stratified graph representation and the inference mechanism is guided by the structured paths of these representations.

A labeled graph is a special structure with node identification capability, which is often used in information networks, biological networks, and other fields. The subgraph query is widely used as an important means of graph data analysis. As the size of the labeled graph increases and changes dynamically, users tend to focus on the high-match results that are of interest to them, and they want to take advantage of the relationship and number of results to get the results of the query quickly. For this reason, we consider the individual needs of users and propose a dynamic Top-K interesting subgraph query. This method establishes a novel graph topology feature index (GTSF index) including a node topology feature index (NTF index) and an edge feature index (EF index), which can effectively prune and filter the invalid nodes and edges that do not meet the restricted condition. The multi-factor candidate set filtering strategy is proposed based on the GTSF index, which can be further pruned to obtain fewer candidate sets. Then, we propose a dynamic Top-K interesting subgraph query method based on the idea of the sliding window to realize the dynamic modification of the matching results of the subgraph in the dynamic evolution of the label graph, to ensure real-time and accurate results of the query. In addition, considering the factors, such as frequent Input/Output (I/O) and network communication overheads, the optimization mechanism of the graph changes and an incremental maintenance strategy for the index are proposed to reduce the huge cost of redundant operation and global updates. The experimental results show that the proposed method can effectively deal with a dynamic Top-K interesting subgraph query on a large-scale labeled graph, at the same time the optimization mechanism of graph changes and the incremental maintenance strategy of the index can effectively reduce the maintenance overheads.

A generalized Baumslag-Solitar group ( GBS group) is a finitely generated group G which acts on a tree with all edge and vertex stabilizers infinite cyclic. Every GBS group is the fundamental group π(픸) of some labeled graph 픸. This paper deals with the isomorphism problem for GBS groups, which is the problem of determining whether π(픸) ≅ π(픹) for two given labeled graphs 픸 and 픹. We describe an algorithm that decides this problem for the case where one of the labeled graphs has a sole mobile edge. [ABSTRACT FROM AUTHOR]

The aim of this paper is to establish a connection between modal logics and labeled graphs, which is useful in solving the problem of nondeterminism. Also, we construct a canonical, maximal and consistent model of a labeled graph associated to a transition system. [ABSTRACT FROM AUTHOR]

The paper investigates relationship between algebraic expressions and labeled graphs. We consider directed grid graphs having m rows and n columns. Our intent is to simplify the expressions of these graphs. With that end in view, we describe two algorithms which generate expressions of polynomial sizes for directed grid graphs. [ABSTRACT FROM AUTHOR]

We prove that, for fixed k ≥ 3, the following classes of labeled n-vertex graphs are asymptotically equicardinal: graphs of diameter k, connected graphs of diameter at least k, and (not necessarily connected) graphs with a shortest path of length at least k. An asymptotically exact approximation of the number of such n-vertex graphs is obtained, and an explicit error estimate in the approximation is found. Thus, the estimates are improved for the asymptotic approximation of the number of n-vertex graphs of fixed diameter k earlier obtained by Füredi and Kim. It is shown that almost all graphs of diameter k have a unique pair of diametrical vertices but almost all graphs of diameter 2 have more than one pair of such vertices. [ABSTRACT FROM AUTHOR]

The class of outerplanar graphs is used for testing the average complexity of algorithms on graphs. A random labeled outerplanar graph can be generated by a polynomial algorithm based on the results of an enumeration of such graphs. By a bicyclic ( tricyclic) graph we mean a connected graph with cyclomatic number 2 (respectively, 3). We find explicit formulas for the number of labeled connected outerplanar bicyclic and tricyclic graphs with n vertices and also obtain asymptotics for the number of these graphs for large n. Moreover, we obtain explicit formulas for the number of labeled outerplanar bicyclic and tricyclic n-vertex blocks and deduce the corresponding asymptotics for large n. [ABSTRACT FROM AUTHOR]

We deduce a new formula for the number of labeled connected graphs with given order and number of edges in terms of the block generating function. Applying this formula, we exactly and asymptotically enumerate cacti with given order and cyclomatic number. [ABSTRACT FROM AUTHOR]

Modal logic is an extension of the logic of predicates and propositions which includes operators that express modality. In modal logic we deal with truth and falsehood in different possible worlds, as well as in the real world. In this paper we construct a labeled graph associated to a transition system, as a starting point in analyzing modal logics. We define the concepts of inclusion, isomorphism, "modal equivalence" and equivalence between graphs. [ABSTRACT FROM AUTHOR]

The concept of stratified graph introduces some method of knowledge representation (see [Ţăndăreanu, N., Knowledge representation by labeled stratified graphs, Proc. 8th World Multi-Conference on Systemics, Cybernetics and Informatics, 5 (2004), 345-350; Ţăndăreanu, N., Proving the Existence of Labelled Stratified Graphs, An. Univ. Craiova Ser. Mat. Inform., 27 (2000), 81-92]) The inference process developed for this method uses the paths of the stratified graphs, an order between the elementary arcs of a path and some results of universal algebras. The order is defined by considering a structured path instead of a regular path. In this paper we define the concept of system of knowledge representation as a tuple of the following components: a stratified graph G, a partial algebra Y of real objects, an embedding mapping (an injective mapping that embeds the nodes of G into objects of Y ) and a set of algorithms such that each of them can combine two objects of Y to get some other object of Y. We define also the concept of inference process performed by a system of knowledge processing in which the interpretation of the symbolic elements is defined by means of natural language constructions. In this manner we obtained a mechanism for texts generation in a natural language (for this approach, Romanian). [ABSTRACT FROM AUTHOR]

This paper investigates relationship between algebraic expressions and labeled graphs. We consider rhomboidal non-series-parallel graphs, specifically, a new digraph called a full square rhomboid. Our intent is to simplify the expressions of rhomboidal graphs and eventually find their shortest representations. With that end in view, we describe and compare two decomposition methods for generating expressions of labeled graphs. [ABSTRACT FROM AUTHOR]

Patients with lesions in the posterior cingulate gyrus (PCG), including the retrosplenial cortex (RSC) and posterior cingulate cortex (PCC), cannot navigate in familiar environments, nor draw routes on a 2D map of the familiar environments. This suggests that the topographical knowledge of the environments (i.e., cognitive map) to find the right route to a goal is represented in the PCG, and the patients lack such knowledge. However, theoretical backgrounds in neuronal levels for these symptoms in primates are unclear. Recent behavioral studies suggest that human spatial knowledge is constructed based on a labeled graph that consists of topological connections (edges) between places (nodes), where local metric information, such as distances between nodes (edge weights) and angles between edges (node labels), are incorporated. We hypothesize that the population neural activity in the PCG may represent such knowledge based on a labeled graph to encode routes in both 3D environments and 2D maps. Since no previous data are available to test the hypothesis, we recorded PCG neuronal activity from a monkey during performance of virtual navigation and map drawing-like tasks. The results indicated that most PCG neurons responded differentially to spatial parameters of the environments, including the place, head direction, and reward delivery at specific reward areas. The labeled graph-based analyses of the data suggest that the population activity of the PCG neurons represents the distance traveled, locations, movement direction, and navigation routes in the 3D and 2D virtual environments. These results support the hypothesis and provide a neuronal basis for the labeled graph-based representation of a familiar environment, consistent with PCG functions inferred from the human clinicopathological studies., Competing Interests: Conflict of interest: The authors declare no conflict of interest., (© 2022 the Author(s), licensee AIMS Press.)

The article discusses on how to obtain the closed-form expressions for the number of labeled bi- and tricyclic graphs and the asymptotics of the number of such graphs. It says that the cyclomatic number of any of those graphs is k +1. It mentions that E. F. Dmitriev used other methods in enumerating abeled 2-edge-connected graphs but has not published his results.