Jia-Bao Liu

Metric dimension, doubly resolving set and strong metric dimension for $(C_n\Box P_k)\Box P_m$

A subset $Q = \{q_1, q_2, ..., q_l\}$ of vertices of a connected graph $G$ is a doubly resolving set of $G$ if for any various vertices $x, y \in V(G)$ we have $r(x|Q)-r(y|Q)\neqλI$ , where $λ$ is an integer, and $I$ indicates the unit $l$ - vector $(1,..., 1)$ . A doubly resolving set of vertices of graph $G$ with the minimum size, is denoted by $ψ(G)$ . In this work, we will consider the computational study of some resolving sets with the minimum size for $(C_n\Box P_k)\Box P_m$ .

On the Number of Conjugate Classes of Derangements

The number of conjugate classes of derangements of order $n$ is the same as the number $h(n)$ of the restricted partitions with every portion greater than $1$ . It is also equal to the number of isotopy classes of $2\times n$ Latin rectangles. Sometimes the exact value is necessary, while sometimes we need the approximation value. In this paper, a recursion formula of $h(n)$ will be obtained, also will some elementary approximation formulae with high accuracy for $h(n)$ be presented. Although we may obtain the value of $h(n)$ in some computer algebra system, it is still meaningful to find an efficient way to calculate the approximate value, especially in engineering, since most people are familiar with neither programming nor CAS software. This paper is mainly for the readers who need a simple and practical formula to obtain the approximate value (without writing a program) with more accuracy, such as to compute the value in an pocket science calculator without programming function. Some methods used here can also be applied to find the fitting functions for some types of data obtained in experiments.

The (degree)-Kirchhoff index of linear crossed octagonal-quadrilateral networks

The Kirchhoff index and degree-Kirchhoff index have attracted extensive attentions due to its practical applications in complex networks, physics, and chemistry. In 2019, Liu et al. [Int. J. Quantum Chem. 119 (2019) e25971] derived the formula of the degree-Kirchhoff index of linear octagonal-quadrilateral networks. In the present paper, we consider linear crossed octagonal-quadrilateral networks $Q_n$ . Explicit closed-form formulas of the Kirchhoff index, the degree-Kirchhoff index, and the number of spanning trees of $Q_n$ are obtained. Moreover, the Kirchhoff index (resp. degree-Kirchhoff index) of $Q_n$ is shown to be almost 1/4 of its Wiener index (resp. Gutman index).

The expected values and limiting behaviours for the Gutman index, Schultz index, multiplicative degree-Kirchhoff index and additive degree-kirchhoff index of a random cyclooctane chain

In this paper, we first introduce the explicit analytical formulas for the expected values of the Gutman and Schultz indices for a random cyclooctane chain COCn. Meanwhile, the explicit formulas of the variances of the Gutman and Schultz indices for a random cyclooctane chain are determined and we prove these two indices are asymptotically subject to normal distribution. Furthermore, we are surprised to find the variances of Kf*(COCn) and Kf+(COCn) for a random cyclooctane chain based on the known results of others' paper and they are asymptotically subject to normal distribution.

The expected values, variances and limiting distributions of Gutman index, Schultz index, multiplicative degree-Kirchhoff index and additive degree-Kirchhoff index for a class of random chain networks

There has been an upsurge of research on complex networks in recent years. The purpose of this paper is to study the mathematical properties of the random chain networks PGn with the help of graph theory. We first solve the expected value expressions of the Gutman index, Schultz index, multiplicative degree-Kirchhoff index and additive degree-Kirchhoff index, and then we get the explicit expression formulas of their variances. Finally, we find that their limiting distributions all have the probabilistic and statistical significance of normal distribution.

The Normalized Laplacian Spectrum Analysis of Fractal Mobius Octagonal Networks and its Applications

