Search

This work aims to characterize a new class of automaton with input as multisets. First, we introduce two finite monoids through different congruence relations on multiset associated with lattice-valued multiset finite automata and show that they are isomorphic to each other. Next, we present the quotient structure of lattice-valued multiset finite automata by defining an admissible relation on the set of states of a given lattice-valued multiset finite automata. Then we show that there is an isomorphism between lattice-valued multiset finite automata and the quotient structure of another lattice-valued multiset finite automata. Finally, we introduce the concept of reachability, observability (coreachability), and response maps of lattice-valued multiset finite recognizer. Interestingly, we show that the lattice-valued response map of a lattice-valued multiset finite recognizer leads us to provide a characterization of a lattice-valued multiset regular language.

Fuzzy mixed graph (FMG) can be used to model some graphical intercommunication network systems if there are many directed and undirected relations between some vertices. In inverse fuzzy graph, the membership value of edges are greater than or equal to the minimum of the membership value of the corresponding vertices. In inverse fuzzy mixed graph (IFMG), directed and undirected relations exist between some vertices and it can be used to analyze many graphical problems of real life such that the membership values of edges are greater than or equal to the minimum of the membership value of the corresponding pair of vertices. In this article, the concept of IFMG is introduced first with some of its properties. Then some isomorphic properties are studied and complement of IFMG is given. Different types of operations like union, intersection, product and join between two IFMGs are defined and investigated some of their related results. An algorithm of the proposed method is executed to identify some vertices. An application is depicted using the concept IFMG to examine the order of vertices in a social network group according to communication gaps.

A vague graph is a generalized structure of a fuzzy graph that gives more precision, flexibility and compatibility to a system when compared with systems that are designed using fuzzy graphs. In this paper, the new concepts of (totally) irregular, strongly (totally) irregular, highly totally irregular, neighborly totally irregular, edge-irregular of vague graphs are introduced and generalized, and some properties and related results are investigated. Then, we present the concepts of homomorphism, weak isomorphism, co-weak isomorphism and isomorphism of irregular vague graphs and some results on (total) domination number, (total) 2-domination number, (total) cobondage number and (total) 2-cobondage number. Finally, one of their applications related to location map of Fire Stations and Emergency Medical centers in urban regions of ​​a metropolis is presented.

In this study, the embedding of picture fuzzy graphs on the surface of spheres is introduced. The picture fuzzy genus graph with its genus value and strong (weak) picture fuzzy genus graphs are defined. Some important properties of picture fuzzy genus graphs are discussed. A relation between genus value and degree of planarity of picture fuzzy graph is established. The isomorphism properties of picture fuzzy genus graphs are studied. The Euler polyhedral equation in terms of genus value is established here. Finally, two real-life applications of picture fuzzy genus graph in traffic problem on road network and electronic circuit design on planar sheet are exhibited.

Structural Synthesis and Analysis plays a major role in identifying the Isomorphism and Symmetry of a Planetary Gear Train (PGT). In synthesis process, detection of isomorphism in PGTs with given number of links and Degree of Freedom (DOF) is essential. One gear pair and one turning pair will be added to the existing link to generate next level PGT. One isomorphic PGT is selected at random to generate higher link PGTs. Graph theory and matrix methods are used by different kinematicians to identify the symmetry and isomorphism in PGTs. Every method has its own merits and demerits. In this paper a comparison was made between the Hamming number technique and Modified Path Matrix (MPM) approach. For easy analysis, PGTs are converted in to graphs and matrices are extracted from these graphs. In this paper isomorphism is checked by using Adjacency matrix and Modified path Matrix. 4-link and 6-link PGTs were considered for analysis in both the methods and compared the results. It is observed that Hamming Number approach is simple and feasible method among the two to identify the symmetry and isomorphism in PGTs.

We study the probabilistic convergence between the mapper graph and the Reeb graph of a topological space $${\mathbb {X}}$$ X equipped with a continuous function $$f: {\mathbb {X}}\rightarrow \mathbb {R}$$ f : X → R . We first give a categorification of the mapper graph and the Reeb graph by interpreting them in terms of cosheaves and stratified covers of the real line $$\mathbb {R}$$ R . We then introduce a variant of the classic mapper graph of Singh et al. (in: Eurographics symposium on point-based graphics, 2007), referred to as the enhanced mapper graph, and demonstrate that such a construction approximates the Reeb graph of $$({\mathbb {X}}, f)$$ ( X , f ) when it is applied to points randomly sampled from a probability density function concentrated on $$({\mathbb {X}}, f)$$ ( X , f ) . Our techniques are based on the interleaving distance of constructible cosheaves and topological estimation via kernel density estimates. Following Munch and Wang (In: 32nd international symposium on computational geometry, volume 51 of Leibniz international proceedings in informatics (LIPIcs), Dagstuhl, Germany, pp 53:1–53:16, 2016), we first show that the mapper graph of $$({\mathbb {X}}, f)$$ ( X , f ) , a constructible $$\mathbb {R}$$ R -space (with a fixed open cover), approximates the Reeb graph of the same space. We then construct an isomorphism between the mapper of $$({\mathbb {X}},f)$$ ( X , f ) to the mapper of a super-level set of a probability density function concentrated on $$({\mathbb {X}}, f)$$ ( X , f ) . Finally, building on the approach of Bobrowski et al. (Bernoulli 23(1):288–328, 2017b), we show that, with high probability, we can recover the mapper of the super-level set given a sufficiently large sample. Our work is the first to consider the mapper construction using the theory of cosheaves in a probabilistic setting. It is part of an ongoing effort to combine sheaf theory, probability, and statistics, to support topological data analysis with random data.

