Search

See PDF

Suppose $G$ is a undirected simple graph. A $k-$subset of edges in $G$ without common vertices is called a $k-$matching and the number of such subsets is denoted by $p(G,k)$. The aim of this paper is to present exact formulas for $p(G,3)$, $p(G,4)$ and $P(G,5)$ in terms of some degree-based invariants.

Suppose G is a simple graph with edge set E G . The Randić index R G is defined as R G = ∑ u v ∈ E G 1 / deg G u deg G v , where deg G u and deg G v denote the vertex degrees of u and v in G , respectively. In this paper, the first and second maximum of Randić index among all n − vertex c − cyclic graphs was computed. As a consequence, it is proved that the Randić index attains its maximum and second maximum on two classes of chemical graphs. Finally, we will present new lower and upper bounds for the Randić index of connected chemical graphs.

A (k,6)-fullerene graph is a planar 3-connected cubic graph whose faces are k-gons and hexagons. The aim of this paper is to compute the equitable chromatic, b-chromatic and list chromatic numbers ...

Suppose $p$ and $q$ are odd prime numbers. In this paper, the connected Cayley graph of groups of order $3pq$, for primes $p$ and $q$, are investigated and all connected normal $\frac{1}{2}-$arc-transitive Cayley graphs of group of these orders will be classified.

Let G be a graph with edge set E(G). The Randic and sum-connectivity indices of G are defined as R ( G ) = ∑ u v ∈ E ( G ) 1 d e g G ( u ) d e g G ( v ) and S C I ( G ) = ∑ u v ∈ E ( G ) 1 d e g G ( u ) + d e g G ( v ) , respectively, where degG(u) denotes the vertex degree of u in G. In this paper, the extremal Randic and sum-connectivity index among all n-vertex chemical trees, n ≥ 13, connected chemical unicyclic graphs, n ≥ 7, connected chemical bicyclic graphs, n ≥ 6 and connected chemical tricyclic graphs, n ≥ 8, were presented.

The power graph $\mathcal{P}(G)$ is a graph with group elements as a vertex set and two elements are adjacent if one is a power of the other. The order supergraph $\mathcal{S}(G)$ of the power graph $\mathcal{P}(G)$ is a graph with vertex set $G$ in which two elements $x, y \in G$ are joined if $o(x) | o(y)$ or $o(y) | o(x)$. The purpose of this paper is to study certain properties of this new graph together with the relationship between $\mathcal{P}(G)$ and $\mathcal{S}(G)$.

Let G be a finite group and c(G) denote the number of cyclic subgroups of G. The group G is called an n-cyclic group if $$c(G) = n$$ . In an earlier paper, finite n-cyclic groups with $$n \le 8$$ are classified and a characterization of the alternating group on five symbols based on the number of cyclic subgroups is given. The aim of this article is to continue this work by presenting a characterization of the simple group PSL(2, 7), by the number of cyclic subgroups. It is also proved that G is a 9-cyclic group if and only if $$G \cong D_{14}$$ , $$Z_5:Z_4$$ , $$Z_7:Z_3$$ , $$Z_3:Z_8$$ , $$Z_7 \times Z_7$$ , $$Z_{p^2q^2}$$ and $$Z_{p^8}$$ , where p and q are different primes, and G is 10-cyclic group if and only if $$G \cong D_{12}$$ , $$SD_{16}$$ , $$Z_4:Z_4$$ , $$Z_4 \times Z_4$$ , $$Z_{16}:Z_2$$ , $$Z_{16} \times Z_2$$ , $$Z_2 \times Q_8$$ , $$Z_{3r} \times Z_3$$ , $$Z_r \times S_3$$ , $$Z_p \times Q_8$$ and $$Z_{p^4q}$$ , where p, q, r are primes and $$r \ne 3$$ .

Let G be a simple and undirected graph with Laplacian polynomial ψ(G,λ)=∑k=0n(-1)n-kck(G)λk . In earlier works, some formulas for computing c2(G) , cn-2(G) and cn-3(G) in terms of the numbe...

The first degree-based entropy of a connected graph G is defined as: $$I_1(G)=\log (\sum _{v_i\in V(G)}\deg (v_i))-\sum _{v_j\in V(G)}\frac{\deg (v_j)\log \deg (v_j)}{\sum _{v_i\in V(G)}\deg ( v_i)}$$ . In this paper, we apply majorization technique to extend some known results about the maximum and minimum values of the first degree-based entropy of trees, unicyclic and bicyclic graphs.

