Search

Topological indices are numerical parameters that indicate the topology of graphs or hypergraphs. A hypergraph H = ( V ( H ) , E ( H ) ) consists of a vertex set V ( H ) and an edge set E ( H ) , where each edge e ∈ E ( H ) is a subset of V ( H ) with at least two elements. In this paper, our main aim is to introduce a general hypergraph structure for the prime ideal sum (PIS)- graph of a commutative ring. The prime ideal sum hypergraph of a ring R is a hypergraph whose vertices are all non-trivial ideals of R and a subset of vertices E i with at least two elements is a hyperedge whenever I + J is a prime ideal of R for each non-trivial ideal I , J in E i and E i is maximal with respect to this property. Moreover, we also compute some degree-based topological indices (first and second Zagreb indices, forgotten topological index, harmonic index, Randić index, Sombor index) for these hypergraphs. In particular, we describe some degree-based topological indices for the newly defined algebraic hypergraph based on prime ideal sum for Z n where n = p α , p q , p 2 q , p 2 q 2 , p q r , p 3 q , p 2 q r , p q r s for the distinct primes p , q , r and s ., Competing Interests: The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper., (© 2024 The Author(s).)

The sum-connectivity, Randić, and atom-bond connectivity indices have a prominent place among those topological indices that depend on the graph's vertex degrees. The ABS (atom-bond sum-connectivity) index is a variant of all the aforementioned three indices, which was recently put forward. Let T ( n ) be the class of all connected tricyclic graphs of order n . Recently, the problem of determining graphs from T ( n ) having the least possible value of the ABS index was solved in (Zuo et al., 2024 [39]) for the case when the maximum degree of the considered graphs does not exceed 4. The present paper addresses the problem of finding graphs from T ( n ) having the largest possible value of the ABS index for n ≥ 5 ., Competing Interests: The authors declare the following financial interests/personal relationships which may be considered as potential competing interests: Yilun Shang, one of the coauthors of the present paper, is a section editor of the journal Heliyon where the present paper is being submitted. Other authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper., (© 2024 The Author(s).)

A topological index can be considered as the transformation of chemical structures into a real number. The study of molecular structures with the help of topological indices has an important role in the field of chemical graph theory. Dendrimers are chemical compounds which are highly-branched star-shaped macromolecules with nanometer-scale dimensions and have huge range of applications in almost all branches of chemistry. In this work, we calculate the generalized ISI index of certain families of Nanostar dendrimers. [ABSTRACT FROM AUTHOR]

The Fibonacci cube of dimension n, denoted as Γ n , is the subgraph of the hypercube induced by vertices with no consecutive 1s. The Lucas cube Λ n is the cyclic version of Γ n . The irregularity of a graph G is the sum of | d (x) - d (y) | over all edges { x , y } of G. In two recent papers based on the recursive structure of Γ n , it is proved that the irregularity of Γ n and Λ n is two times the number of edges of Γ n - 1 and 2n times the number of vertices of Γ n - 4 , respectively. Using an interpretation of the irregularity in terms of couples of incident edges of a special kind, we give a bijective proof of both results. For these two graphs, we deduce also a constant time algorithm for computing the imbalance of an edge. In the last section using the same approach, we determine the number of edges and the sequence of degrees of the cube complement of Γ n . [ABSTRACT FROM AUTHOR]

Given a finite group G, the permutability graph of non-normal subgroups Γ N (G) is given by all proper non-normal subgroups of G as vertex set and two vertices H and K are joined if H K = K H . Rajkumar and Devi generalized Γ N (G) to the permutability graph of subgroups Γ (G) , extending the vertex set to all proper subgroups of G (removing the assumption of being non-normal) and keeping the same criterion to join two vertices. We consider a natural counterpart for Γ (G) and Γ N (G) , that is, the subgroups lattice L (G) of G, and introduce the non-permutability graph of subgroups Γ L (G) ; its vertices are now given by the set L (G) - C L (G) (L (G)) , where C L (G) (L (G)) denotes the smallest sublattice of L (G) containing all permutable subgroups of G, and we join two vertices H, K of Γ L (G) if and only if H K ≠ K H . We study classical invariants of Γ L (G) , showing generalizations of previous results in the literature. [ABSTRACT FROM AUTHOR]