Two fractional factorial designs are called isomorphic if one can be obtained from the other by relabeling the factors, reordering the runs and switching the levels of factors. Given a set of all o...

On-line social networks, such as in Facebook and Twitter, are often studied from the perspective of friendship ties between agents in the network. Adversarial ties, however, also play an important role in the structure and function of social networks, but are often hidden. Underlying generative mechanisms of social networks are predicted by structural balance theory, which postulates that triads of agents, prefer to be transitive, where friends of friends are more likely friends, or anti-transitive, where adversaries of adversaries become friends. The previously proposed Iterated Local Transitivity (ILT) and Iterated Local Anti-Transitivity (ILAT) models incorporated transitivity and anti-transitivity, respectively, as evolutionary mechanisms. These models resulted in graphs with many observable properties of social networks, such as low diameter, high clustering, and densification. We propose a new, generative model, referred to as the Iterated Local Model (ILM) for social networks synthesizing both transitive and anti-transitive triads over time. In ILM, we are given a countably infinite binary sequence as input, and that sequence determines whether we apply a transitive or an anti-transitive step. The resulting model exhibits many properties of complex networks observed in the ILT and ILAT models. In particular, for any input binary sequence, we show that asymptotically the model generates finite graphs that densify, have clustering coefficient bounded away from 0, have diameter at most 3, and exhibit bad spectral expansion. We also give a thorough analysis of the chromatic number, domination number, Hamiltonicity, and isomorphism types of induced subgraphs of ILM graphs.

The Burnside ring $$\mathcal {B}(G)$$ of a finite group G, a classical tool in the representation theory of finite groups, is studied from the point of view of computational algebra. In the first part (cf. Kreuzer and Patil, Beitr Algebra Geom 58:427–452, 2017) we examined the ring theoretic properties of $$\mathcal {B}(G)$$ using the methods of computer algebra. In this part we shift our focus to important maps between two Burnside rings and make several well-known maps of representation theory explicitly computable. The inputs of all our algorithms are the tables of marks of the two groups, and the outputs are matrices of integers representing the maps via their image in the ghost ring. All algorithms have been implemented in the computer algebra system ApCoCoA and are illustrated by applying them to explicit examples. Especially, we study the restriction and induction maps, the projection and inflation maps, the conjugation isomorphism, and the Frobenius-Wielandt homomorphism.

The graph theory is being used for representation in networks and chemical atomic structures very frequently. However, these days, uncertainties are imposed on such networks. Isomorphism in generalized fuzzy graphs has been introduced here to capture the similarity of uncertainties in different networks. Homomorphism, weak isomorphism, co-weak isomorphism and nearly isomorphism are defined with examples. Also, an application of image visualization is described.

It is known that every digital covering map p:(E,k) ? (B,?) has the unique path lifting property. In this paper, we show that its inverse is true when the continuous surjective map p has no conciliator point. Also, we prove that a digital (k,?)-continuous surjection p:(E,k)? (B,?) is a digital covering map if and only if it is a local isomorphism, when all digital spaces are connected. Moreover, we find out a loop criterion for a digital covering map to be a radius n covering map.

In this paper, we concentrate on one algebraic-based quasi-cyclic low-density parity-check (QC-LDPC) code constructed from two subsets of a finite field and generalize it to propose a class of variable-rate QC-LDPC (VR-QC-LDPC) codes, whose parity-check matrices are nested horizontally and have constant number of rows. Thus the proposed codes are significant at least in terms of storage complexity and can be simply implemented. The constructed codes also inherit the original algebraic-based QC-LDPC codes and their exponent matrices can be obtained from two subsets of the given finite field. We hereby analyze the structural properties from the isomorphism perspective, and present some rules to significantly prune the size of search space and determine the non-isomorphic exponent matrices. By distinguishing the smaller quantities of non-isomorphic matrices with cycle property metric, we can easily construct a series of nested exponent matrices with better cycle distributions and obtain the VR-QC-LDPC codes. Numerical results demonstrate that the constructed codes have better iterative decoding performance within a range of code rates and decoding iterations.