Let G be a graph with vertex set V(G) and edge set E(G). A graph invariant for G is a number related to the structure of G which is invariant under the symmetry of G. The Sombor and reduced Sombor indices of G are two new graph invariants defined as SO(G)=∑uv∈E(G)dG(u)2+dG(v)2 and SOred(G)=∑uv∈E(G)dG(u)−12+dG(v)−12, respectively, where dG(v) is the degree of the vertex v in G. We denote by Hn,ν the graph constructed from the star Sn by adding ν edge(s), 0≤ν≤n−2, between a fixed pendent vertex and ν other pendent vertices. Réti et al. [T. Réti, T Došlić and A. Ali, On the Sombor index of graphs, Contrib. Math.3 (2021) 11–18] proposed a conjecture that the graph Hn,ν has the maximum Sombor index among all connected ν-cyclic graphs of order n, where 0≤ν≤n−2. In some earlier works, the validity of this conjecture was proved for ν≤5. In this paper, we confirm that this conjecture is true, when ν=6. The Sombor index in the case that the number of pendent vertices is less than or equal to n−ν−2 is investigated, and the same results are obtained for the reduced Sombor index. Some relationships between Sombor, reduced Sombor, and first Zagreb indices of graphs are also obtained.

Suppose G is a finite group with identity element 1. The generating graph $$\Gamma (G)$$ is defined as a graph with vertex set G in such a way that two distinct vertices are connected by an edge if and only if they generate G and the Q-generating graph $$\Omega (G)$$ is defined as the quotient graph $$\frac{\Gamma (G)\backslash \{ 1\}}{\mathcal {C}^\star (G)}$$ , where $$\mathcal {C}^\star (G)$$ is the set of all non-identity conjugacy classes of G and $$\Gamma (G)\backslash \{ 1\}$$ is a graph obtained from $$\Gamma (G)$$ by removing the vertex 1. In this paper, some structural properties of this graph are investigated. The structure of Q-generating graphs of dihedral, semidihedral, dicyclic and all sporadic groups other than M, B and $$Fi_{24}^\prime $$ is also presented.

For a molecular graph G with vertex set V(G), the Wiener polarity index Wp(G) is the number of unordered pairs of vertices {u, v} such that d G ( u , v ) = 3 . In this paper, an ordering of chemical trees of order n with respect to Wiener polarity index is given.

A graph is said to be a semi-Cayley graph over a group G if it admits G as a semiregular automorphism group with two orbits of equal size. In this paper, definition of normal edge-transitive, arc-t...

Let $G$ be a graph with edge set $E(G)$. The first and second reformulated Zagreb indices of $G$ are defined as $E M_1(G)=\sum_{e \in E(G)} \operatorname{deg}(e)^2$ and $E M_2(G)=\sum_{e \sim f} \operatorname{deg}(e) \operatorname{deg}(f)$,respectively, where $\operatorname{deg}(e)$ denotes the degree of the edge $e$, and $e \sim f$ means that the edges $e$ and $f$ are incident. In this paper, the extremal trees with respect to the first and second reformulated Zagreb indices are presented.

The variable sum exdeg index of a graph G is defined as SEIa(G)=uvE(G)[adegG(u)+adegG(v)], where a 1 is a positive real number. The aim of this paper is applying the majorization technique to obtain the maximum and minimum values of variable sum exdeg index of trees, unicyclic, bicyclic and tricyclic graphs.

The power graph $\mathcal{P}(G)$ of a group $G$ is the graphwith group elements as vertex set and two elements areadjacent if one is a power of the other. The aim of this paper is to compute the automorphism group of the power graph of several well-known and important classes of finite groups.

For a finite group G , the power graph P ( G ) is a graph with the vertex set G , in which two distinct elements are adjacent if one is a power of the other. Feng, Ma and Wang (Feng et al., 2016) described the full automorphism group of P ( G ) . In this paper, we study automorphism groups of the main supergraphs and cyclic graphs, which are supergraphs of P ( G ) . It is proved that the automorphism group of these graphs can be written as a combination of Cartesian and wreath products of some symmetric groups. The full automorphism groups of these graphs of certain finite groups are also calculated.

In this paper, the resolvent energy and spectral moment are investigated by the help of some special functions. Some sharp bounds are analyzed for these structures including its vertices, its edges, its degrees and its eigenvalues.