The first and second status connectivity indices of a connected graph G are defined as S 1 (G) = ∑ u v ∈ E (G) [ σ G (u) + σ G (v) ] and S 2 (G) = ∑ u v ∈ E (G) σ G (u) σ G (v) respectively, where E(G) is the edge set of G and σ G (u) is the sum of distances between the vertex u and all other vertices of G. In this paper we compute the status connectivity indices of line graphs of trees. Further we give the bounds for these indices of line graphs of connected graphs. [ABSTRACT FROM AUTHOR]

Let T be a tree. Then a vertex of T with degree one is a leaf of T and a vertex of degree at least three is a branch vertex of T. The set of leaves of T is denoted by L(T) and the set of branch vertices of T is denoted by B(T). For two distinct vertices u, v of T, let PT[u, v] denote the unique path in T connecting u and v. Let T be a tree with B(T) ≠ ∅. For each leaf x of T, let yx denote the nearest branch vertex to x. We delete V(PT[x, yx]) {yx} from T for all x ∈ L(T). The resulting subtree of T is called the reducible stem of T and denoted by R_Stem(T). We give sharp sufficient conditions on the degree sum for a graph to have a spanning tree whose reducible stem has a few branch vertices. [ABSTRACT FROM AUTHOR]

In this note, we show a sharp lower bound of min { ∑ i = 1 k d G (u i) : u 1 u 2 ... u k is a path of (2-)connected G on its order such that (k-1)-iterated line graphs Lk−1(G) are hamiltonian. [ABSTRACT FROM AUTHOR]

We prove the Erdős–Sós conjecture for trees with bounded maximum degree and large dense host graphs. As a corollary, we obtain an upper bound on the multicolour Ramsey number of large trees whose maximum degree is bounded by a constant. [ABSTRACT FROM AUTHOR]

The Balaban index and sum-Balaban index of a connected (molecular) graph G are defined as J (G) = m μ + 1 ∑ u v ∈ E (G) 1 σ G (u) σ G (v) and S J (G) = m μ + 1 ∑ u v ∈ E (G) 1 σ G (u) + σ G (v) , respectively, where m is the number of edges, μ is the cyclomatic number, σ G (u) is the sum of distances between vertex u and all other vertices of G. In this paper, we establish that K D S (n - 3 , 1) > K D S (n - 4 , 2) > ⋯ > K D S n 2 - 1 , n 2 - 1 (K = J , S J) , where D S (p , q) is a double star on n (= p + q + 2 , p ≥ q) vertices. As an application, we determine the extremal graphs of the Balaban index and the sum-Balaban index in the class of chain graphs G on n vertices, where G is a tree or a unicyclic graph. Finally, we give an open problem on Balaban (sum-Balaban) index of connected chain graphs. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a graph topological structure, called Intersection Graph Iτ(X) = (V(τ), E(τ)), where V(τ) = Collection of all topologies defined on X other than τi and τd and for τ1, τ2 ∈ V(τ), τ1 ∼ τ2 or (τ1, τ2) ∈ E(τ) if and only if τ1 ∩ τ2 ≠ τi. The diameter, girth, connectivity, maximal independent sets, different variants of domination number and chromatic number of Iτ(X) are studied. Moreover, we also derive upper and lower bounds of clique number and chromatic number of the graph Iτ(X). [ABSTRACT FROM AUTHOR]

We define the general degree-eccentricity index of a connected graph G as D E I a , b (G) = ∑ v ∈ V (G) d G a (v) e c c G b (v) for a , b ∈ R , where V(G) is the vertex set of G, d G (v) is the degree of a vertex v and e c c G (v) is the eccentricity of v in G. Let I 1 be any index which decreases with the addition of edges and let I 2 be any index which increases with the addition of edges. We obtain sharp lower bounds on the I 1 index and the D E I a , b index, where a < 0 and b > 0 , and sharp upper bounds on the I 2 index and the D E I a , b index, where a > 0 and b < 0 , for connected graphs of given order in combination with given independence number, vertex cover number or minimum degree. We also present sharp upper bounds on the D E I a , b index, where a ≥ 1 and b < 0 , for connected graphs of given order n in combination with given vertex connectivity, edge connectivity, number of pendant vertices, number of bridges or matching number β ≤ n 4 . [ABSTRACT FROM AUTHOR]

For a connected graph G, we denote the number of connected subgraphs of G by F(G). For a tree T, F(T) has been studied extensively and it has been observed that F(T) has a reverse correlation with Wiener index of T. We call F(G), the subgraph index of G. In this paper, we study the subgraph index of unicyclic graphs and graphs with fixed number of pendant vertices. We obtain the unicyclic graphs which extremize the subgraph index over all unicyclic graphs on n vertices. The graphs which extremize the subgraph index among all unicyclic graphs with fixed girth are also obtained. Among all connected graphs on n vertices with fixed number of pendant vertices, the graph which minimizes and the graph which maximizes the subgraph index are characterized. [ABSTRACT FROM AUTHOR]

Let T (X ∪ Y, A) be a bipartite tournament with partite sets X, Y and arc set A. For any vertex x ∈ X ∪Y, the second out-neighbourhood N++(x) of x is the set of all vertices with distance 2 from x. In this paper, we prove that T contains at least two vertices x such that |N++(x)| ≥ |N+(x)| unless T is in a special class ℬ1 of bipartite tournaments; show that T contains at least a vertex x such that |N++(x)| ≥ |N−(x)| and characterize the class ℬ2 of bipartite tournaments in which there exists exactly one vertex x with this property; and prove that if |X| = |Y | or |X| ≥ 4|Y |, then the bipartite tournament T contains a vertex x such that |N++(x)|+|N+(x)| ≥ 2|N−(x)|.

Oxide networks have diverse applications in the polymer and pharmaceutical industries. Polynomials and degree-based topological indices have tendencies to correlate properties of molecular graphs. In this article, we formulate the closed forms of Zagreb and forgotten polynomials and topological indices such as Hyper-Zagreb index, first and second multiple Zagreb indices, forgotten index, Albert index, Bell index, IRM(G) of oxide networks. We also compute the F-index of complement of oxide networks, F-coindex of G and F-coindex of complement of oxide networks. We put graphical analysis of each index with respect to the parameter involved in each case.

A set S of vertices of a graph G is called a decycling set if G−S is acyclic. The minimum order of a decycling set is called the decycling number of G, and denoted by ∇(G). Our results include: (a) For any graph G,, where T is taken over all the spanning trees of G and α(G − E(T)) is the independence number of the co-tree G − E(T). This formula implies that computing the decycling number of a graph G is equivalent to finding a spanning tree in G such that its co-tree has the largest independence number. Applying the formula, the lower bounds for the decycling number of some (dense) graphs may be obtained. (b) For any decycling set S of a k-regular graph G, where β(G) = |E(G)|−|V (G)|+1 and m(S) = c+|E(S)|−1, c and |E(S)| are, respectively, the number of components of G − S and the number of edges in G[S]. Hence S is a ∇-set if and only if m(S) is minimum, where∇-set denotes a decycling set containing exactly ∇(G) vertices of G. This provides a new way to locate ∇(G) for k-regular graphs G. (c) 4-regular graphs G with the decycling number are determined.

A bipartite-split graph is a bipartite graph whose vertex set can be partitioned into a complete bipartite set and an independent set. The bipartite- splittance of an arbitrary bipartite graph is the minimum number of edges to be added or removed in order to produce a bipartite-split graph. In this paper, we show that the bipartite-splittance of a bipartite graph depends only on the degree sequence pair of the bipartite graph, and an easily computable formula for it is derived. As a corollary, a simple characterization of the degree sequence pair of bipartite-split graphs is also given.

The authors in the paper [15] presented an algorithm that generates uniformly all the bipartite realizations and the other algorithm that generates uniformly all the simple bipartite realizations whenever A is a bipartite degree sequence of a simple graph. The running time of both algorithms is 𝒪(m),where m=12∑i=1nai${\rm{m}} = {1 \over 2}\sum\nolimits_{\rm {i} = 1}^n {{ \rm{a}_\rm {i}}}$. Let A =(A1 : A2 : ... : Ak) be a k-partite degree sequence of a simple graph, where Ai has ni entries such that ∑ni=n. In the present article, we give a generalized algorithm that generates uniformly all the k-partite realizations of A and another algorithm that generates uniformly all the simple k-partite realizations of A. The running time of both algorithms is 𝒪(m), where m=12∑i=1nai$m = {1 \over 2}\sum\nolimits_{i = 1}^n {{a_i}}$.

Let A = (a1, a2, ..., an) be a degree sequence of a simple bipartite graph. We present an algorithm that takes A as input, and outputs a simple bipartite realization of A, without stalling. The running time of the algorithm is ⊝(n1n2), where ni is the number of vertices in the part i of the bipartite graph. Then we couple the generation algorithm with a rejection sampling scheme to generate a simple realization of A uniformly at random. The best algorithm we know is the implicit one due to Bayati, Kim and Saberi (2010) that has a running time of O(mamax), where m=12∑i=1nai$m = {1 \over 2}\sum\nolimits_{i = 1}^n {{a_i}} and amax is the maximum of the degrees, but does not sample uniformly. Similarly, the algorithm presented by Chen et al. (2005) does not sample uniformly, but nearly uniformly. The realization of A output by our algorithm may be a start point for the edge-swapping Markov Chains pioneered by Brualdi (1980) and Kannan et al.(1999).

In this paper, we determine automorphisms of j(τ) and prove some results on j(τ),when topological space (X, τ) is finite. Also we determine necessary and sufficient condition for the open subset inclusion graphs of (X, τ1) and (X, τ2) to become isomorphic. Moreover, the topological space (X, τ) whose corresponding open subset inclusion graph is complete, is characterised. [ABSTRACT FROM AUTHOR]

We obtain lower and upper bounds on general multiplicative Zagreb indices for trees with given independence number and order. Bounds on basic multiplicative Zagreb indices follow from our results. We also show that the bounds are best possible. [ABSTRACT FROM AUTHOR]

Let G be a graph with set of vertices V G and set of edges E G . The Sombor index is a recently introduced vertex-degree-based-topological index, defined as S O (G) = ∑ u v ∈ E (G) (d u) 2 + (d v) 2 , where d u denotes the degree of the vertex u. In this paper we study the extremal values of SO over the set of unicyclic graphs and over the set of bicyclic graphs. [ABSTRACT FROM AUTHOR]

Topological index is a numerical value associated with a chemical constitution for correlation of chemical structure with various physical properties, chemical reactivity or biological activity. In this work, some new indices based on neighborhood degree sum of nodes are proposed. To make the computation of the novel indices convenient, an algorithm is designed. Quantitative structure property relationship (QSPR) study is a good statistical method for investigating drug activity or binding mode for different receptors. QSPR analysis of the newly introduced indices is studied here which reveals their predicting power. A comparative study of the novel indices with some well-known and mostly used indices in structure-property modelling and isomer discrimination is performed. Some mathematical properties of these indices are also discussed here. [ABSTRACT FROM AUTHOR]

Topological index is a useful number associated with molecular graph and the number correlate certain physico-chemical properties of chemical compounds. The concept of line graph and subdivision graph for a graph G has found various applications in chemical research. In this paper, we compute the first, second, and third Zagreb coindices, the F-coindex, the first and second multiplicative Zagreb coindices and the hyper Zagreb coindex of the subdivision graph and the line graph of subdivision graph of the wheel graph. [ABSTRACT FROM AUTHOR]

In this research work, we define the first and second Reciprocal leap functions of graph , where the d2(υ) is the second degree of the vertices. We compute the first and second Reciprocal leap function for some families of the graphs and some graph operations. Also we compute the first and second Reciprocal leap functions of the central and Mycielskian graphs of some standard graph and Graphene are obtained with their plotting in 3D. [ABSTRACT FROM AUTHOR]

For a connected graph G, the Mostar index Mo(G) and the irregularity irr(G) are defined as M o (G) = ∑ u v ∈ E (G) | n u - n v | and i r r (G) = ∑ u v ∈ E (G) | d u - d v | , respectively, where d u is the degree of the vertex u of G and n u denotes the number of vertices of G which are closer to u than to v for an edge uv. In this paper, we focus on the difference Δ M (G) = M o (G) - i r r (G) of graphs G. For trees T of order n, we characterize the minimum and second minimum Δ M (T) of T and the minimum Δ M (T r (T)) of the triangulation graphs Tr(T). The parity of Δ M of cactus graphs is also reported. The effect on Δ M is studied for two local operations of subdivision and contraction of an edge in a tree. A formula for Δ M (S (T)) of the subdivision trees S(T) and the upper and lower bounds on Δ M (S (T)) - Δ M (T) are determined with the corresponding extremal trees T. Moreover, three related open problems are proposed to Δ M of graphs. [ABSTRACT FROM AUTHOR]