We give an overview of recent advances on the graph isomorphism problem. Our main focus will be on Babai's quasi-polynomial time isomorphism test and subsequent developments that led to the design of isomorphism algorithms with a quasi-polynomial parameterized running time of the from $n^{\text{polylog}(k)}$, where $k$ is a graph parameter such as the maximum degree. A second focus will be the combinatorial Weisfeiler-Leman algorithm.

Гиперграфическими автоматами называются автоматы, у которых множества состояний и выходных символов наделены структурами гиперграфов, сохраняющимися функциями переходов и выходными функциями. Универсальные притягивающие объекты в категории таких автоматов называются универсальными гиперграфическими автоматами. Для таких автоматов полугруппы входных символов являются производными алгебрами отображений, свойства которых взаимосвязаны со свойствами алгебраических структур данных автоматов. Это позволяет изучать универсальные гиперграфические автоматы с помощью исследования их полугрупп входных символов. В работе исследуется проблема абстрактной определяемости таких автоматов их полугруппами входных символов, суть которой заключается в нахождении условий изоморфности полугрупп входных символов универсальных гиперграфических автоматов. Основной результат работы дает решение этой задачи для универсальных гиперграфических автоматов над эффективными гиперграфами с p−определимыми ребрами. Это достаточно широкий и весьма важный класс автоматов, так как он содержит, в частности, автоматы, у которых гиперграфы состояний и выходных символов являются плоскостями (например, проективными или аффинными), а также автоматы, у которых множества состояний и выходных символов разбиваются на классы некоторой эквивалентности без одноэлементных классов. В настоящей работе доказано, что универсальные гиперграфические автоматы над эффективными гиперграфами с p−определимыми ребрами полностью (с точностью до изоморфизма) определяются своими полугруппами входных символов, а также описано строение измоморфизмов таких автоматов.

This paper is devoted to the problem of isomorphism in graphs and proposes a method based on time response of a differential equation. First it is shown that the solution of a differential equation obtaining from a Laplacian matrix can be used as an index and the proof is presented. Then a search algorithm is proposed to find out that the two graphs are isomorphic and there is a permutation matrix describing relations between the graphs. The search algorithm depends on eigenvalues of the Laplacian matrix. For a Laplacian matrix with repeated eigenvalues, Greshgorin theorem is used to convert it to a matrix with non-repeated eigenvalues. This is performed by adding loops to vertices, so that they have separated Greshgorin bands. Then the time response of the differential equation is checked. The proposed method is performed on co-spectral graphs and results are described.

In this paper, we study non-abelian extensions of strict Lie 2-algebras via the cohomology theory. A non-abelian extension of a strict Lie 2-algebra $\g$ by $\frkh$ gives rise to a strict homomorphism from $\g$ to $\SOut(\frkh)$. Conversely, we prove that the obstruction of existence of non-abelian extensions of strict Lie 2-algebras associated to a strict Lie 2-algebra homomorphism from $\g$ to $\SOut(\frkh)$ is given by an element in the third cohomology group. We further prove that the isomorphism classes of non-abelian extensions of strict Lie 2-algebras are classified by the second cohomology group., Comment: 20 pages

We establish a multiplication formula for a tridiagonal standard basis element in the idempotented coideal subalgebras of quantum affine $\mathfrak{gl}_n$ arising from the geometry of affine partial flag varieties of type $C$. We apply this formula to obtain the stabilization algebras $\dot{\mathbf K}^{\mathfrak{c}}_n$, $\dot{\mathbf K}^{\jmath \imath}_{\mathfrak{n}}$, $\dot{\mathbf K}^{\imath \jmath}_{\mathfrak{n}}$ and $\dot{\mathbf K}^{\imath \imath}_{\eta}$, which are idempotented coideal subalgebras of quantum affine $\mathfrak{gl}_n$. The symmetry in the formula leads to an isomorphism of the idempotented coideal subalgebras $\dot{\mathbf K}^{\jmath \imath}_{\mathfrak{n}}$ and $\dot{\mathbf K}^{\imath \jmath}_{\mathfrak{n}}$ with compatible monomial, standard and canonical bases., Comment: 39 pages, fixed some typos, to appear in Journal of Pure and Applied Algebra

We study the algorithmic content of back-and-forth proofs for graphs and homogeneous structures from the perspective of Turing computations in which unbounded search is forbidden. Quite unexpectedly, we discover subtle differences between the back-and-forth proofs for the random graph, the dense linear order of the rationals, and the universal countable abelian p-group. We also prove the primitive recursive analog of the Cantor–Bernstein theorem for graphs which says that if there is a “back” isomorphism and the “forth” isomorphism, then there is a “back-and-forth” isomorphism. We also show that the fully primitive recursive degrees (to be defined) of the dense linear order of the rationals are downwards dense.