A zero divisor graph, Γ ( R ), is formed from a ring R by having each element of Z(R)\{ 0} to be a vertex in the graph and having two vertices u and v adjacent if the corresponding elements from the ring are nonequal and have product equal to zero. In this paper, the structure of the zero-divisor graph of 2 x 2 matrices over a field, Γ( M 2 ( F )), are completely determined. Mathematics Subject Classification (2010): Primary 13A99; Secondary 16U99, 05C50. Keywords: Zero divisor graph, ring, A- join of graphs

A logarithmic signature for a finite group G is a sequence α = [A1, …, As] of subsets of G such that every element g ∈ G can be uniquely written in the form g = g1…gs, where gi ∈ Ai, 1 ⩽ i ⩽ s. The number ∑si = 1|Ai| is called the length of α and denoted by l(α). A logarithmic signature α is said to be minimal (MLS) if l(α) = ∑ni = 1mipi, where is the prime factorization of |G|. The MLS conjecture states that every finite simple group has an MLS. The aim of this article is proving the existence of a minimal logarithmic signature for the untwisted groups G2(3n), the orthogonal groups Ω7(q) and PΩ+8(q), q is an odd prime power, the orthogonal groups Ω9(3), PΩ+10(3), and PΩ−8(3), the Tits simple group 2F4(2)′, the Janko group J3, the twisted group 3D4(2), the Rudvalis group Ru, and the Fischer group Fi22. As a consequence of our results, it is proved that all finite groups of order ⩽ 1012 other than the Ree group Ree(27), the O’Nan group O′N, and the untwisted group G2(7) have MLS.

The power graph of a group G is the graph with group elements as vertex set and two elements are adjacent if one is a power of the other. The aim of this paper is to compute the spectrum of the power graph of cyclic groups, dihedral groups, elementary abelian groups of prime power order and the Mathieu group .

The Fibonacci cube $${\Gamma_{n}}$$ is obtained from the n-cube Q n by removing all the vertices that contain two consecutive 1s. If, in addition, the vertices that start and end with 1 are removed, the Lucas cube $${\Lambda_{n}}$$ is obtained. The number of vertex and edge orbits, the sets of the sizes of the orbits, and the number of orbits of each size, are determined for the Fibonacci cubes and the Lucas cubes under the action of the automorphism group. In particular, the set of vertex orbit sizes of $${\Lambda_{n}}$$ is $${\{k \geq 1; k |n\} \cup \{k \geq 18; k |2n\}}$$ , the number of vertex orbits of $${\Lambda_{n}}$$ of size k, where k is odd and divides n, is equal to $${\sum_{d | k} \mu (\frac{k}{d})F_{\lfloor{\frac{d}{2}}\rfloor+2}}$$ , and the number of edge orbits of $${\Lambda_{n}}$$ is equal to the number of vertex orbits of $${\Gamma_{n-3}}$$ . Dihedral transformations of strings and primitive strings are essential tools to prove these results.

The Fibonacci cube ? n is obtained from the n-cube Q n by removing all the vertices that contain two consecutive 1s. It is proved that ? n admits a perfect code if and only if n ? 3 . Fibonacci cubes are isometric subgraphs of hypercubes and form an appealing model for interconnection networks.The study of codes in graphs presents a wide generalization of the problem of the existence of classical error-correcting codes.In this paper, it is proved that Fibonacci cubes do not admit any perfect code, unless the dimension is less than or equal to 3.

Suppose G is a connected graph or a union of connected graphs and ? is a subgroup of Aut(G). The modified Wiener index of G with respect to ? can be defined as follows: W ^ ? ( G ) = | V ( G ) | 2 | ? | ? u ? V ( G ) ? g ? ? d ( u , g ( u ) ) . In this article, this graph invariant for the cycle Cn with respect to all subgroups of Aut(Cn) is computed. As consequences, the modified Wiener indices of some molecular graphs like (3, 6)- and (5, 6)-fullerenes with respect to a subgroup of their symmetry groups are computed. Some open questions are also presented.