The study and calculation of spectrum of networks can be used to describe networks structure and quantify analysis of networks performance. The fractal Möbius octagonal networks, denoted by $Q_n$ , is derived from the inverse identification of the opposite lateral edges of fractal linear octagonal networks. In this paper, the normalized Laplacian spectrum of $Q_n$ is determined by two matrices $\mathcal {L}_A$ and $\mathcal {L}_S$ . As an important application of our results, some topological indices (multiplicative degree-Kirchhoff index, the number of spanning trees) formulas of $Q_n$ are obtained.

preprint2021arXiv

Some algebraic properties of a class of integral graphs determined by their spectrum

Let $Γ=(V,E)$ be a graph. If all the eigenvalues of the adjacency matrix of the graph $Γ$ are integers, then we say that $Γ$ is an integral graph. A graph $Γ$ is determined by its spectrum if every graph cospectral to it is in fact isomorphic to it. In this paper, we investigate some algebraic properties of the Cayley graph $Γ=Cay(\mathbb{Z}_{n}, S)$ , where $n=p^m$ , ( $p$ is a prime integer, $m\in\mathbb{N}$ ) and $S=\{{a}\in\mathbb{Z}_{n}\,|\,\, (a, n)=1\}$ . First, we show that $Γ$ is an integral graph. Also we determine the automorphism group of $Γ$ . Moreover, we show that $Γ$ and $K_v \bigtriangledownΓ$ are determined by their spectrum.

Computing Minimal Doubly Resolving Sets and the Strong Metric Dimension of the Layer Sun Graph and the Line Graph of Layer Sun Graph

Let $G$ be a finite, connected graph of order of at least 2, with vertex set $V(G)$ and edge set $E (G)$ . A set $S$ of vertices of the graph $G$ is a doubly resolving set for $G$ if every two distinct vertices of $G$ are doubly resolved by some two vertices of $S$ . The minimal doubly resolving set of vertices of graph $G$ is a doubly resolving set with minimum cardinality and is denoted by $ψ(G)$ . In this paper, first, we construct a class of graphs of order $2n+ Σ_{r=1}^{k-2}nm^{r}$ , denoted by $LSG(n,m, k)$ , and call these graphs as the layer Sun graphs with parameters $n$ , $m$ and $k$ . Moreover, we compute minimal doubly resolving sets and the strong metric dimension of layer Sun graph $LSG(n,m, k)$ and the line graph of the layer Sun graph $LSG(n,m, k)$ .

Metric dimension, minimal doubly resolving sets and the strong metric dimension for jellyfish graph and cocktail party graph

Let $Γ$ be a simple connected undirected graph with vertex set $V(Γ)$ and edge set $E(Γ)$ . The metric dimension of a graph $Γ$ is the least number of vertices in a set with the property that the list of distances from any vertex to those in the set uniquely identifies that vertex. For an ordered subset $W = \{w_1, w_2, ..., w_k\}$ of vertices in a graph $Γ$ and a vertex $v$ of $Γ$ , the metric representation of $v$ with respect to $W$ is the $k$ -vector $r(v | W) = (d(v, w_1), d(v, w_2), ..., d(v, w_k ))$ . If every pair of distinct vertices of $Γ$ have different metric representations then the ordered set $W$ is called a resolving set of $Γ$ . It is known that the problem of computing this invariant is NP-hard. In this paper, we consider the problem of determining the cardinality $ψ(Γ)$ of minimal doubly resolving sets of $Γ$ , and the strong metric dimension for jellyfish graph $JFG(n, m)$ and cocktail party graph $CP(k+1)$ .

On the Maximum ABC Spectral Radius of Connected Graphs and Trees

Let $G=(V,E)$ be a connected graph, where $V=\{v_1, v_2, \cdots, v_n\}$ and $m=|E|$ . $d_i$ will denote the degree of vertex $v_i$ of $G$ , and $Δ=\max_{1\leq i \leq n} d_i$ . The ABC matrix of $G$ is defined as $M(G)=(m_{ij})_{n \times n}$ , where $m_{ij}=\sqrt{(d_i + d_j -2)/(d_i d_j)}$ if $v_i v_j \in E$ , and 0 otherwise. The largest eigenvalue of $M(G)$ is called the ABC spectral radius of $G$ , denoted by $ρ_{ABC}(G)$ . Recently, this graph invariant has attracted some attentions. We prove that $ρ_{ABC}(G) \leq \sqrt{Δ+(2m-n+1)/Δ-2}$ . As an application, the unique tree with $n \geq 4$ vertices having second largest ABC spectral radius is determined.