We study the graph isomorphism game that arises in quantum information theory from the perspective of bigalois extensions of compact quantum groups. We show that every algebraic quantum isomorphism between a pair of (quantum) graphs $X$ and $Y$ arises as a quotient of a certain measured bigalois extension for the quantum automorphism groups $G_X$ and $G_Y$ of the graphs $X$ and $Y$. In particular, this implies that the quantum groups $G_X$ and $G_Y$ are monoidally equivalent. We also establish a converse to this result, which says that every compact quantum group $G$ monoidally equivalent to $G_X$ is of the form $G_Y$ for a suitably chosen quantum graph $Y$ that is quantum isomorphic to $X$. As an application of these results, we deduce that the $\ast$-algebraic, C$^\ast$-algebraic, and quantum commuting (qc) notions of a quantum isomorphism between classical graphs $X$ and $Y$ all coincide. Using the notion of equivalence for non-local games, we deduce the same result for other synchronous non-local games, including the synBCS game and certain related graph homomorphism games., Comment: 33 pages

Two graphs are co-spectral if their respective adjacency matrices have the same multi-set of eigenvalues. A graph is said to be determined by its spectrum if all graphs that are co-spectral with it are isomorphic to it. We consider these properties in relation to logical definability. We show that any pair of graphs that are elementarily equivalent with respect to the three-variable counting first-order logic $C^3$ are co-spectral, and this is not the case with $C^2$, nor with any number of variables if we exclude counting quantifiers. We also show that the class of graphs that are determined by their spectra is definable in partial fixed-point logic with counting. We relate these properties to other algebraic and combinatorial problems., 17 pages

Srivastava et al. (J Fuzzy Math 2:525–534, 1994) introduced the notion of a fuzzy closure space and studied the category FCS of fuzzy closure spaces and fuzzy closure preserving maps. In this article, we have introduced the Sierpinski fuzzy closure space and proved that it is a Sierpinski object in the category FCS. Further, a characterization (up to an isomorphism) of the category FCS is given, with the help of the Sierpinski fuzzy closure space.