Suppose G is a graph, A(G) its adjacency matrix, and μ1(G)≤(G)μ2(G)≤ ... ≤ μ(n)(G)are eigenvalues of A(G). The numbers S(k)(G) = Σ(i) n = 1 μ(i)k (G), 0 ≤ k ≤ n -1 are said to be the k-th spectral moment of G and the sequence S(G) = (S0(G), S1 (G),..., S(n-1)(G)is called the spectral moments sequence of G. Suppose G1 and G2 are graphs. If there exists an integer k, 1 ≤ k ≤ n - 1, such that for each i, 0 ≤ i ≤ k - 1, S(i) (G1) = S(i)(G2) and S(k)(G1) < S(k)(G2) then we write G1

In this paper we present explicit formulas for computing the topological efficiency index of the most important graph operations such as the Cartesian product, composition, corona, join and hierarchical product of two graphs. We apply our results to compute this distance-related invariant for some important classes of molecular graphs and nano-structures by specializing components of these graph operations.

Let G be a graph with vertex set V(G). The total irregularity of G is defined as i r r t ( G ) = ∑ { u , v } ⊆ V ( G ) | d e g G ( u ) − d e g G ( v ) | , where degG(v) is the degree of the vertex v of G. The aim of this paper is to present some bounds for this graph invariant. A new simple proof for a recently proposed conjecture on total irregularity of graphs is also presented.

A group $H$ is said to be capable, if there exists another group$G$ such that $\frac{G}{Z(G)}~\cong~H$, where $Z(G)$ denotes thecenter of $G$. In a recent paper \cite{2}, the authorsconsidered the problem of capability of five non-abelian $p-$groups of order $p^4$ into account. In this paper, we continue this paper by considering three other groups of order $p^4$. It is proved that the group $$H_6=\langle x, y, z \mid x^{p^2}=y^p=z^p= 1, yx=x^{p+1}y, zx=xyz, yz=zy\rangle$$ is not capable. Moreover, if $p > 3$ is prime and $d \not\equiv 0, 1 \ (mod \ p)$ then the following groups are not capable:\\{\tiny $H_7^1=\langle x, y, z \mid x^{9} = y^3 = 1, z^3 = x^{3}, yx = x^{4}y, zx = xyz, zy = yz \rangle$,\\$H_7^2= \langle x, y, z \mid x^{p^2} = y^p = z^p = 1, yx = x^{p+1}y, zx = x^{p+1}yz, zy = x^pyz \rangle,$ \\$H_8^1=\langle x, y, z \mid x^{9} = y^3 = 1, z^3 = x^{-3}, yx = x^{4}y, zx = xyz, zy = yz \rangle$,\\$H_8^2=\langle x, y, z \mid x^{p^2} = y^p = z^p = 1, yx = x^{p+1}y, zx = x^{dp+1}yz, zy = x^{dp}yz \rangle$.}

The atom-bond connectivity index of a graph G(ABC indexfor short) is defined as the summation of quantitiesq d(u)+d(v)−2d(u)d(v) overall edges of G. A cactus graph is a connected graph in which every blockis an edge or a cycle. The aim of this paper is to obtain the first andsecond maximum values of the ABC index among all n vertex cactusgraphs. 1. IntroductionSuppose G is a simple connected graph with vertex and edge sets V (G) andE(G), respectively. A block of G is a maximal connected subgraphof G withoutcut-vertex. A cactus is a connected graph in which every block is an edge or acycle [18, p. 160]. These are connected graphs in which each edge belongs toat most one cycle. An example of a cactus graph is depicted in Figure 1.Figure 1. Examples of cactus graphs.Cactus graphs have several applications in computer science and biologyand so it is a topic of interest among many researchers in different scientificdisciplines. In [1, 6], it is proved that some graph problems which are NP-hardfor general graphs can be solved in polynomial time for cacti. On the otherhand, in [15] a number of combinatorial optimization problems are presented

A molecular graph is a graph in which vertices are atoms and edges are chemical bonds. In this paper, we describe a method for computing the symmetry of some giant carbon molecules. Some conjectures and open questions are also presented.

Let \(G\) be a simple graph. The Randic index of \(G\) is defined as the sum of \(\left( \sqrt{d_{G}(u)d_{G}(v)}\right) ^{-1}\) over all edges \(uv\) of \(G\), where \(d_{G}(x)\) denotes the vertex degree of \(x\) in \(G\). In this paper, the maximum and second maximum of Randic index in the set of all \(n-\)vertex tetracyclic graphs are computed.

A logarithmic signature for a finite group G is a sequence [A1,? ,As] of subsets of G such that every element g?G can be uniquely written in the form g=g1?gs, where gi?Ai, 1≤i≤s. The aim of this paper is proving the existence of an MLS for the Suzuki simple groups Sz(22m+1), m>1, when 22m+1+2m+1+1 or 22m+1?2m+1+1 are primes. The existence of an MLS for untwisted group G2(4) and the sporadic Suzuki group Suz are also proved. As a consequence of our results, we prove that the simple groups have an MLS.

The Timisoara-eccentricity (TM-EC) index of a molecular graphis defined as the sum of  i i i over all at- oms i in � , where  i,  i and  i are the degree, eccentricity and the number of atoms at distance  i from atom i. The topo- logical efficiency index ofis defined as = 2W / Nw , where W denotes the Wiener index, w is the minimal vertex contribution and N is the number of carbon atoms. This paper is devoted to the study of nanocones and fullerenes by these new graph in- variants. It is proved that the TM-EC index of a fullerenecan be bounded by a polynomial of degree 2, for twelve infinite series of fullerenes. It is also shown that in one pentagonal carbon nanocone with exactly 5n 2 + 10n + 5 carbon atoms, we have   1.24 and TM - EC = 280n 3 + 385n 2 + 195n + 40. Finally, we examine the dual of this nanocone and prove that we have   1.24 and TM - EC = 70n 3 + 20n 2 - 5n.

The power graph $${\fancyscript{P}}(G)$$ of a group $$G$$ is the graph which has a vertex set of the group elements and two elements are adjacent if one is a power of the other. Chakrabarty, Ghosh, and Sen proved the main properties of the undirected power graph of a finite group. The aim of this paper is to generalize some results of their work and presenting some counterexamples for one of the problems raised by these authors. It is also proved that the power graph of a $$p$$ -group is $$2$$ -connected if and only if the group is a cyclic or generalized quaternion group and if $$G$$ is a nilpotent group which is not of prime power order then the power graph $${\fancyscript{P}}(G)$$ is $$2$$ -connected. We also prove that the number of edges of the power graph of the simple groups is less than or equal to the number of edges in the power graph of the cyclic group of the same order. This partially answers to a question in an earlier paper. Finally, we give a complete classification of groups in which the power graph is a union of complete graphs sharing a common vertex.

Suppose G is a simple graph and ck = ck(G) denotes the number of complete subgraphs of size k in G. Then the dependence polynomial of G is defined as fG(x) = 1−c1x+c2x2−c3x3+⋯+(−1)nxn, where n is the size of the largest complete subgraph in G. In this paper, exact formulas for dependence polynomial of some graph operations are presented.

The aim of this paper is to classify the zero divisor graph of finite rings of cubefree order. It is proved that all zero divisor graphs can be interpreted as the extended join over well-known graphs.

A (3,6)-fullerene is a 3-connected cubic planar graph whose faces are triangles and hexagons. In this paper, it is proved that for a (3,6)-fullerene graph F, |Aut(F)| divides 24. An open question is also presented.

The revised Szeged index is a molecular structure descriptor equal to the sum of products $[n_u(e) + \frac{n_0(e)}{2}][n_v(e) + \frac{n_0(e)}{2}]$ over all edges $e = uv$ of the molecular graph $G$, where $n_0(e)$ is the number of vertices equidistant from $u$ and $v$, $n_u(e)$ is the number of vertices closer to $u$ than $v$ and $n_v(e)$ is defined analogously. The adjacency matrix of a graph weighted in this way is called its revised Szeged matrix and the set of its eigenvalues is the revised Szeged spectrum of $G$. In this paper some new results on the revised Szeged spectrum of graphs are presented.

The energy of a molecular graph G is defined as the summation of the absolute values of the eigenvalues of adjacency matrix of a graph G. In this paper, an infinite class of fullerene graphs with 10n vertices, n ≥ 2, is considered. By proving centrosymmetricity of the adjacency matrix of these fullerene graphs, a lower bound for its energy is given. Our method is general and can be extended to other class of fullerene graphs.

The atom–bond connectivity index is a useful graph invariant suitable for stability of alkanes and the strain energy of cycloalkanes. In this paper, the first, second and third maximum of this topological index in the class of all quasi-tree graphs are computed.

Themain goal of this paper is to obtain some bounds for the normalized Laplacian energy of a connected graph. The normalized Laplacian energy of the line and para-line graphs of a graph are investigated. The relationship of the smallest and largest positive normalized Laplacian eigenvalues of graphs are also studied.