Ordering Trees by Their ABC Spectral Radii

Let $G=(V,E)$ be a connected graph, where $V=\{v_1, v_2, \cdots, v_n\}$ . Let $d_i$ denote the degree of vertex $v_i$ . The ABC matrix of $G$ is defined as $M(G)=(m_{ij})_{n \times n}$ , where $m_{ij}=\sqrt{(d_i + d_j -2)/(d_i d_j)}$ if $v_i v_j \in E$ , and 0 otherwise. The ABC spectral radius of $G$ is the largest eigenvalue of $M(G)$ . In the present paper, we establish two graph perturbations with respect to ABC spectral radius. By applying these perturbations, the trees with the third, fourth, and fifth largest ABC spectral radii are determined.

The (multiplicative degree-)Kirchhoff index of graphs derived from the Catersian product of $S_n$ and $K_2$

Recently, Li et al. [Appl. Math. Comput. 382 (2020) 125335] proposed the problem of determining the Kirchhoff index and multiplicative degree-Kirchhoff index of graphs derived from $S_n \times K_2$ , the Catersian product of the star $S_n$ and the complete graph $K_2$ . In the present paper, we completely solve this problem. That is, the explicit closed-form formulae of Kirchhoff index, multiplicative degree-Kirchhoff index, and number of spanning trees are obtained for some graphs derived from $S_n \times K_2$ .

The Laplacian and normalized Laplacian spectra of Mobius polyomino networks and their applications

Spectral theory has widely used in complex networks and solved some practical problems. In this paper, we investigated the Laplacian and normalized Laplacian spectra of Mobius polyomino networks by using spectral theory. Let Mn denote Mobius polyomino networks (n>=3). As applications of the obtained results, the Kirchhoff index, multiplicative degree-Kirchhoff index, Kemeny's constant and spanning trees of Mn are obtained. Moreover, it is surprising to find that the multiplicative degree-Kirchhoff index of Mn is nine times as much as the Kirchhoff index.

The Laplacian spectrum, Kirchhoff index and complexity of the linear heptagonal networks

Let $H_n$ be the linear heptagonal networks with $2n$ heptagons. We study the structure properties and the eigenvalues of the linear heptagonal networks. According to the Laplacian polynomial of $H_n$ , we utilize the decomposition theorem. Thus, the Laplacian spectrum of $H_n$ is created by eigenvalues of a pair of matrices: $L_A$ and $L_S$ of order number $5n+1$ and $4n+1$ , respectively. On the basis of the roots and coefficients of their characteristic polynomials of $L_A$ and $L_S$ , we not only get the explicit forms of Kirchhoff index, but also corresponding total complexity of $H_n$ .

The normalized Laplacians and random walks of the parallel subdivision graphs

The $k$ -parallel subdivision graph $S_k(G)$ is generated from $G$ which each edge of $G$ is replaced by $k$ parallel paths of length 2. The $2k$ -parallel subdivision graph $S_{2k}(G)$ is constructed from $G$ which each edge of $G$ is replaced by $k$ parallel paths of length 3. In this paper, the normalized Laplacian spectra of $S_k(G)$ and $S_{2k}(G)$ are given. They turn out that the multiplicities of the corresponding eigenvalues are only determined by $k$ . As applications, the expected hitting time, the expected commute time and any two-points resistance distance between vertices $i$ and $j$ of $S_k(G)$ , the normalized Laplacian spectra of $S_k(G)$ and $S_{2k}(G)$ with $r$ iterations are given. Moreover, the multiplicative degree Kirchhoff index, Kemeny's constant and the number of spanning tress of $S_k(G)$ , $S_k^r(G)$ , $S_{2k}(G)$ and $S_{2k}^r(G)$ are respectively obtained. Our results have generalized the previous works in Xie et al. and Guo et al. respectively.

