graph

To date, the feasibility of constructing a complete graph invariant in polynomial time remains uncertain. Therefore, developing fast algorithms for checking non-isomorphism, including heuristic ones, is crucial. Successful implementation of these heuristics involves modifying existing graph invariants and creating new ones, both of which are still pertinent. Many existing invariants enable the distinction of a large number of graphs in real time.This paper introduces an invariant specifically for tournaments, a type of directed graph. Tournaments are interesting because the number of different tournaments, given a fixed order of vertices, matches the number of undirected graphs with the same fixed order. The proposed invariant considers all possible tournaments formed by subsets of vertices from the given digraph with the same set of arcs. For each subset tournament, standard places are calculated and summed to determine the final vertex points, which constitute the new invariant.Our calculations reveal that the new invariant differs from the most natural tournament invariant, which assigns points to each participant. Initial computational experiments show that the smallest pair correlation between sequences representing these two invariants is observed at dimension 15.

Topological indices of graphs are numerical descriptors that determine the relationship between the properties of  molecules and their structures. In this paper, we introduce three novel vertex degree-based topological indices that show a good correlation with the Sombor index. We have also derived bounds for them, identified the relationship between them and other topological indices, and finally examined their ability to predict some physico-chemical properties of octane isomers.

In this note, we show that automata theory is a suitable tool for analyzing monopoly-forcing processes. Also, we present the notion of mono-forcing automata by using the monopoly-forcing set for graphs. Moreover, we prove that mono-forcing automata accept more languages than zero-forcing finite automata also, we show that all results in zero-forcing finite automata for complete graphs are established for mono-forcing automata. We examine and deliberate on the language associated with mono-forcing automata for certain specified graphs. Also, we present the style of words that can be recognized with mono-forcing automata. Additionally, we delineate the types of words identifiable by mono-forcing automata. We also describe the configuration of graphs from which mono-forcing automata emerge, generating  specific languages. Several examples are provided to elucidate these concepts.

Suppose that G is a connected graph constructed from pairwise disjoint connected graphs G1,... ,Gt by selecting a vertex of G1, a vertex of G2, and identifying these two vertices. Then continue in this manner inductively. The graphs G1,... ,Gk are the primary subgraphs of G. Some particular cases of these graphs are important in chemistry which we consider them in this paper and study their elliptic Sombor index.

Assume we have a set of k colors and to each vertex of a graph G we assign an arbitry of these colors. If we require that each vertex to set is assigned has in its closed neighborhood all k colors, then this is called the generalized k-rainbow dominating function of a graph G. The corresponding γgkr, which is the minimum sum of numbers of assigned colores over all vertices of G, is called the gk-rainbow domination number of G. In this paper we present a linear algorithms for determining a minimum generalized 2-rainbow dominating set of a tree and on GP(n,2).

Let $R$ be a commutative semiring and $I$ be a $k$-ideal of $R$. In this paper, we introduce the $k$-ideal-based graph of $R$, denoted by $\Gamma_{I^{*}}(R)$. The basic properties and possible structures of the graph are studied.

The main aim of the paper is to give the crossing number of the join product $G^\ast + D_n$ for the graph $G^\ast$ isomorphic to 4-regular graph on six vertices except for two distinct edges with no common vertex such that two remaining vertices are still adjacent, and where $D_n$ consists of $n$ isolated vertices. The proofs are done with possibility of an existence of a separating cycle in some particular drawing of the investigated graph $G^\ast$ and also with the help of well-known exact values for crossing numbers of join products of two subgraphs $H_k$ of $G^\ast$ with discrete graphs.

Transit functions are introduced to study betweenness, intervals and convexity in an axiomatic setup on graphs and other discrete structures. Prime example of a transit function on graphs is the well studied interval function of a connected graph. In this paper, we study the Cycle transit function $mathcal{C}( u,v)$ on graphs which is a transit function derived from the interval function. We study the betweenness properties and also characterize graphs in which the cycle transit function coincides with the interval function. We also characterize graphs where $|mathcal{C}( u,v)cap mathcal{C}( v,w) cap mathcal{C}( u,w)|le 1$ as an analogue of median graphs.

Many abilities of Monte Carlo simulation methods have led to their increasing use in solving various reliability problems of structures. These methods are based on generating random samples in order to simulate events and estimate their results. Achieving certain accuracy requires a significant number of simulation operations. Acceptable accuracies can be achieved with a smaller number of samples by adopting different approaches. In this article, for the first time, symmetric structures are analyzed using the theory of graphs and canonical forms, the frequency of the structures is calculated, and their reliability is also checked using these theories. Also, the study and investigation of the calculation of frequencies and eigenvectors corresponding to symmetric structural models from the point of view of the decomposition of the stiffness matrix in probabilistic reliability analysis, which we will achieve this goal by using the proposed theories. In this article, in addition to obtaining all canonical forms, the relationship between all canonical forms is obtained. Finally, a new Rayleigh-based theory called the proposed improved Rayleigh theory is presented, which is used to extract the natural frequencies of structures. Also, in this research, several samples of different frames and structures were presented using the proposed method and finally, numerical results were presented and the solution of the three-story frame with 24 degrees of freedom was presented. It can be seen from the results that the proposed method has a much higher speed and accuracy than the Monte Carlo method.

