Search

In this article, we introduce a new counting polynomial, namely the orbit polynomial. It is well-known that this polynomial has a unique positive zero δ in the interval [0, 1]. The aim of this paper is to study the specific properties of this polynomial and then determine the location of this root for several classes of complex networks to compare with other graphical measures. Additionally, we compare the unique positive zero measure with several well-known centrality graph measures. [ABSTRACT FROM AUTHOR]

This note is intended as a contribution to the study of quantitative measures of graph complexity that use entropy measures based on symmetry. Determining orbit sizes of graph automorphism groups is a key part of such studies. Here we focus on an extreme case where every orbit contains just a single vertex. A permutation of the vertices of a graph G is an automorphism if, and only if, the corresponding permutation matrix commutes with the adjacency matrix of G. This fact establishes a direct connection between the adjacency matrix and the automorphism group. In particular, it is known that if the eigenvalues of the adjacency matrix of G are all distinct, every non-trivial automorphism has order 2. In this note, we add a condition to the case of distinct eigenvalues that makes the graph asymmetric, i.e., reduces the automorphism group to the identity alone. In addition, we prove analogous results for the Google and Laplacian matrices. The condition is used to build an O(n3) algorithm for detecting identity graphs, and examples are given to demonstrate that it is sufficient, but not necessary. [ABSTRACT FROM AUTHOR]

The complete set of 618047 isomers of the alkanes with 4 to 20 carbon atoms has been created. From all isomers the automorphism groups have been calculated and evaluated in terms of size, number of asymmetric carbon atoms, and numeric properties of atom and bond orbits. The presence of a symmetric bond is related to the number of atom and bond orbits. Molecular descriptors based on automorphism data have been studied, including the known symmetry index, an entropy measure and the root of an orbit polynomial. These descriptors are closely related to the presence of symmetric substructures. The prediction performance of QSPR models for three molecular properties of alkanes and using binary substructure descriptors, is improved by adding descriptors based on automorphism data. [ABSTRACT FROM AUTHOR]

This paper demonstrates properties of Hosoya entropy, a quantitative measure of graph complexity based on a decomposition of the vertices linked to partial Hosoya polynomials. Connections between the information content of a graph and Hosoya entropy are established, and the special case of Hosoya entropy of trees is investigated. [ABSTRACT FROM AUTHOR]

The definition of orbit polynomial is based on the size of orbits of a graph which is O G (x) = ∑ i x | O i | , where O 1 , ... , O k are all orbits of graph G. It is a well-known fact that according to Descartes' rule of signs, the new polynomial 1 − O G (x) has a positive root in (0 , 1) , which is unique and it is a relevant measure of the symmetry of a graph. In the current work, several bounds for the unique and positive zero of modified orbit polynomial 1 − O G (x) are investigated. Besides, the relation between the unique positive root of O G in terms of the structure of G is presented. [ABSTRACT FROM AUTHOR]

The size of the orbits or similar vertices of a network provides important information regarding each individual component of the network. In this paper, we investigate the entropy or information content and the symmetry index for several classes of graphs and compare the values of this measure with that of the symmetry index of certain graphs. [ABSTRACT FROM AUTHOR]

If G is a graph and P is a partition of V (G) , then the partition distance of G is the sum of the distances between all pairs of vertices that lie in the same part of P. A colored distance is the dual concept of the partition distance. These notions are motivated by a problem in the facility location network and applied to several well-known distance-based graph invariants. In this paper, we apply an extended cut method to induce the partition and color distances to some subsets of vertices which are not necessary a partition of V (G) . Then, we define a two-dimensional weighted graph and an operator to prove that the induced partition and colored distances of a graph can be obtained from the weighted Wiener index of a two-dimensional weighted quotient graph induced by the transitive closure of the Djoković–Winkler relation as well as by any partition that is coarser. Finally, we utilize our main results to find some upper bounds for the modified Wiener index and the number of orbits of partial cube graphs under the action of automorphism group of graphs. [ABSTRACT FROM AUTHOR]

The orbit polynomial is a new graph counting polynomial which is defined as O G (x) = ∑ i = 1 r x | O i | , where O 1 , ..., O r are all vertex orbits of the graph G. In this article, we investigate the structural properties of the automorphism group of a graph by using several novel counting polynomials. Besides, we explore the orbit polynomial of a graph operation. Indeed, we compare the degeneracy of the orbit polynomial with a new graph polynomial based on both eigenvalues of a graph and the size of orbits. [ABSTRACT FROM AUTHOR]

The Graovac–Pisanski (GP) index of a graph is a modified version of the Wiener index based on the distance between each vertex x and its image α (x) , where α is an automorphism of graph. The aim of this paper is to compute the automorphism group of some classes of cubic polyhedral graphs and then we determine their Wiener index. In addition, we investigate the GP-index of these classes of graphs. [ABSTRACT FROM AUTHOR]

A fullerene is a cubic three-connected graph whose faces are entirely composed of pentagons and hexagons. Entropy applied to graphs is one of the significant approaches to measuring the complexity of relational structures. Recently, the research on complex networks has received great attention, because many complex systems can be modelled as networks consisting of components as well as relations among these components. Information—theoretic measures have been used to analyze chemical structures possessing bond types and hetero-atoms. In the present article, we reviewed various entropy-based measures on fullerene graphs. In particular, we surveyed results on the topological information content of a graph, namely the orbit-entropy Ia(G), the symmetry index, a degree-based entropy measure Iλ(G), the eccentric-entropy Ifσ(G) and the Hosoya entropy H(G). [ABSTRACT FROM AUTHOR]

Every three-connected simple planar graph is a polyhedral graph and a cubic polyhedral graph with pentagonal and hexagonal faces is called as a classical fullerene. The aim of this paper is to survey some results about the symmetry group of cubic polyhedral graphs. We show that the order of symmetry group of such graphs divides 240. [ABSTRACT FROM AUTHOR]

This paper presents a proof of the existence of connected, undirected graphs with prescribed orbit structure, giving an explicit construction procedure for these graphs. Trees with prescribed orbit structure are also investigated. [ABSTRACT FROM AUTHOR]

In this paper we extend earlier results on Hosoya entropy (H-entropy) of graphs, and establish connections between H-entropy and automorphisms of graphs. In particular, we determine the H-entropy of graphs whose automorphism group has exactly two orbits, and characterize some classes of graphs with zero H-entropy. [ABSTRACT FROM AUTHOR]

• Novel Results on Partial Hosoya Polynomials: An Application in Chemistry • Submitted to Appl. Math. Comput. • In the paper several mistype errors were corrected and now the paper is complete. This article deal with an investigation of certain properties of partial Hosoya polynomial and then computing this new polynomial for some family of well-known graphs. Also, we verify some results concerning the zeros location of this polynomial in a ring shaped region. In this way, we include not only new results as special cases, but also improve the results due to Dehmer et al. [12] as a particular case. In continuing, the unique positive root of a new version of partial Hosoya polynomial has been evaluated. Finally, we explore some functional measures based on the complex zeros of partial Hosoya polynomials and then we compute the Pearson correlation between these measures and well-known topological indices. Our results show that these new measures have a linear correlation with the Wiener index. [ABSTRACT FROM AUTHOR]