Bicyclic graphs with extremal degree resistance distance

Let $r(u,v)$ be the resistance distance between two vertices $u, v$ of a simple graph $G$ , which is the effective resistance between the vertices in the corresponding electrical network constructed from $G$ by replacing each edge of $G$ with a unit resistor. The degree resistance distance of a simple graph $G$ is defined as ${D_R}(G) = \sum\limits_{\{u,v\} \subseteq V(G)} {[d(u) + d(v)]r(u,v)},$ where $d(u)$ is the degree of the vertex $u$ . In this paper, the bicyclic graphs with extremal degree resistance distance are strong-minded. We first determine the $n$ -vertex bicyclic graphs having precisely two cycles with minimum and maximum degree resistance distance. We then completely characterize the bicyclic graphs with extremal degree resistance distance.

Further results on degree based topological indices of certain chemical networks

There are various topological indices such as degree based topological indices, distance based topological indices and counting related topological indices etc. These topological indices correlate certain physicochemical properties such as boiling point, stability of chemical compounds. In this paper, we compute the sum-connectivity index and multiplicative Zagreb indices for certain networks of chemical importance like silicate networks, hexagonal networks, oxide networks, and honeycomb networks. Moreover, a comparative study using computer-based graphs has been made to clarify their nature for these families of networks.

kirchhoff index and degree kirchhoff index of complete multipartite graph

The Kirchhoff index of a graph is defined as half of the sum of all effective resistance distances between any two vertices. Assuming a complete multipartite graph G, by methods from linear algebra we explicitly formulate effective resistance distances between any two vertices of G, and its Kirchhoff index. In rest of paper we explore extremal value of Kirchhoff index for multipartite graphs

On extremal multiplicative Zagreb indices of trees with given domination number

For a graph $G$ , the first multiplicative Zagreb index $\prod_1$ is equal to the product of squares of the vertex degrees, and the second multiplicative Zagreb index $\prod_2$ is equal to the product of the products of degrees of pairs of adjacent vertices. The (mutiplicative) Zagreb indices have been the focus of considerable research in computational chemistry dating back to Gutman and Trinajstić in 1972. In this paper, we explore the mutiplicative Zagreb indices in terms of arbitrary domination number. The sharp upper and lower bounds of $\prod_1(G)$ and $\prod_2(G)$ are given. In addition, the corresponding extreme graphs are charaterized.

Resistance distance and Kirchhoff index in the corona-vertex and the corona $-$ edge of subdivision graph

The subdivision graph $S(G)$ of a graph $G$ is the graph obtained by inserting a new vertex into every edge of $G$ . In $\cite{PL}$, two classes of new corona graphs, the corona-vertex of the subdivision graph $G_{1}\diamondsuit G_{2}$ and corona-edge of the subdivision graph $G_{1}\star G_{2}$ were defined. The adjacency spectrum and the signless Laplacian spectrum of the two new graphs were computed when $G_{1}$ is an arbitrary graph and $G_{2}$ is an $r$ -regular graph. In this paper, we give the formulate of the resistance distance and the Kirchhoff index in $G_{1}\diamondsuit G_{2}$ and $G_{1}\star G_{2}$ when $G_{1}$ and $G_{2}$ are arbitrary graphs. These results generalize them in $\cite{PL}$.

Structure Properties of Koch Networks Based on Networks Dynamical Systems

We introduce an informative labeling algorithm for the vertices of a family of Koch networks. Each of the labels is consisted of two parts, the precise position and the time adding to Koch networks. The shortest path routing between any two vertices is determined only on the basis of their labels, and the routing is calculated only by few computations. The rigorous solutions of betweenness centrality for every node and edge are also derived by the help of their labels. Furthermore, the community structure in Koch networks is studied by the current and voltage characteristics of its resistor networks.