$\newcommand{\poly}{_{\operatorname{poly}}^{\bullet}}\newcommand{\td}{(\operatorname{td}_{L/A}^{\nabla})^{\frac{1}{2}}}\newcommand{\cx}[1]{\operatorname{tot}\big(\Gamma(\Lambda^\bullet A^\vee)\otimes_R\mathcal{#1}\poly\big)}\newcommand{\cy}[1]{\mathbb{H}^\bullet_{\operatorname{CE}}(A,\mathcal{#1}\poly)}$Kontsevich's formality theorem states that there exists an $L_\infty$ quasi-isomorphism from the dgla $T\poly(M)$ of polyvector fields on a smooth manifold $M$ to the dgla $D\poly(M)$ of polydifferential operators on $M$, which extends the classical Hochschild--Kostant--Rosenberg map. In this paper, we extend Kontsevich's formality theorem to Lie pairs, a framework which includes a range of diverse geometric contexts such as complex manifolds, foliations, and $\mathfrak{g}$-manifolds. The spaces $\cx{T}$ and $\cx{D}$ associated with a Lie pair $(L,A)$ each carry an $L_\infty$ algebra structure canonical up to $L_\infty$ isomorphism. These two spaces serve as replacements for the spaces of polyvector fields and polydifferential operators, respectively. Their corresponding cohomology groups $\cy{T}$ and $\cy{D}$ admit canonical Gerstenhaber algebra structures. We establish the following formality theorem for Lie pairs: there exists an $L_\infty$ quasi isomorphism from $\cx{T}$ to $\cx{D}$ whose first Taylor coefficient is equal to $\operatorname{hkr}\circ\td$. Here $\td$ acts on $\cx{T}$ by contraction. Furthermore, we prove a Kontsevich--Duflo type theorem for Lie pairs: the Hochschild--Kostant--Rosenberg map twisted by the square root of the Todd class of the Lie pair $(L,A)$ is an isomorphism of Gerstenhaber algebras from $\cy{T}$ to $\cy{D}$. As applications, we establish formality theorems and Kontsevich--Duflo type theorems for complex manifolds, foliations, and $\mathfrak{g}$-manifolds. In the case of complex manifolds, we recover the Kontsevich--Duflo theorem of complex geometry., Comment: 55 pages, several typos corrected, some references added, some minor cosmetic changes in the presentation

The problem of isomorphism checking of two elementary conjunctions of predicate formulas is considered in this work. Such a problem appears while solving some Artificial Intelligence problems, admitting formalization by means of predicate calculus language. The exact definition of the concept of isomorphism of such formulas is given in this paper. However, isomorphic elementary conjunctions of predicate formulas are formulas that, with some substitution of variables instead of their arguments, coincide with the accuracy of the order of writing literals. Problems are described that, when solved, mean the necessity of testing formulas for isomorphism arises. Polynomial equivalence of this problem with the Graph Isomorphism (GI) problem is proved.

A dessin is a 2-cell embedding of a connected 2-coloured bipartite graph into an orientable closed surface. A dessin is regular if its group of colour- and orientation-preserving automorphisms acts regularly on the edges. In this paper we employ group-theoretic method to determine and enumerate the isomorphism classes of regular dessins with complete bipartite underlying graphs of odd prime power order.

Universal hypergraphical automata are universally attracting objects in the category of automata for which the set of states and the set of output symbols are equipped with structures of hypergraphs. It was proved earlier that a wide class of such sort of automata are determined up to isomorphism by their semigroups of input symbols. We investigate the connection between isomorphisms of universal hypergraphical automata and isomorphisms of their components: semigroups of input symbols and hypergraphs of states and output symbols.

We define Deligne-Beilinson cycle maps for Lichtenbaum cohomology $H_L^m(X, \mathbb Z(n))$ and that with compact supports $H_{c,L}^m(X, \mathbb Z(n))$ of an arbitrary complex algebraic variety $X.$ When $(m,n)=(2,1),$ the homological part of our cycle map with compact supports gives a generalization of the Abel-Jacobi theorem and its projection to the Betti cohomology yields that of the Lefschetz theorem on $(1,1)$-cycles for arbitrary complex algebraic varieties. In general degrees $(m,n),$ we show that the Deligne-Beilinson cycle maps are always surjective on torsion and have torsion-free cokernels. If $m \leq 2n,$ the version with compact supports induces an isomorphism on torsion, and so does the one without compact supports if $min \{2m-1, 2 \dim X+1 \} \leq 2n.$ We also characterize the algebraic part of Griffiths's intermediate Jacobians with a universal property.

In this article it is presented that the characteristic semi – group of the direct sum and direct product “G” and “AG” of the asynchronous automatons of the strongly connected and determined analogs of their extensions are isomorphism. Taking into account that the characteristic semi – group determines the ability to process the information then the direct sum and direct product can be consider as realization – the sequence and parallel calculation accordingly. The obtained results mean that this ability doesn’t depend on the sequence and parallel realization (the same number of abstract class of the suitable characteristic semi- groups).

Exploring further the connection between exponentiation on real closed fields and the existence of an integer part modelling strong fragments of arithmetic, we demonstrate that each model of true arithmetic is an integer part of an exponential real closed field that is elementarily equivalent to the real numbers with exponentiation and that each model of Peano arithmetic is an integer part of a real closed field that admits an isomorphism between its ordered additive and its ordered multiplicative group of positive elements. Under the assumption of Schanuel’s Conjecture, we obtain further strengthenings for the last statement.

The bigraph theory, devised by Robin Milner, is a recent mathematical framework for concurrent processes. Its generality is able to subsume many existing process calculi, for example, CCS, CSP, and Petri nets. Further, it provides a uniform proof of bisimilarity, which is a congruence. We present the first canonical string encoding for pure and lean bigraphs by lifting the breadth-first canonical form of rooted unordered trees to a unique representation for bigraphs up to isomorphism (i.e., lean-support equivalence). The encoding’s applicability is limited to atomic alphabets. The time complexity is $$O(n^{2}k\, d \log {d})$$ O ( n 2 k d log d ) , where n is the number of places, d the degree of the place graph and k the maximum arity of a bigraph’s signature. We provide proof of the correctness of our method and also conduct experimental measurements to assess the complexity.

In this study, cluster hypergraphs are introduced to generalize the concept of hypergraphs, where cluster nodes are allowed. Few related terms and properties on cluster hypergraphs are discussed. Some operations, including the Cartesian product, union, intersection, etc., are studied. Different types of matrix representations and isomorphism are also proposed on cluster hypergraphs. The notion of an effective degree for nodes is introduced to capture the group/ cluster effects. At last, the area of applications and future directions with conclusions is deployed.

Isomorphism of polynomials with two secrets (IP2S) problem was proposed by Patarin et al. at Eurocrypt 1996 and the problem is to find two secret linear maps filling in the gap between two polynomial maps over a finite field. At PQC 2020, Santoso proposed a problem originated from IP2S, which is called block isomorphism of polynomials with circulant matrices (BIPC) problem. The BIPC problem is obtained by linearizing IP2S and restricting secret linear maps to linear maps represented by circulant matrices. Using the commutativity of products of circulant matrices, Santoso also proposed an ElGamal-like encryption scheme based on the BIPC problem. In this paper, we give a new security analysis on the ElGamal-like encryption scheme. In particular, we introduce a new attack (called linear stack attack) which finds an equivalent key of the ElGamal-like encryption scheme by using the linearity of the BIPC problem. We see that the attack is a polynomial-time algorithm and can break some 128-bit proposed parameters of the ElGamal-like encryption scheme within 10 h on a standard PC.

Nonlinear feedback shift registers (NFSRs) have been used in many recent stream ciphers. They are generally classified as Fibonacci NFSRs and Galois NFSRs in terms of their implementation configurations. Two NFSRs are said to be isomorphic if their state diagrams are isomorphic, and two NFSRs are equivalent if their sets of output sequences are equal. Equivalent NFSRs must be isomorphic NFSRs, but not the vice versa. Previous work has been done on the isomorphism and equivalence of Fibonacci NFSRs. This paper continues this research for Galois NFSRs. It first gives some characterizations for several kinds of isomorphic Galois NFSRs, which improves and generalizes the previous corresponding results for Fibonacci NFSRs. It then presents some characterizations for two kinds of equivalent Galois NFSRs, helpful to the design of NFSR-based stream ciphers.

A bipartite graph $G=(V,E)$ with $V=V_1\cup V_2$ is biregular if all the vertices of a stable set $V_i$ have the same degree $r_i$ for $i=1,2$. In this paper, we give an improved new Moore bound for an infinite family of such graphs with odd diameter. This problem was introduced in 1983 by Yebra, Fiol, and F\`abrega.\\ Besides, we propose some constructions of bipartite biregular graphs with diameter $d$ and large number of vertices $N(r_1,r_2;d)$, together with their spectra. In some cases of diameters $d=3$, $4$, and $5$, the new graphs attaining the Moore bound are unique up to isomorphism., Comment: 19 pages, 2 figures

Planar graphs play an effective role in many practical applications where the crossing of edges becomes problematic. This paper aims to investigate the complex q-rung orthopair fuzzy (CQROF) planar graphs (CQROFPGs). In a CQROFPG, the nodes and edges are based on complex QROF information that represents the uncertain knowledge in the range of unit circles in terms of complex numbers. The motivation in discussing such a topic is the wide flexibility of QROF information in the expression of uncertain knowledge compared to intuitionistic and Pythagorean fuzzy settings. We discussed the complex QROF graphs (CQROFGs), complex QROF multigraphs (CQROFMGs), and related terms followed by examples. Furthermore, the notion of strength and planarity index (PI) of the CQROFPGs is defined and exemplified followed by a study of strong and weak edges. We further defined the notion of complex QROF face (CQROFF) and complex QROF dual graph (CQROFDG) and exemplified these concepts. A study of isomorphism, coweak and weak isomorphism, is set up, and some results relating to the CQROFPG and isomorphisms are explored using examples. Furthermore, the problem of short circuits that results due to crossing is discussed because of the proposed study where an algorithm based on complex QROF (CQROF) information is presented for reducing the crossing in networks. Some advantages of the projected study over the previous study are observed, and some future study is predicted.

With three pairs of fuzzy sets, intuitionistic fuzzy sets and Pythagorean fuzzy sets, interval-valued intuitionistic fuzzy sets and interval-valued Pythagorean fuzzy sets, dual hesitation fuzzy sets, and dual hesitation Pythagorean fuzzy sets as the research objects, the isomorphic relation between each pair of fuzzy sets is studied from three aspects, such as operational laws, aggregation operators, and ranking methods. Firstly, based on an automorphism on the unit interval, the transformation relationship between intuitionistic fuzzy dual triple (TI, SI, NI) and Pythagorean fuzzy dual triple (TP, SP, NP) is investigated, and the mathematical isomorphism for each pair of fuzzy sets is developed. Subsequently, the isomorphic operations for these three pairs of fuzzy sets are provided, which lays the foundation for the operators’ isomorphism. Secondly, the isomorphic Archimedean aggregation operators of each pairs of fuzzy sets are constructed based on the isomorphic operational laws. Finally, the isomorphism ranking methods are developed by exploring the conversion relationship between the score function and the accuracy function of each pair of fuzzy sets.

We give a geometric interpretation of Broussous-Grabitz embedding types. We fix a central division algebra $D$ of finite index over a non-Archimedean local field $F$ and a positive integer $m$. Further we fix a hereditary order $\mathfrak{a}$ of $\operatorname{M}_m(D)$ and an unramified field extension $E|F$ in $\operatorname{M}_m(D)$ which is embeddable in $D$ and which normalizes $\mathfrak{a}$. Such a pair $(E,\mathfrak{a})$ is called an embedding. The embedding types classify the $\operatorname{GL}_m(D)$-conjugation classes of these embeddings. Such a type is a class of matrices with non-negative integer entries. We give a formula which allows us to recover the embedding type of $(E,\mathfrak{a})$ from the simplicial type of the image of the barycenter of $\mathfrak{a}$ under the canonical isomorphism, from the set of $E^\times$-fixed points of the reduced building of $\operatorname{GL}_m(D)$ to the reduced building of the centralizer of $E^\times$ in $\operatorname{GL}_m(D)$. Conversely the formula allows to calculate the simplicial type up to cyclic permutation of the Coxeter diagram.

We introduce the framework of Deep Weisfeiler Leman algorithms (DeepWL), which allows the design of purely combinatorial graph isomorphism tests that are more powerful than the well-known Weisfeiler-Leman algorithm. We prove that, as an abstract computational model, polynomial time DeepWL-algorithms have exactly the same expressiveness as the logic Choiceless Polynomial Time (with counting) introduced by Blass, Gurevich, and Shelah (Ann. Pure Appl. Logic., 1999) It is a well-known open question whether the existence of a polynomial time graph isomorphism test implies the existence of a polynomial time canonisation algorithm. Our main technical result states that for each class of graphs (satisfying some mild closure condition), if there is a polynomial time DeepWL isomorphism test then there is a polynomial canonisation algorithm for this class. This implies that there is also a logic capturing polynomial time on this class.

A vertex $v \in V(G)$ is called $\lambda$-main if it belongs to a star set $X \subset V(G)$ of the eigenvalue $\lambda$ of a graph $G$ and this eigenvalue is main for the graph obtained from $G$ by deleting all the vertices in $X \setminus \{v\}$; otherwise, $v$ is $\lambda$-non-main. Some results concerning main and non-main vertices of an eigenvalue are deduced. For a main eigenvalue $\lambda$ of a graph $G$, we introduce the minimum and maximum number of $\lambda$-main vertices in some $\lambda$-star set of $G$ as new graph invariant parameters. The determination of these parameters is formulated as a combinatorial optimization problem based on a simplex-like approach. Using these and some related parameters we develop new spectral tools that can be used in the research of the isomorphism problem. Examples of graphs for which the maximum number of $\lambda$-main vertices coincides with the cardinality of a $\lambda$-star set are provided., Comment: 21 pages, 4 figures. To be published in Discrete Mathematics

This paper includes the analysis and the results of the study of the possibility to utilize the unevenness coefficients of the use of individual graph edges for the assessment of the isomorphism of ICT networks described with Reference Graphs. These parameters are used to confirm or reject the presence of the isomorphism of the analyzed graphs. In the first part of the paper the terms chord graph, Reference Graph and isomorphism of graphs are defined. Further, the analysis of the possibility to utilize the unevenness coefficients for the evaluation of the isomorphism of RG structures is described. The term unevenness coefficient is defined and the method of their calculation is discussed. The examples of the application of the aforementioned coefficients for the assessment of the isomorphism of networks modelled with RG graphs are given.

We prove that the group C p 4 × C q is a DCI-group for distinct primes p and q, that is, two Cayley digraphs over C p 4 × C q are isomorphic if and only if their connection sets are conjugate by a group automorphism.

Every countable structure has a sentence of the infinitary logic $\mathcal {L}_{\omega _1 \omega }$ which characterizes that structure up to isomorphism among countable structures. Such a sentence is called a Scott sentence, and can be thought of as a description of the structure. The least complexity of a Scott sentence for a structure can be thought of as a measurement of the complexity of describing the structure. We begin with an introduction to the area, with short and simple proofs where possible, followed by a survey of recent advances.

In this chapter, we discuss the concept of irregularity in bipolar fuzzy graphs and present isomorphism properties of regular, m-totally regular, neighborly irregular, totally irregular, highly irregular, and neighborly totally irregular bipolar fuzzy graphs. We present certain characterizations under which, regular and totally regular bipolar fuzzy graphs, and highly irregular and neighborly irregular bipolar fuzzy graphs are equivalent. We discuss certain formulae of order and size of \(m-\)totally regular bipolar fuzzy graphs. We study the concept of bipolar fuzzy line graphs, and establish a necessary and sufficient condition for a bipolar fuzzy graph to be isomorphic to its corresponding bipolar fuzzy line graph.

In this chapter, we first review the notion of bipolar fuzzy sets and present several basic concepts concerning bipolar fuzzy graphs and bipolar fuzzy digraphs. We discuss different methods of construction of bipolar fuzzy graphs and their isomorphism properties. We describe certain types of bipolar fuzzy graphs, bipolar fuzzy walk, bipolar fuzzy bridge, strength of connectedness, weak and strong bipolar fuzzy edges. We establish the relations on bipolar fuzzy graphs, complement of bipolar fuzzy graphs, and crisp graphs with different operations, \(\alpha -\)cuts and \((\alpha ,\beta )-\)cuts. We also study certain operations and properties of complex bipolar fuzzy graphs. Moreover, with the help of composition of bipolar fuzzy relations, connectivity, and weighted matrices, we study the importance of bipolar fuzzy digraphs with a number of real-world problems. This chapter is basically adapted from [1, 2, 3, 45, 46, 51].

Minimization of deterministic automata on finite words results in a {\em canonical\/} automaton. For deterministic automata on infinite words, no canonical minimal automaton exists, and a language may have different minimal deterministic B\"uchi (DBW) or co-B\"uchi (DCW) automata. In recent years, researchers have studied {\em good-for-games\/} (GFG) automata -- nondeterministic automata that can resolve their nondeterministic choices in a way that only depends on the past. Several applications of automata in formal methods, most notably synthesis, that are traditionally based on deterministic automata, can instead be based on GFG automata. The {\em minimization\/} problem for DBW and DCW is NP-complete, and it stays NP-complete for GFG B\"uchi and co-B\"uchi automata. On the other hand, minimization of GFG co-B\"uchi automata with {\em transition-based\/} acceptance (GFG-tNCWs) can be solved in polynomial time. In these automata, acceptance is defined by a set $\alpha$ of transitions, and a run is accepting if it traverses transitions in $\alpha$ only finitely often. This raises the question of canonicity of minimal deterministic and GFG automata with transition-based acceptance. In this paper we study this problem. We start with GFG-tNCWs and show that the safe components (that is, these obtained by restricting the transitions to these not in $\alpha$) of all minimal GFG-tNCWs are isomorphic, and that by saturating the automaton with transitions in $\alpha$ we get isomorphism among all minimal GFG-tNCWs. Thus, a canonical form for minimal GFG-tNCWs can be obtained in polynomial time. We continue to DCWs with transition-based acceptance (tDCWs), and their dual tDBWs. We show that here, while no canonical form for minimal automata exists, restricting attention to the safe components is useful, and implies that the only minimal tDCWs that have no canonical form are these for which the transition to the GFG model results in strictly smaller automaton, which do have a canonical minimal form., Comment: In Proceedings GandALF 2020, arXiv:2009.09360

The topological distance is to measure the structural difference between two graphs in a metric space. Graphs are ubiquitous, and topological measurements over graphs arise in diverse areas, including, e.g. COVID-19 structural analysis, DNA/RNA alignment, discovering the Isomers, checking the code plagiarism. Unfortunately, popular distance scores used in these applications, that scale over large graphs, are not metrics, and the computation usually becomes NP-hard. While, fuzzy measurement is an uncertain representation to apply for a polynomial-time solution for undirected multigraph isomorphism. But the graph isomorphism problem is to determine two finite graphs that are isomorphic, which is not known with a polynomial-time solution. This paper solves the undirected multigraph isomorphism problem with an algorithmic approach as NP=P and proposes a polynomial-time solution to check if two undirected multigraphs are isomorphic or not. Based on the solution, we define a new fuzzy measurement based on graph isomorphism for topological distance/structural similarity between two graphs. Thus, this paper proposed a fuzzy measure of the topological distance between two undirected multigraphs. If two graphs are isomorphic, the topological distance is 0; if not, we will calculate the Euclidean distance among eight extracted features and provide the fuzzy distance. The fuzzy measurement executes more efficiently and accurately than the current methods.

This paper is mostly a follow up on the work of Etkin and Ordentlich that studied the capacity regions of binary input deterministic interference channels. The only binary input deterministic interference channel whose capacity region is unknown (up to isomorphism) is when one receiver receives the Boolean AND of the two transmitted symbols, and the other receiver obtains the Boolean OR of the two transmitted symbols. Etkin and Ordentlich stated in the paper that they believed that time-division would be the capacity region for this interference channel. In this paper we show that one can achieve rates outside the time-division region.That time-division yields the zero-error capacity region for this setting is known as Simonyi’s sand-glass conjecture, a statement that has received considerable attention in the combinatorics community. Various upper-bounds on the sum-rate of the zeroerror capacity region had been proposed in the combinatorics community. In this paper we evaluate an outer bound to the (traditional notion of) capacity region due to Etkin and Ordentlich and show that this yields, surprisingly, a tighter bound that the best known bound for the sand-glass problem.Finally, we establish the capacity region of the some special classes of binary input interference channels by improving on the outer-bound proposed by Etkin and Ordentlich.

In this research work, the notion of complex Pythagorean fuzzy planar graph (CPFPG), an extension of Pythagorean fuzzy planar graph, is presented to study the planarity. The planarity of these graphs is based on the extended range of degree from real to complex plane with unit circle. Here, the ideas of complex Pythagorean fuzzy multigraphs (CPFMGs), complex Pythagorean fuzzy planar graphs (CPFPGs) and some distinguished aspects of these graphs are presented by inspecting the complex Pythagorean fuzzy planarity value using weak and strong edges. A close relation is established between CPFPGs and dual graphs. Discussion about the non-planarity of graphs and the concepts of co-weak isomorphism, isomorphism and weak isomorphism for CPFPGs are also added. Furthermore, an application based on the proposed idea is presented to illustrate the efficiency of given model. The comparison study is also given to validate the consistency and superiority of our model.

Evolution algebras is a class of non-associative algebras with connections with many mathematical fields. One natural way to define the evolution algebra associated to a given graph is taking into account the adjacencies of the graph. In this review note we discuss recents results about these mathematical structures and we emphasize in some interesting open problems.