The Sombor index of the graph $G$ is a degree based topological index, defined as $SO = sum_{uv in mathbf E(G)}sqrt{d_u^2+d_v^2}$, where $d_u$ is the degree of the vertex $u$, and $mathbf E(G)$ is the edge set of $G$. Bounds on $SO$ are established in terms of graph energy, size of minimum vertex cover, matching number, and induced matching number.

The study of hyperstructures derived from particular mathematical objects is very important and interesting. Graph theory has been established as a fundamental and important tool for solving practical problems in other branches of mathematics. This paper can be considered as one of the connections between hyperstructures and graph theory. In this way, by using the dominating set notion of a graph, we define a hyperoperation on verticals of it and study its properties and then we construct a hypergroup based on this hyperoperation. This hypergroup is presented for some classes of graphs.

The inherent feature of real-world data is uncertainty. If data is generated in valid experiments or standard collections, probability theory or fuzzy theory is a powerful tool for analyzing them. But data is not always reliable, especially when it is not possible to perform a reliable test or data collection multiple times. In this situations, referring to the beliefs of experts in the field in question is an alternative approach and uncertainty theory is a tool by which the beliefs of experts can be mathematically incorporated into the problem-solving structure. In this paper, we investigate the finding minimum weighted maximal matching with uncertain weights. For this purpose, we offer two methods. In the first method, by introducing the concept of chance constraint, we obtain model with definite coefficients. The second method is based on the concept of uncertain expected value. Finally, a numerical example for these two methods is presented.

Let G be a graph of order n and with the vertex set {v_1,v_2,…,v_n } and the edge set E(G). The adjancency matrix of G is an n×n matrix A(G) whose (i,j)-entry is 1 if v_i is adjacent to v_j and 0, otherwise. Assume that D(G) is the n×n diagonal matrix whose (i,i)-entry is the degree of v_i. The matrices L(G) = D(G) - A(G) and Q(G) = D(G) + A(G) are called the Laplacian matrix and signless Laplacian matrix of G, respectively. The signelss Laplacian eigenvalues of a graph are the roots of characteristic polynomial of the signless Laplacian matrix of it. In this paper, we obtained signless Laplacian spectrum of some special subgraphs of complete graph and then estimated some bounds for signless Laplacian Energy of some graphs.

Assume a large microscopic internal bonding chemical structure of a substance designed like a Petersen graph where electrons are the vertices and edges representing the bonding energy levels in between them. For large structures, it is difficult to find out the average level of bonding energy between any pair of electron-proton microscopic structures. For a chemical scientist, it is a difficulty and a challenge both to find out what is the average amount of energy bounded between any subsequent pair of electron-proton bi-valent bond, trivalent bond, or tetravalent bond. This paper presents a sample-based estimation methodology for estimating the bonding energy mean value. A node-sampling procedure is proposed whose bias, mean-squared errors and other properties are derived. Results are supported by empirical studies. Findings are compared with particular cases and confidence intervals are used as a basic tool of comparison for robustness purposes.

In recent years several notions of discrete homotopy for graphs have been introduced, including a notion of ×-homotopy due to Dochtermann. In this paper, we define a ×-homotopy fundamental groupoid for graphs, and prove that it is a functorial ×-homotopy invariant for finite graphs. We also introduce tools to compute this fundamental groupoid, including a van Kampen theorem. We conclude with a comparison with previous definitions along these lines, including those built on polyhedral complexes of graph morphisms.

The current study aims to establish a connection between graphs and automata theory, which apparently demonstrate different mathematical structures. Through searching out some properties of one of these structures, we try to find some new properties of the other structure as well. This will result in obtaining some unknown properties. At first, a novel automaton called zero-forcing (Z-F) finite automata is defined according to the notion of a zero-forcing set of a graph. It is shown that for a given graph and for some zero forcing sets, various Z-F-finite automata will be obtained. In addition, the language and the closure properties of Z-F-finite automata, in particular; union, connection, and serial connection are studied. Moreover, considering some properties of graphs such as the closed trail, connected and complete; some new features for Z-F-finite automata are presented. Further, it is shown that there is not any finite graph such that f be a part of the language of its Z-F-finite automata. Actually, it is proved that for every given graph, the Z-F-finite automata of it does not show any closed trail containing all edges for every zero forcing set, but if the graph G has been a closed trail containing all edges, then the Z-F-finite automata of it has a weak closed trail containing all edges. Some examples are also given to clarify these new notions.

In 1972, within a study of the structure-dependency of total π-electron energy (E), it was shown that E depends on the sum of squares of the vertex degrees of the molecular graph (later named first Zagreb index), and thus provides a measure of the branching of the carbon-atom skeleton. Topological indices are found to be very useful in chemistry, biochemistry and nanotechnology in isomer discrimination, structure–property relationship, structure-activity relationship and pharmaceutical drug design. In chemical graph theory, a topological index is a number related to a graph which is structurally invariant. One of the oldest most popular and extremely studied topological indices are well–known Zagreb indices. In a (molecular) graph G, the Zagreb topological index is equal to the sum of squares of the degrees of vertices of G and the Zagreb coindex is defined as the sum of a graph’s vertex degrees which is not adjacent. In this paper, we obtain the Zagreb coindex of four operations on graphs.

The line graph of the graph $Gamma$ denoted by $L(Gamma)$ is a graph with a vertex set consists of the sets of edges of $Gamma$ and two vertices are adjacent in $L(Gamma)$ if they are incident in $Gamma$. In this article, we discuss and determine the effect of operations on the line graphs of simple graphs.