Shou‐Jun Xu

Search for another author

Author Description

No additional information available

Ask a Question About This Mathematician

Hosoya polynomials of armchair open‐ended nanotubes

2006-09-22

Abstract For a connected graph G we denote by d ( G , k ) the number of vertex pairs at distance k . The Hosoya polynomial of G is … Abstract For a connected graph G we denote by d ( G , k ) the number of vertex pairs at distance k . The Hosoya polynomial of G is H ( G , x ) = ∑ k ≥0 d ( G , k ) x k . In this paper, analytical formulae for calculating the polynomials of armchair open‐ended nanotubes are given. Furthermore, the Wiener index, derived from the first derivative of the Hosoya polynomial in x = 1, and the hyper‐Wiener index, from one‐half of the second derivative of the Hosoya polynomial multiplied by x in x = 1, can be calculated. © 2006 Wiley Periodicals, Inc. Int J Quantum Chem, 2007

View PDF Chat

The Hosoya polynomial decomposition for catacondensed benzenoid graphs

2008-02-22

Shou‐Jun Xu , Heping Zhang

Hosoya polynomials of TUC4C8(S) nanotubes

2008-08-29

Shou‐Jun Xu , Heping Zhang

Generalized Hosoya polynomials of hexagonal chains

2007-08-20

Shou‐Jun Xu , Heping Zhang

Complete forcing numbers of catacondensed hexagonal systems

2013-05-14

Shou‐Jun Xu , Heping Zhang , Jinzhuan Cai

Hosoya polynomials under gated amalgamations

2008-01-07

Shou‐Jun Xu , Heping Zhang

Moplex orderings generated by the LexDFS algorithm

2013-03-18

Shou‐Jun Xu , Xianyue Li , Ronghua Liang

Complete forcing numbers of primitive coronoids

2015-04-29

Shou‐Jun Xu , Xiu-Song Liu , Wai Hong Ronald Chan +1 more

A Linear-Time Algorithm for Computing the Complete Forcing Number and the Clar Number of Catacondensed Hexagonal Systems

2015-01-01

Wai Hong Ronald Chan , Shou‐Jun Xu , Ge Nong

Let G be a graph with edge set E(G) that admits a perfect matching M. A forcing set of M is a subset of M contained in no other perfect … Let G be a graph with edge set E(G) that admits a perfect matching M. A forcing set of M is a subset of M contained in no other perfect matching of G. A complete forcing set of G, recently introduced by Xu et al. [Complete forcing numbers of catacondensed hexagonal systems, J. Comb. Optim., doi: 10.1007/s10878013-9624-x], is a subset of E(G) to which the restriction of any perfect matching M is a forcing set of M. The minimum possible cardinality of a complete forcing set of G is the complete forcing number of G. In this article, we prove theorems for general graphs about explicit relations between the complete forcing numbers under the operation of identifying edges. Regarding its applications to a catacondensed hexagonal system, we prove an unexpectedly linear relationship between the complete forcing number and the Clar number, an important concept on Clar’s aromatic sextet theory in chemistry, propose a linear-time algorithm for computing the complete forcing number and the Clar number and, nally, give an exponential sharp lower bound on the number of minimum complete forcing sets.

<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" id="d1e53" altimg="si28.svg"><mml:msub><mml:mrow><mml:mi>P</mml:mi></mml:mrow><mml:mrow><mml:mn>5</mml:mn></mml:mrow></mml:msub></mml:math>-isolation in graphs

2023-08-08

Jie Chen , Shou‐Jun Xu

None of the coronoid systems can be isometrically embedded into a hypercube

2008-01-07

Heping Zhang , Shou‐Jun Xu

The Hosoya Polynomial of One-Pentagonal Carbon Nanocone

2014-01-09

Qiuxia Zhang , Shou‐Jun Xu , Haiyang Chen

AbstractLet G be a chemical graph with vertex set V(G) and the distance between vertices u and v in G. The Hosoya polynomial in variable x of graph G is … AbstractLet G be a chemical graph with vertex set V(G) and the distance between vertices u and v in G. The Hosoya polynomial in variable x of graph G is . In this article, we give an analytical expression for calculating the Hosoya polynomial of one-pentagonal carbon nanocone. Furthermore, a series of distance-based molecular structure descriptors, such as the well-known Wiener index, the hyper-Wiener index, and the Harary index, can be easily obtained. From this point of view, we generalize the results on the Wiener index of one-pentagonal carbon nanocone by Ashrafi and Mohammad-Abadi (4). Wiener indexHosoya polynomialmolecular structure descriptorsone-pentagonal nanoconeHarary index

The Hosoya polynomial decomposition for hexagonal chains

2007-12-10

Shou‐Jun Xu , Heping Zhang

The complexity of total edge domination and some related results on trees

2020-06-05

Zhuo Pan , Yang Yu , Xianyue Li +1 more

View PDF Chat

Computation of the resistance distance and the Kirchhoff index for the two types of claw-free cubic graphs

2024-03-19

Muhammad Shoaib Sardar , Xiang-Feng Pan , Shou‐Jun Xu

The Hosoya Polynomial of One-Heptagonal Nanocone

2013-05-01

Shou‐Jun Xu , Qiuxia Zhang

For a molecular graph G with vertex set V (G) , we denote by dG (u,v ) the distance between vertices u and v in G ... Keywords: Wiener index, … For a molecular graph G with vertex set V (G) , we denote by dG (u,v ) the distance between vertices u and v in G ... Keywords: Wiener index, molecular structure descriptors, one-heptagonal nanocone, hosoya polynomial, hyper-wiener index, harary index.

Hosoya polynomials of TUC4C8(R) nanotubes

2008-10-06

Jianfu Chen , Shou‐Jun Xu , Heping Zhang

Abstract For a connected graph G , the Hosoya polynomial of G is defined as H ( G, x ) = ∑ { u,v }⊆ V ( G ) x … Abstract For a connected graph G , the Hosoya polynomial of G is defined as H ( G, x ) = ∑ { u,v }⊆ V ( G ) x d ( u, v ) , where V ( G ) is the set of all vertices of G and d ( u,v ) is the distance between vertices u and v . In this article, we obtain analytical expressions for Hosoya polynomials of TUC 4 C 8 ( R ) nanotubes. Furthermore, the Wiener index and the hyper‐Wiener index can be calculated. © 2008 Wiley Periodicals, Inc. Int J Quantum Chem, 2009

Global forcing number for maximal matchings

2017-12-26

Damir Vukičević , Shuang Zhao , Jelena Sedlar +2 more

On the maximum value of the eccentric distance sums of cubic transitive graphs

2019-05-11

Yan‐Ting Xie , Shou‐Jun Xu

2-Rainbow domination stability of graphs

2019-05-10

Zepeng Li , Zehui Shao , Shou‐Jun Xu

On the Resistance Distance and Kirchhoff Index of $$K_n$$-chain(Ring) Network

2024-05-16

Wensheng Sun , Muhammad Shoaib Sardar , Yujun Yang +1 more

On regular sets in Cayley graphs

2024-03-02

Xiaomeng Wang , Shou‐Jun Xu , Sanming Zhou

Extremal values on the Kirchhoff index of the line graph of trees

2024-09-01

Muhammad Shoaib Sardar , Shou‐Jun Xu , Xiang-Feng Pan

On the extremal values of the eccentric distance sum of trees with a given maximum degree

2020-04-14

Lianying Miao , Jingru Pang , Shou‐Jun Xu

A characterization of 3-γ-critical graphs which are not bicritical

2020-10-27

Jie Chen , Shou‐Jun Xu

On graphs maximizing the zero forcing number

2023-03-21

Yi-Ping Liang , Shou‐Jun Xu

Global Forcing Numbers of Handgun-shaped Benzenoid Systems

2014-08-31

Xiu-Song Liu , Shou‐Jun Xu , Liangping Tu

Let G be a molecular graph with bond set E(G) that admits a Kekulé structure. A global forcing set of G is any subset of E(G) such that no two … Let G be a molecular graph with bond set E(G) that admits a Kekulé structure. A global forcing set of G is any subset of E(G) such that no two Kekulé structures of G coincide on S. The number of bonds in a global forcing set of the smallest cardinality is called the global forcing number of G. The global forcing number gives some sort of identification of the minimal amount of information required to specify Kekule structures of a molecular graph. In this article, we give explicit formulae for global forcing numbers of handgun-shaped benzenoid systems. As a corollary, formulae for the global forcing numbers of parallelogram benzenoid systems can be obtained. [J. Sedlar, The global forcing number of the parallelogram polyhex, Discrete Appl. Math. 160 (2012) 2306-2313]. Keywords: Benzenoid hydrocarbon, global forcing number, global forcing set, handgun-shaped benzenoid system, Kekule structure, perfect matching.

A Hopf algebra on subgraphs of a graph

2019-07-29

Xiaomeng Wang , Shou‐Jun Xu , Xing Gao

In this paper, we construct a bialgebraic and further a Hopf algebraic structure on top of subgraphs of a given graph. Further, we give the dual structure of this Hopf … In this paper, we construct a bialgebraic and further a Hopf algebraic structure on top of subgraphs of a given graph. Further, we give the dual structure of this Hopf algebraic structure. We study the algebra morphisms induced by graph homomorphisms, and obtain a covariant functor from a graph category to an algebra category.

View PDF Chat

On Extremal Graphs for Zero Forcing Number

2022-11-07

Yi-Ping Liang , Jianxi Li , Shou‐Jun Xu

Spectral bounds for the zero forcing number of a graph

2023-01-29

Hongzhang Chen , Jianxi Li , Shou‐Jun Xu

Let Z(G) be the zero forcing number of a simple connected graph G.In this paper, we study the relationship between the zero forcing number of a graph and its (normalized) … Let Z(G) be the zero forcing number of a simple connected graph G.In this paper, we study the relationship between the zero forcing number of a graph and its (normalized) Laplacian eigenvalues.We provide the upper and lower bounds on Z(G) in terms of its (normalized) Laplacian eigenvalues, respectively.Our bounds extend the existing bounds for regular graphs.

View PDF Chat

The extendability of Cayley graphs generated by transpositions

2023-10-24

Yong‐De Feng , Yan‐Ting Xie , Shou‐Jun Xu

Resistance Distance and Kirchhoff Index in Windmill Graphs

2024-07-05

Muhammad Shoaib Sardar , Shou‐Jun Xu

The objective of this study is to compute the Kirchhoff index and resistance distance for two classes of windmill graphs, namely the French windmill graph and the Dutch windmill graph. … The objective of this study is to compute the Kirchhoff index and resistance distance for two classes of windmill graphs, namely the French windmill graph and the Dutch windmill graph. In this study, G is considered a simple connected graph with vertex set V (G) and edge set E(G). N is supposed to represent a network derived from G by substituting a 1-ohm resistor for each edge of G. In that case, the resistance between υ,ν ∈ V (G) is considered analogous to the resistance between two equivalent nodes in network N. We employed techniques from electrical network theory to compute the resistance distance and Kirchhoff index. The Kirchhoff index of G is the sum of the resistance distances between all pairs of vertices in G. Our computations revealed specific patterns and relationships in the resistance distances and Kirchhoff indices across different classes of windmill graphs. In addition, the Kirchhoff index and resistance distance are computed in this study for specific generalizations of these graphs. The derived equations can inspire further investigation into the resistance distance and Kirchhoff index in real-world windmill networks. Additionally, they offer a chemical framework for future research, aiding in the determination of molecular structures and characteristics.

Some results on <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" id="d1e44" altimg="si18.svg"><mml:mrow><mml:mo>{</mml:mo><mml:msub><mml:mrow><mml:mi>K</mml:mi></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>C</mml:mi></mml:mrow><mml:mrow><mml:mn>2</mml:mn><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>:</mml:mo><mml:mi>i</mml:mi><mml:mo linebreak="goodbreak" linebreakstyle="…

2024-09-06

Xiaoyun Lv , Jianxi Li , Shou‐Jun Xu

Resistance distance and Kirchhoff index of unbalanced blowups of graphs

2024-11-19

Wensheng Sun , Yujun Yang , Shou‐Jun Xu

Extremal Values on the Kirchhoff Index of the Line Graph of Unicyclic Networks

2024-12-03

Muhammad Shoaib Sardar , Shou‐Jun Xu

Hosoya Polynomials of Hexagonal Triangles and Trapeziums

2014-01-01

Q. He , Jianzhong Gu , Shou‐Jun Xu +1 more

The Hosoya polynomial of a graph G with vertex set V (G) is defined as H(G, x )= � {u,v}⊆V (G) x d G(u,v) in variable x, where the sum … The Hosoya polynomial of a graph G with vertex set V (G) is defined as H(G, x )= � {u,v}⊆V (G) x d G(u,v) in variable x, where the sum is over all unordered pairs {u, v} of vertices in G, dG(u, v) is the distance of two vertices u, v in G. In this paper, we investigate Hosoya polynomials of hexagonal trapeziums, tessellations of congruent regular hexagons shaped like trapeziums and give their explicit analytical expressions. As a special case, Hosoya polynomials of hexagonal triangles are obtained. Also, the three well-studied topological indices: Wiener index, hyper-Wiener index and Tratch-Stankevitch-Zefirov index, of hexagonal trapeziums can be easily obtained.

Hosoya polynomials of random benzenoid chains

2016-03-01

Shou‐Jun Xu , Q. He , Shan Zhou +1 more

Let G be a molecular graph with vertex set V(G) and dG(u,v) be the topological distance between vertices u and v in G. The Hosoya polynomial H(G,x) of G is … Let G be a molecular graph with vertex set V(G) and dG(u,v) be the topological distance between vertices u and v in G. The Hosoya polynomial H(G,x) of G is a polynomial d x in variable x. In this paper, we obtain an explicit analytical expression for the expected value of the Hosoya polynomial of a random benzenoid chain with n hexagons. Furthermore, as corollaries, the expected values of the well-known topological indices: Wiener index, hyper-Wiener index and TratchStankevitchZefirov index of a random benzenoid chain with n hexagons can be obtained by simple mathematical calculations, which generates the results given by I. Gutman et al. (Wiener numbers of random benzenoid chains, Chem. Phys. Lett. 173 (1990) 403408).

Hosoya polynomials of random phenylene chains.

2018-01-01

Q. He , Shou‐Jun Xu

The Geometrical Demonstration of the Order of Resonant Saddle Points in $${\mathbb {C}}^2$$

2020-01-30

Hao Wu , Shou‐Jun Xu

Independent Perfect Domination Sets in Semi-Cayley Graphs

2020-01-01

Xiaomeng Wang , Shou‐Jun Xu , Xianyue Li

Independent perfect dominating sets in semi-Cayley graphs

2021-02-22

Xiaomeng Wang , Shou‐Jun Xu , Xianyue Li

Complete Forcing Numbers of Random Multiple Hexagonal Chains

2021-11-03

Shuting Xue , Hong Bian , Lina Wei +2 more

Let G be a simple connected graph with vertex set V(G) and edge set E(G) that admits a perfect matching M. A forcing set of M is a subset of … Let G be a simple connected graph with vertex set V(G) and edge set E(G) that admits a perfect matching M. A forcing set of M is a subset of M contained in no other perfect matchings of G. The minimum cardinality of forcing sets is the forcing number of M. A complete forcing set of G, recently introduced by Xu et al. [Complete forcing numbers of catacondensed hexagonal systems, J. Combin. Optim. 29(4) (2015) 803-814], is a subset S of E(G) on which the restriction of any perfect matching M of G is a forcing set of M. A complete forcing set of the smallest cardinality is called a minimum complete forcing set, and its cardinality is the complete forcing number of G, denoted by cf(G). In this paper, we present the complete forcing sets and complete forcing number of random multiple hexagonal chains.

Hypercube embeddings and Cayley graphs generated by transpositions

2022-03-25

Yan‐Ting Xie , Yong‐De Feng , Shou‐Jun Xu

A graph is called a partial cube if it can be embedded into a hypercube isometrically. In this paper, we study a class of Cayley graphs— Cayley graphs generated by … A graph is called a partial cube if it can be embedded into a hypercube isometrically. In this paper, we study a class of Cayley graphs— Cayley graphs generated by transpositions —and show that a Cayley graph generated by transpositions is a partial cube if and only if is a bubble sort graph. This result enhances a result of Alahmadi et al. in 2016: is a partial cube. As a corollary, we give the analytical expressions of the Wiener indices of bubble sort graphs.

The Gevrey normalization for quasi-periodic systems under Siegel type small divisor conditions

2022-10-18

Shou‐Jun Xu , Hao Wu

On the local Gevrey integrability

2023-11-27

Shou‐Jun Xu , Hao Wu , Xiang Zhang

Comparability digraphs: An analogue of comparability graphs

2023-12-13

Xiaolu Gao , Jing Huang , Shou‐Jun Xu

View PDF Chat

A relation between the cube polynomials of partial cubes and the clique polynomials of their crossing graphs

2024-04-23

Yan‐Ting Xie , Yong‐De Feng , Shou‐Jun Xu

Abstract Partial cubes are the graphs which can be embedded into hypercubes. The cube polynomial of a graph is a counting polynomial of induced hypercubes of , which is defined … Abstract Partial cubes are the graphs which can be embedded into hypercubes. The cube polynomial of a graph is a counting polynomial of induced hypercubes of , which is defined as , where is the number of induced ‐cubes (hypercubes of dimension ) of . The clique polynomial of is defined as , where () is the number of ‐cliques in and . Equivalently, is exactly the independence polynomial of the complement of . The crossing graph of a partial cube is the graph whose vertices are corresponding to the ‐classes of , and two ‐classes are adjacent in if and only if they cross in . In the present paper, we prove that for a partial cube , and the equality holds if and only if is a median graph. Since every graph can be represented as the crossing graph of a median graph, the above necessary‐and‐sufficient result shows that the study on the cube polynomials of median graphs can be transformed to the one on the clique polynomials of general graphs (equivalently, on the independence polynomials of their complements). In addition, we disprove the conjecture that the cube polynomials of median graphs are unimodal.

On subgroup regular sets in Cayley sum graphs

2024-05-08

Xiaomeng Wang , Shou‐Jun Xu

A Characterization of Graphs with Semitotal Domination Number One-Third Their Order

2024-05-30

Jie Chen , Caixia Wang , Yiping Liang +1 more

Schultz polynomial and modified Schultz polynomial of a random benzenoid chain

2015-04-01

Q. He , Shou‐Jun Xu

Let G be a graph with a vertex set V(G), d(G)(u,v) and delta G(v) denote the topological distance between vertices u and v in G and the degree of the … Let G be a graph with a vertex set V(G), d(G)(u,v) and delta G(v) denote the topological distance between vertices u and v in G and the degree of the vertex v in G, respectively. The Schultz polynomial of G is defined as H+ (G) = Sigma ({u,v}subset of V(G)) (delta(G)(u) + delta(G)(v))x(dG(u,v)) and the modified Schultz polynomial of G is defined as H* (G) = Sigma ({u,v}subset of V(G)) (delta(G)(u) + delta(G)(v))x(dG(u,v)) alytical expressions for expected values of Schultz polynomial and modified Schultz polynomial of a random benzenoid chain with n hexagons. Further expected values of some related topological indices are obtained.

Some Results on the Existence of Spanning k-ended Trees in a t-connected Graph

2025-05-30

Hongzhang Chen , Jianxi Li , Shou‐Jun Xu

Extremal linear triangular chains with respect to the Kirchhoff index

2025-05-22

Wensheng Sun , Yujun Yang , Shou‐Jun Xu

Abstract Let G be a connected graph. The resistance distance among two vertices is defined as the effective resistance between the corresponding nodes in the electrical network constructed from G … Abstract Let G be a connected graph. The resistance distance among two vertices is defined as the effective resistance between the corresponding nodes in the electrical network constructed from G by replacing each edge with a unit resistor. The Kirchhoff index is an important distance-based topological index corresponding to graphs, which is the sum of all the resistance distances pairs of G . Let B n be a linear polyomino chain with n squares. The linear triangular chain is a graph with 2 n triangles, characterized by randomly adding an edge to each square of B n so as to make it into two triangular faces. In this paper, by standard techniques of electrical networks and the recursion formula for resistance distances, we characterize the linear triangular chains with extreme Kirchhoff index.

The $$A_{\alpha }$$-spectral radius for $$\{P_{2}, C_{3}, P_{5}, \mathcal {T}(3)\}$$-factors in graphs

2025-05-06

Xiaoyun Lv , Jianxi Li , Shou‐Jun Xu

The deleted co-maximal subgroup graphs of some groups

2025-03-22

Li‐Na Wei , Hong Bian , Shou‐Jun Xu

Stability of Graph Pairs Involving Cycles

2025-03-21

Xiaomeng Wang , Shou‐Jun Xu , Sanming Zhou

RDDGN: minimizing the total resistance distance and diameter using graph neural networks

2025-03-17

Muhammad Shoaib Sardar , Muhammad Shahid Iqbal , Shou‐Jun Xu

Characterizing path-factor deleted graphs via $Q$-index and $\mathcal{D}$-index

2025-03-17

Xiaoyun Lv , Jianxi Li , Shou‐Jun Xu

A graph $G$ has a $\mathcal{P}_{\geq k}$-factor if $G$ has a spanning subgraph $H$ such that every component of $H$ is a path of order at least $k$. A graph … A graph $G$ has a $\mathcal{P}_{\geq k}$-factor if $G$ has a spanning subgraph $H$ such that every component of $H$ is a path of order at least $k$. A graph $G$ is $\mathcal{P}_{\geq k}$-factor deleted if $G-e$ has a $\mathcal{P}_{\geq k}$-factor for each edge $e \in E(G)$. In this paper, we study the $\mathcal{P}_{\geq 2}$-factor deleted graphs by their $Q$-index (the largest eigenvalue of the signless Laplacian matrix) and $\mathcal{D}$-index (the largest eigenvalue of the distance matrix). Sufficient conditions (in terms of $Q$-index and $\mathcal{D}$-index) to guarantee that a graph $G$ to be a $\mathcal{P}_{\geq 2}$-factor deleted graph are established.

Two Variants of Toughness of a Graph and its Eigenvalues

2025-03-01

Hongzhang Chen , Jianxi Li , Shou‐Jun Xu

Disproof of a Conjecture on the Edge Mostar Index

2024-12-31

Fazal Hayat , Shou‐Jun Xu , Bo Zhou

For a connected graph $G$, the edge Mostar index $Mo_e(G)$ is defined as $Mo_e(G)=\sum\limits_{e=uv \in E(G)}|m_u(e|G) - m_v(e|G)|$, where $m_u(e|G)$ and $m_v(e|G)$ are respectively, the number of edges of $G$ … For a connected graph $G$, the edge Mostar index $Mo_e(G)$ is defined as $Mo_e(G)=\sum\limits_{e=uv \in E(G)}|m_u(e|G) - m_v(e|G)|$, where $m_u(e|G)$ and $m_v(e|G)$ are respectively, the number of edges of $G$ lying closer to vertex $u$ than to vertex $v$ and the number of edges of $G$ lying closer to vertex $v$ than to vertex $u$. We determine a sharp upper bound for the edge Mostar index on bicyclic graphs and identify the graphs that achieve the bound, which disproves a conjecture proposed by Liu et al. [Iranian J. Math. Chem. 11(2) (2020) 95--106].

Extremal Values on the Kirchhoff Index of the Line Graph of Unicyclic Networks

2024-12-03

Muhammad Shoaib Sardar , Shou‐Jun Xu

Resistance distance and Kirchhoff index of unbalanced blowups of graphs

2024-11-19

Wensheng Sun , Yujun Yang , Shou‐Jun Xu

Reducibility of 2-Dimensional Ultra-Differentiable Quasi-Periodic Systems with Small Parameters Under Brjuno-Rüssmann Condition

2024-11-15

Shou‐Jun Xu , Hao Wu , Junxiang Xu

GRAPHS WITH SEMITOTAL DOMINATION NUMBER HALF THEIR ORDER

2024-09-13

Jie Chen , Shou‐Jun Xu

Abstract In an isolate-free graph G , a subset S of vertices is a semitotal dominating set of G if it is a dominating set of G and every vertex … Abstract In an isolate-free graph G , a subset S of vertices is a semitotal dominating set of G if it is a dominating set of G and every vertex in S is within distance 2 of another vertex of S . The semitotal domination number of G , denoted by $\gamma _{t2}(G)$ , is the minimum cardinality of a semitotal dominating set in G . Goddard, Henning and McPillan [‘Semitotal domination in graphs’, Utilitas Math. 94 (2014), 67–81] characterised the trees and graphs of minimum degree 2 with semitotal domination number half their order. In this paper, we characterise all graphs whose semitotal domination number is half their order.

Some results on <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" id="d1e44" altimg="si18.svg"><mml:mrow><mml:mo>{</mml:mo><mml:msub><mml:mrow><mml:mi>K</mml:mi></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>C</mml:mi></mml:mrow><mml:mrow><mml:mn>2</mml:mn><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>:</mml:mo><mml:mi>i</mml:mi><mml:mo linebreak="goodbreak" linebreakstyle="…

2024-09-06

Xiaoyun Lv , Jianxi Li , Shou‐Jun Xu

Extremal values on the Kirchhoff index of the line graph of trees

2024-09-01

Muhammad Shoaib Sardar , Shou‐Jun Xu , Xiang-Feng Pan

Ultra log-concavity and real-rootedness of dependence polynomials

2024-08-17

Yan-Ting Xie , Shou‐Jun Xu

For some positive integer $m$, a real polynomial $P(x)=\sum\limits_{k=0}^ma_kx^k$ with $a_k\geqslant 0$ is called log-concave (resp. ultra log-concave) if $a_k^2\geqslant a_{k-1}a_{k+1}$ (resp. $a_k^2\geqslant \left(1+\frac{1}{k}\right)\left(1+\frac{1}{m-k}\right)\cdot$ $a_{k-1}a_{k+1}$) for all $1\leqslant k\leqslant m-1$. … For some positive integer $m$, a real polynomial $P(x)=\sum\limits_{k=0}^ma_kx^k$ with $a_k\geqslant 0$ is called log-concave (resp. ultra log-concave) if $a_k^2\geqslant a_{k-1}a_{k+1}$ (resp. $a_k^2\geqslant \left(1+\frac{1}{k}\right)\left(1+\frac{1}{m-k}\right)\cdot$ $a_{k-1}a_{k+1}$) for all $1\leqslant k\leqslant m-1$. If $P(x)$ has only real roots, then it is called real-rooted. It is well-known that the conditions of log-concavity, ultra log-concavity and real-rootedness are ever-stronger. For a graph $G$, a dependent set is a set of vertices which is not independent, i.e., the set of vertices whose induced subgraph contains at least one edge. The dependence polynomial of $G$ is defined as $D(G, x):=\sum\limits_{k\geqslant 0}d_k(G)x^k$, where $d_k(G)$ is the number of dependent sets of size $k$ in $G$. Horrocks proved that $D(G, x)$ is log-concave for every graph $G$ [J. Combin. Theory, Ser. B, 84 (2002) 180--185]. In the present paper, we prove that, for a graph $G$, $D(G, x)$ is ultra log-concave if $G$ is $(K_2\cup 2K_1)$-free or contains an independent set of size $|V(G)|-2$, and give the characterization of graphs whose dependence polynomials are real-rooted. Finally, we focus more attention to the problems of log-concavity about independence systems and pose several conjectures closely related the famous Mason's Conjecture.

View PDF Chat

Algorithmic aspects of {P}-isolation in graphs and extremal graphs for a {P3}-isolation bound

2024-07-14

Jie Chen , Yi-Ping Liang , Caixia Wang +1 more

Resistance Distance and Kirchhoff Index in Windmill Graphs

2024-07-05

Muhammad Shoaib Sardar , Shou‐Jun Xu

Minimizing the second Zagreb eccentricity index in bipartite graphs with a fixed size and diameter

2024-06-29

Fazal Hayat , Shou‐Jun Xu , Xuli Qi

A characterization of regular partial cubes whose all convex cycles have the same lengths

2024-06-28

Yan‐Ting Xie , Yong‐De Feng , Shou‐Jun Xu

Abstract Partial cubes are graphs that can be isometrically embedded into hypercubes. Convex cycles play an important role in the study of partial cubes. In this paper, we prove that … Abstract Partial cubes are graphs that can be isometrically embedded into hypercubes. Convex cycles play an important role in the study of partial cubes. In this paper, we prove that a regular partial cube is a hypercube (resp., a Doubled Odd graph, an even cycle of length where ) if and only if all its convex cycles are 4‐cycles (resp., 6‐cycles, ‐cycles). In particular, the partial cubes whose all convex cycles are 4‐cycles are equivalent to almost‐median graphs. Therefore, we conclude that regular almost‐median graphs are exactly hypercubes, which generalizes the result by Mulder—regular median graphs are hypercubes.

View PDF Chat

Solution to a conjecture on resistance distances of block tower graphs

2024-06-06

Wensheng Sun , Yujun Yang , Wu‐Xian Chen +1 more

Let $G$ be a connected graph. The resistance distance between two vertices $u$ and $v$ of $G$, denoted by $R_{G}[u,v]$, is defined as the net effective resistance between them in … Let $G$ be a connected graph. The resistance distance between two vertices $u$ and $v$ of $G$, denoted by $R_{G}[u,v]$, is defined as the net effective resistance between them in the electric network constructed from $G$ by replacing each edge with a unit resistor. The resistance diameter of $G$, denoted by $D_{r}(G)$, is defined as the maximum resistance distance among all pairs of vertices of $G$. Let $P_n=a_1a_2\ldots a_n$ be the $n$-vertex path graph and $C_{4}=b_{1}b_2b_3b_4b_{1}$ be the 4-cycle. Then the $n$-th block tower graph $G_n$ is defined as the the Cartesian product of $P_n$ and $C_4$, that is, $G_n=P_{n}\square C_4$. Clearly, the vertex set of $G_n$ is $\{(a_i,b_j)|i=1,\ldots,n;j=1,\ldots,4\}$. In [Discrete Appl. Math. 320 (2022) 387--407], Evans and Francis proposed the following conjecture on resistance distances of $G_n$ and $G_{n+1}$: \begin{equation*} \lim_{n \rightarrow \infty}\left(R_{G_{n+1}}[(a_{1},b_1),(a_{n+1},b_3)]-R_{G_{n}}[(a_{1},b_1),(a_{n},b_3)]\right)=\frac{1}{4}. \end{equation*} In this paper, combing algebraic methods and electric network approaches, we confirm and further generalize this conjecture. In addition, we determine all the pair of vertices that reach the resistance diameter of $G_{n}$, which enables us to give an equivalent explanation of the conjecture.

View PDF Chat

A Characterization of Graphs with Semitotal Domination Number One-Third Their Order

2024-05-30

Jie Chen , Caixia Wang , Yiping Liang +1 more

On the Resistance Distance and Kirchhoff Index of $$K_n$$-chain(Ring) Network

2024-05-16

Wensheng Sun , Muhammad Shoaib Sardar , Yujun Yang +1 more

Extremal Bicyclic Graphs with Respect to Permanental Sums and Hosoya Indices

2024-05-16

Tingzeng Wu , Yinggang Bai , Shou‐Jun Xu

Graph polynomials is one of the important research directions in mathematical chemistry. The coefficients of some graph polynomials, such as matching polynomial and permanental polynomial, are related to structural properties … Graph polynomials is one of the important research directions in mathematical chemistry. The coefficients of some graph polynomials, such as matching polynomial and permanental polynomial, are related to structural properties of graphs. The Hosoya index of a graph is the sum of the absolute value of all coefficients for the matching polynomial. And the permanental sum of a graph is the sum of the absolute value of all coefficients of the permanental polynomial. In this paper, we characterize the second to sixth minimal Hosoya indices of all bicyclic graphs. Furthermore, using the results, the second to sixth minimal permanental sums of all bicyclic graphs are also characterized.

View PDF Chat

On subgroup regular sets in Cayley sum graphs

2024-05-08

Xiaomeng Wang , Shou‐Jun Xu

A relation between the cube polynomials of partial cubes and the clique polynomials of their crossing graphs

2024-04-23

Yan‐Ting Xie , Yong‐De Feng , Shou‐Jun Xu

Computation of the resistance distance and the Kirchhoff index for the two types of claw-free cubic graphs

2024-03-19

Muhammad Shoaib Sardar , Xiang-Feng Pan , Shou‐Jun Xu

Extremal results on the Mostar index of trees with fixed parameters

2024-03-08

Fazal Hayat , Shou‐Jun Xu

For a graph [Formula: see text], the Mostar index of [Formula: see text] is the sum of [Formula: see text] over all edges [Formula: see text] of [Formula: see text], … For a graph [Formula: see text], the Mostar index of [Formula: see text] is the sum of [Formula: see text] over all edges [Formula: see text] of [Formula: see text], where [Formula: see text] denotes the number of vertices of [Formula: see text] that have a smaller distance in [Formula: see text] to [Formula: see text] than to [Formula: see text], and analogously for [Formula: see text]. We determine all the graphs that maximize and minimize the Mostar index, respectively, over all trees in terms of some fixed parameters like the number of odd vertices, the number of vertices of degree two, and the number of pendent paths of fixed length.

View PDF Chat

Perfect codes in circulant graphs of degree $p^l-1$

2024-03-04

Xiaomeng Wang , Oriol Serra , Shou‐Jun Xu +1 more

A perfect code in a graph is an independent set of the graph such that every vertex outside the set is adjacent to exactly one vertex in the set. A … A perfect code in a graph is an independent set of the graph such that every vertex outside the set is adjacent to exactly one vertex in the set. A circulant graph is a Cayley graph of a cyclic group. In this paper we study perfect codes in circulant graphs of degree $p^l - 1$, where $p$ is a prime and $l \ge 1$. We obtain a necessary and sufficient condition for such a circulant graph to admit perfect codes, give a construction of all such circulant graphs which admit perfect codes, and prove a lower bound on the number of distinct perfect codes in such a circulant graph. This extends known results for the case $l=1$ and provides insight on the general problem on the existence and structure of perfect codes in circulant graphs.

View PDF Chat

On regular sets in Cayley graphs

2024-03-02

Xiaomeng Wang , Shou‐Jun Xu , Sanming Zhou

Stability of graph pairs involving cycles

2024-03-02

Xiaomeng Wang , Shou‐Jun Xu , Sanming Zhou

A graph pair $(\Gamma, \Sigma)$ is called stable if $\aut(\Gamma)\times\aut(\Sigma)$ is isomorphic to $\aut(\Gamma\times\Sigma)$ and unstable otherwise, where $\Gamma\times\Sigma$ is the direct product of $\Gamma$ and $\Sigma$. A graph is … A graph pair $(\Gamma, \Sigma)$ is called stable if $\aut(\Gamma)\times\aut(\Sigma)$ is isomorphic to $\aut(\Gamma\times\Sigma)$ and unstable otherwise, where $\Gamma\times\Sigma$ is the direct product of $\Gamma$ and $\Sigma$. A graph is called $R$-thin if distinct vertices have different neighbourhoods. $\Gamma$ and $\Sigma$ are said to be coprime if there is no nontrivial graph $\Delta$ such that $\Gamma \cong \Gamma_1 \times \Delta$ and $\Sigma \cong \Sigma_1 \times \Delta$ for some graphs $\Gamma_1$ and $\Sigma_1$. An unstable graph pair $(\Gamma, \Sigma)$ is called nontrivially unstable if $\Gamma$ and $\Sigma$ are $R$-thin connected coprime graphs and at least one of them is non-bipartite. This paper contributes to the study of the stability of graph pairs with a focus on the case when $\Sigma = C_n$ is a cycle. We give two sufficient conditions for $(\Gamma, C_n)$ to be nontrivially unstable, where $n \ne 4$ and $\Gamma$ is an $R$-thin connected graph. In the case when $\Gamma$ is an $R$-thin connected non-bipartite graph, we obtain the following results: (i) if $(\Gamma, K_2)$ is unstable, then $(\Gamma, C_{n})$ is unstable for every even integer $n \geq 4$; (ii) if an even integer $n \ge 6$ is compatible with $\Gamma$ in some sense, then $(\Gamma, C_{n})$ is nontrivially unstable if and only if $(\Gamma, K_2)$ is unstable; (iii) if there is an even integer $n \ge 6$ compatible with $\Gamma$ such that $(\Gamma, C_{n})$ is nontrivially unstable, then $(\Gamma, C_{m})$ is unstable for all even integers $m \ge 6$. We also prove that if $\Gamma$ is an $R$-thin connected graph and $n \ge 3$ is an odd integer compatible with $\Gamma$, then $(\Gamma, C_{n})$ is stable.

View PDF Chat

Semitotal forcing in claw-free cubic graphs

2024-01-01

Yi-Ping Liang , Jie Chen , Shou‐Jun Xu

For an isolate-free graph G = (V (G), E(G)), a set S ⊆ V (G) is called a semitotal forcing set of G if it is a forcing set (or … For an isolate-free graph G = (V (G), E(G)), a set S ⊆ V (G) is called a semitotal forcing set of G if it is a forcing set (or a zero forcing set) of G and every vertex in S is within distance 2 of another vertex of S. The semitotal forcing number F t2 (G) is the minimum cardinality of a semitotal forcing set in G.In this paper, we prove that if G = K 4 is a connected claw-free cubic graph of order n, then F t2 (G) ≤ 3 8 n + 1.The graphs achieving equality in this bound are characterized, an infinite set of graphs.

View PDF Chat

A lower bound on the Mostar index of tricyclic graphs

2024-01-01

Fazal Hayat , Shou‐Jun Xu

For a graph G, the Mostar index of G is the sum of |nu-nv| over all edges e = uv of G, where nu denotes the number of vertices of … For a graph G, the Mostar index of G is the sum of |nu-nv| over all edges e = uv of G, where nu denotes the number of vertices of G that have a smaller distance in G to u than to v, and analogously for nv. In this paper, we obtain a lower bound for the Mostar index on tricyclic graphs and identify those graphs that attain the lower bound.

Comparability digraphs: An analogue of comparability graphs

2023-12-13

Xiaolu Gao , Jing Huang , Shou‐Jun Xu

View PDF Chat

On the local Gevrey integrability

2023-11-27

Shou‐Jun Xu , Hao Wu , Xiang Zhang

The extendability of Cayley graphs generated by transpositions

2023-10-24

Yong‐De Feng , Yan‐Ting Xie , Shou‐Jun Xu

<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" id="d1e53" altimg="si28.svg"><mml:msub><mml:mrow><mml:mi>P</mml:mi></mml:mrow><mml:mrow><mml:mn>5</mml:mn></mml:mrow></mml:msub></mml:math>-isolation in graphs

2023-08-08

Jie Chen , Shou‐Jun Xu

UPPER BOUNDS ON THE SEMITOTAL FORCING NUMBER OF GRAPHS

2023-06-19

Yi-Ping Liang , Jie Chen , Shou‐Jun Xu

Abstract Let G be a graph with no isolated vertex. A semitotal forcing set of G is a (zero) forcing set S such that every vertex in S is within … Abstract Let G be a graph with no isolated vertex. A semitotal forcing set of G is a (zero) forcing set S such that every vertex in S is within distance 2 of another vertex of S . The semitotal forcing number $F_{t2}(G)$ is the minimum cardinality of a semitotal forcing set in G . In this paper, we prove that it is NP-complete to determine the semitotal forcing number of a graph. We also prove that if $G\neq K_n$ is a connected graph of order $n\geq 4$ with maximum degree $\Delta \geq 2$ , then $F_{t2}(G)\leq (\Delta-1)n/\Delta$ , with equality if and only if either $G=C_{4}$ or $G=P_{4}$ or $G=K_{\Delta ,\Delta }$ .

On graphs maximizing the zero forcing number

2023-03-21

Yi-Ping Liang , Shou‐Jun Xu

Spectral bounds for the zero forcing number of a graph

2023-01-29

Hongzhang Chen , Jianxi Li , Shou‐Jun Xu

View PDF Chat

A characterization of regular partial cubes whose all convex cycles have the same lengths

2023-01-01

Yanting Xie , Yong‐De Feng , Shou‐Jun Xu

Partial cubes are graphs that can be isometrically embedded into hypercubes. Convex cycles play an important role in the study of partial cubes. In this paper, we prove that a … Partial cubes are graphs that can be isometrically embedded into hypercubes. Convex cycles play an important role in the study of partial cubes. In this paper, we prove that a regular partial cube is a hypercube (resp., a doubled Odd graph, an even cycle of length $2n$ where $n\geqslant 4$) if and only if all its convex cycles are 4-cycles (resp., 6-cycles, $2n$-cycles). In particular, the partial cubes whose all convex cycles are 4-cycles are equivalent to almost-median graphs, so we obtain that regular almost-median graphs are exactly hypercubes, which generate the result by Mulder [J. Graph Theory, 4 (1980) 107--110] -- regular median graphs are hypercubes.

View PDF Chat

A relation between the cube polynomials of partial cubes and the clique polynomials of their crossing graphs

2023-01-01

Yan‐Ting Xie , Yong‐De Feng , Shou‐Jun Xu

Partial cubes are the graphs which can be embedded into hypercubes. The {\em cube polynomial} of a graph $G$ is a counting polynomial of induced hypercubes of $G$, which is … Partial cubes are the graphs which can be embedded into hypercubes. The {\em cube polynomial} of a graph $G$ is a counting polynomial of induced hypercubes of $G$, which is defined as $C(G,x):=\sum_{i\geqslant 0}\alpha_i(G)x^i$, where $\alpha_i(G)$ is the number of induced $i$-cubes (hypercubes of dimension $i$) of $G$. The {\em clique polynomial} of $G$ is defined as $Cl(G,x):=\sum_{i\geqslant 0}a_i(G)x^i$, where $a_i(G)$ ($i\geqslant 1$) is the number of $i$-cliques in $G$ and $a_0(G)=1$. Equivalently, $Cl(G, x)$ is exactly the independence polynomial of the complement $\overline{G}$ of $G$. The {\em crossing graph} $G^{\#}$ of a partial cube $G$ is the graph whose vertices are corresponding to the $\Theta$-classes of $G$, and two $\Theta$-classes are adjacent in $G^{\#}$ if and only if they cross in $G$. In the present paper, we prove that for a partial cube $G$, $C(G,x)\leqslant Cl(G^{\#}, x+1)$ and the equality holds if and only if $G$ is a median graph. Since every graph can be represented as the crossing graph of a median graph [SIAM J. Discrete Math., 15 (2002) 235--251], the above necessary-and-sufficient result shows that the study on the cube polynomials of median graphs can be transformed to the one on the clique polynomials of general graphs (equivalently, on the independence polynomials of their complements). In addition, we disprove the conjecture that the cube polynomials of median graphs are unimodal.

On bicyclic graphs with maximum edge Mostar index

2023-01-01

Fazal Hayat , Shou‐Jun Xu , Bo Zhou

For a given connected graph $G$, the edge Mostar index $Mo_e(G)$ is defined as $Mo_e(G)=\sum_{e=uv \in E(G)}|m_u(e|G) - m_v(e|G)|$, where $m_u(e|G)$ and $m_v(e|G)$ are respectively, the number of edges of … For a given connected graph $G$, the edge Mostar index $Mo_e(G)$ is defined as $Mo_e(G)=\sum_{e=uv \in E(G)}|m_u(e|G) - m_v(e|G)|$, where $m_u(e|G)$ and $m_v(e|G)$ are respectively, the number of edges of $G$ lying closer to vertex $u$ than to vertex $v$ and the number of edges of $G$ lying closer to vertex $v$ than to vertex $u$. In this paper, we determine sharp upper bound for edge Mostar index on bicyclic graphs with fixed number of edges, also the graphs that achieve the bound are completely characterized, and thus disprove a conjecture on the edge Mostar index of bicyclic graph in [H. Liu, L. Song, Q. Xiao, Z. Tang, On edge Mostar index of graphs. Iranian J. Math. Chem. 11(2) (2020) 95--106].

View PDF Chat

Extremal results on the Mostar index of trees with fixed parameters

2023-01-01

Fazal Hayat , Shou‐Jun Xu

For a graph $G$, the Mostar index of $G$ is the sum of $|n_u(e)$ - $n_v(e)|$ over all edges $e=uv$ of $G$, where $n_u(e)$ denotes the number of vertices of … For a graph $G$, the Mostar index of $G$ is the sum of $|n_u(e)$ - $n_v(e)|$ over all edges $e=uv$ of $G$, where $n_u(e)$ denotes the number of vertices of $G$ that have a smaller distance in $G$ to $u$ than to $v$, and analogously for $n_v(e)$. We determine all the graphs that maximize and minimize the Mostar index respectively over all trees in terms of some fixed parameters like the number of odd vertices, the number of vertices of degree two, and the number of pendent paths of fixed length.

On tricyclic graphs with maximum edge Mostar index

2023-01-01

Fazal Hayat , Shou‐Jun Xu , Bo Zhou

For a given connected graph $G$, the edge Mostar index $Mo_e(G)$ is defined as $Mo_e(G)=\sum_{e=uv \in E(G)}|m_u(e|G) - m_v(e|G)|$, where $m_u(e|G)$ and $m_v(e|G)$ are respectively, the number of edges of … For a given connected graph $G$, the edge Mostar index $Mo_e(G)$ is defined as $Mo_e(G)=\sum_{e=uv \in E(G)}|m_u(e|G) - m_v(e|G)|$, where $m_u(e|G)$ and $m_v(e|G)$ are respectively, the number of edges of $G$ lying closer to vertex $u$ than to vertex $v$ and the number of edges of $G$ lying closer to vertex $v$ than to vertex $u$. In this paper, we determine the sharp upper bound for the edge Mostar index on tricyclic graphs with a fixed number of edges, and the graphs that attain the bound are completely characterized.

On regular sets in Cayley graphs

2023-01-01

Xiaomeng Wang , Shou‐Jun Xu , Sanming Zhou

Let $\Ga = (V, E)$ be a graph and $a, b$ nonnegative integers. An $(a, b)$-regular set in $\Ga$ is a nonempty proper subset $D$ of $V$ such that every … Let $\Ga = (V, E)$ be a graph and $a, b$ nonnegative integers. An $(a, b)$-regular set in $\Ga$ is a nonempty proper subset $D$ of $V$ such that every vertex in $D$ has exactly $a$ neighbours in $D$ and every vertex in $V \setminus D$ has exactly $b$ neighbours in $D$. A $(0,1)$-regular set is called a perfect code, an efficient dominating set, or an independent perfect dominating set. A subset $D$ of a group $G$ is called an $(a,b)$-regular set of $G$ if it is an $(a, b)$-regular set in some Cayley graph of $G$, and an $(a, b)$-regular set in a Cayley graph of $G$ is called a subgroup $(a, b)$-regular set if it is also a subgroup of $G$. In this paper we study $(a, b)$-regular sets in Cayley graphs with a focus on $(0, k)$-regular sets, where $k \ge 1$ is an integer. Among other things we determine when a non-trivial proper normal subgroup of a group is a $(0, k)$-regular set of the group. We also determine all subgroup $(0, k)$-regular sets of dihedral groups and generalized quaternion groups. We obtain necessary and sufficient conditions for a hypercube or the Cartesian product of $n$ copies of the cycle of length $p$ to admit $(0, k)$-regular sets, where $p$ is an odd prime. Our results generalize several known results from perfect codes to $(0, k)$-regular sets.

Solution to an open problem on the closeness of graphs

2023-01-01

Fazal Hayat , Shou‐Jun Xu

A network can be analyzed by means of many graph theoretical parameters. In the context of networks analysis, closeness is a structural metric that evaluates a node's significance inside a … A network can be analyzed by means of many graph theoretical parameters. In the context of networks analysis, closeness is a structural metric that evaluates a node's significance inside a network. A cactus is a connected graph in which any block is either a cut edge or a cycle. This paper analyzes the closeness of cacti, we determine the unique graph that minimizes the closeness over all cacti with fixed numbers of vertices and cycles, which solves an open problem proposed by Poklukar \& \v{Z}erovnik [Fundam. Inform. 167 (2019) 219--234].

View PDF Chat

On Extremal Graphs for Zero Forcing Number

2022-11-07

Yi-Ping Liang , Jianxi Li , Shou‐Jun Xu

The Gevrey normalization for quasi-periodic systems under Siegel type small divisor conditions

2022-10-18

Shou‐Jun Xu , Hao Wu

Hypercube embeddings and Cayley graphs generated by transpositions

2022-03-25

Yan‐Ting Xie , Yong‐De Feng , Shou‐Jun Xu

Coauthor	Papers Together
Heping Zhang	10
Xiaomeng Wang	9
Fazal Hayat	8
Yan‐Ting Xie	7
Yong‐De Feng	7
Jianxi Li	6
Muhammad Shoaib Sardar	6
Yi-Ping Liang	5
Sanming Zhou	5
Xianyue Li	5
Wai Hong Ronald Chan	4
Wensheng Sun	4
Q. He	4
Hao Wu	4
Yujun Yang	4
Hong Bian	3
Xing Gao	3
Jie Chen	3
Hongzhang Chen	3
Bo Zhou	2
Yang Yu	2
Xiaoyun Lv	2
Jie Chen	2
Xiu-Song Liu	2
Xiaolu Gao	2
Zhuo Pan	2
Qiuxia Zhang	2
Xiang-Feng Pan	2
Caixia Wang	2
Haizheng Yu	2
Shuting Xue	2
Zepeng Li	1
Jing Huang	1
Yanting Xie	1
Yiping Liang	1
Shan Zhou	1
Lina Wei	1
Guangfu Wang	1
Jianxi Li	1
Lianying Miao	1
Yan-Ting Xie	1
Jianzhong Gu	1
Ronghua Liang	1
Jingru Pang	1
Yuliang Cao	1
Muhammad Shahid Iqbal	1
Xiao-Lu Gao	1
Zehui Shao	1
Wu‐Xian Chen	1
Lina Wei	1

On some counting polynomials in chemistry

1988-03-01

Haruo Hosoya

Topological Index. A Newly Proposed Quantity Characterizing the Topological Nature of Structural Isomers of Saturated Hydrocarbons

1971-09-01

Haruo Hosoya

Abstract A topological index Z is proposed for a connected graph G representing the carbon skeleton of a saturated hydrocarbon. The integer Z is the sum of a set of … Abstract A topological index Z is proposed for a connected graph G representing the carbon skeleton of a saturated hydrocarbon. The integer Z is the sum of a set of the numbers p(G,k), which is the number of ways in which such k bonds are so chosen from G that no two of them are connected. For chain molecules Z is closely related to the characteristic polynomial derived from the topological matrix. It is found that Z is correlated well with the topological nature of the carbon skeleton, i.e., the mode of branching and ring closure. Some interesting relations are found, such as a graphical representation of the Fibonacci numbers and a composition principle for counting Z. Correlation of Z with boiling points of saturated hydrocarbons is pointed out.

View PDF Chat

Wiener polynomials of some chemically interesting graphs

2004-01-01

Bo‐Yin Yang , Yeong‐Nan Yeh

Abstract The chemist Harold Wiener found 𝒲( G ), the sum of distances between all pairs of vertices in a connected graph G , to be useful as a predictor … Abstract The chemist Harold Wiener found 𝒲( G ), the sum of distances between all pairs of vertices in a connected graph G , to be useful as a predictor of certain physical and chemical properties. The q ‐analogue of 𝒲, called the Wiener polynomial 𝒲( G ; q ), is also useful, but it has few existing useful formulas. We will evaluate 𝒲( G ; q ) for certain graphs G of chemical interest. © 2004 Wiley Periodicals, Inc. Int J Quantum Chem, 2004

The Wiener polynomial of a graph

1996-01-01

Bruce E. Sagan , Yeong-Nan Yeh , Ping Zhang

The Wiener index is a graphical invariant that has found extensive application in chemistry. We define a generating function, which we call the Wiener polynomial, whose derivative is a q-analog … The Wiener index is a graphical invariant that has found extensive application in chemistry. We define a generating function, which we call the Wiener polynomial, whose derivative is a q-analog of the Wiener index. We study some of the elementary properties of this polynomial and compute it for some common graphs. We then find a formula for the Wiener polynomial of a dendrimer, a certain highly regular tree of interest to chemists, and show that it is unimodal. Finally, we point out a connection with the Poincaré polynomial of a finite Coxeter group. © 1996 John Wiley & Sons, Inc.

View PDF Chat

Resistance distance

1993-12-01

Douglas J. Klein , Milan Randić

Hosoya polynomials under gated amalgamations

2008-01-07

Shou‐Jun Xu , Heping Zhang

Hosoya polynomials of armchair open‐ended nanotubes

2006-09-22

Shou‐Jun Xu , Heping Zhang

View PDF Chat

Extended Wiener indices. A new set of descriptors for quantitative structure-property studies

1998-01-01

Ernesto Estrada , Ovidiu Ivanciuc , Iván Gutman +2 more

Higher order analogues of the Wiener number are defined, providing rather precise regression models for a number of physico-chemical properties of alkanes, which certainly are much better than the analogous … Higher order analogues of the Wiener number are defined, providing rather precise regression models for a number of physico-chemical properties of alkanes, which certainly are much better than the analogous models based solely on the Wiener number. The new structure descriptors are defined on the basis of the Wiener–Hosoya polynomial HG(x): the kth extended Wiener index kW is equal to the kth derivative of HG(x), evaluated at x=1, in which case 1W is just the original Wiener number.

On the resistance diameter of hypercubes

2019-10-16

Muhammad Shoaib Sardar , Hongbo Hua , Xiang-Feng Pan +1 more

Upper bounds on the<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" display="inline" overflow="scroll"><mml:mi>k</mml:mi></mml:math>-forcing number of a graph

2014-09-20

David Amos , Yair Caro , Randy Davila +1 more

Resistance distance and Laplacian spectrum

2003-11-01

Wenjun Xiao , Iván Gutman

Total forcing number of the triangular grid

2004-12-22

Damir Vukičević , Jelena Sedlar

L etT be a square triangular grid with n rows and columns of vertices and n an even number. A set of edges E ⊂ E(T ) completely determines perfect … L etT be a square triangular grid with n rows and columns of vertices and n an even number. A set of edges E ⊂ E(T ) completely determines perfect matchings on T if there are no two dif- ferent matchings on T coinciding on E. We establish the upper and the lower bound for the smallest value of |E|, i.e. we show that 5 4 n 2 − 21 2 n +

Graphical properties of polyhexes: Perfect matching vector and forcing

1991-12-01

Frank Harary , Douglas J. Klein , Tomislav P. Živković

Handbook of Product Graphs

2011-06-06

Richard H. Hammack , Wilfried Imrich , Sandi Klavžar

Handbook of Product Graphs, Second Edition examines the dichotomy between the structure of products and their subgraphs. It also features the design of efficient algorithms that recognize products and their … Handbook of Product Graphs, Second Edition examines the dichotomy between the structure of products and their subgraphs. It also features the design of efficient algorithms that recognize products and their subgraphs and explores the relationship between graph parameters of the product and factors. Extensively revised and expanded, the handbook presents full proofs of many important results as well as up-to-date research and conjectures. Results and Algorithms New to the Second Edition: Cancellation results A quadratic recognition algorithm for partial cubes Results on the strong isometric dimension Computing the Wiener index via canonical isometric embedding Connectivity results A fractional version of Hedetniemis conjecture Results on the independence number of Cartesian powers of vertex-transitive graphs Verification of Vizings conjecture for chordal graphs Results on minimum cycle bases Numerous selected recent results, such as complete minors and nowhere-zero flows The second edition of this classic handbook provides a thorough introduction to the subject and an extensive survey of the field. The first three parts of the book cover graph products in detail. The authors discuss algebraic properties, such as factorization and cancellation, and explore interesting and important classes of subgraphs. The fourth part presents algorithms for the recognition of products and related classes of graphs. The final two parts focus on graph invariants and infinite, directed, and product-like graphs. Sample implementations of selected algorithms and other information are available on the books website, which can be reached via the authors home pages.

Resistance distance and Kirchhoff index in circulant graphs

2006-09-05

Heping Zhang , Yujun Yang

Abstract The resistance distance r ij between vertices i and j of a connected (molecular) graph G is computed as the effective resistance between nodes i and j in the … Abstract The resistance distance r ij between vertices i and j of a connected (molecular) graph G is computed as the effective resistance between nodes i and j in the corresponding network constructed from G by replacing each edge of G with a unit resistor. The Kirchhoff index Kf ( G ) is the sum of resistance distances between all pairs of vertices. In this work, closed‐form formulae for Kirchhoff index and resistance distances of circulant graphs are derived in terms of Laplacian spectrum and eigenvectors. Special formulae are also given for four classes of circulant graphs (complete graphs, complete graphs minus a perfect matching, cycles, Möbius ladders M p ). In particular, the asymptotic behavior of Kf ( M p ) as p → ∞ is obtained, that is, Kf ( M p ) grows as ⅙ p 3 as p → ∞. © 2006 Wiley Periodicals, Inc. Int J Quantum Chem, 2007

Resistance distance in regular graphs

1999-01-01

I. Lukovits , Sonja Nikoli , Nenad Trinajsti

This report considers the resistance distance as a recently proposed new intrinsic metric on (molecular) graphs, and in particular, the sum R over resistance distances between all pairs of vertices … This report considers the resistance distance as a recently proposed new intrinsic metric on (molecular) graphs, and in particular, the sum R over resistance distances between all pairs of vertices is considered as a graph invariant. It has been proved that R(GN)>R(KN), where GN denotes a connected graph containing N vertices and KN denotes a complete graph containing N vertices. The formulas to obtain the R for two classes of regular graphs (cycles and complete graphs) are derived. Numerical values of R for four Platonic molecules are also given. They ordered the considered Platonic solids as the icosahedron, the cube, the octahedron, and the tetrahedron according to complexity of their Schlegel graphs. This order agrees with those obtained by many other, frequently used descriptors. ©1999 John Wiley & Sons, Inc. Int J Quant Chem 71: 217–225, 1999

Distance-Related Indexes in the Quantitative Structure−Property Relationship Modeling

2001-01-09

Bono Lučić , István Lukovits , Sonja Nikolić +1 more

A comparative study of structure-boiling point modeling for a set of 180 acyclic and cyclic hydrocarbons (DS-180) and two of its subsets (one containing a selection of 76 acyclic and … A comparative study of structure-boiling point modeling for a set of 180 acyclic and cyclic hydrocarbons (DS-180) and two of its subsets (one containing a selection of 76 acyclic and cyclic alkanes (DS-76), and the other containing 104 (DS-104) mono- and polycyclic butanes through octanes) using several known and novel distance-related indices is reported. The distance-related indices used were as follows: Wiener index, hyper-Wiener index, detour index, hyper-detour index, Harary index, Pasaréti index, Vérhalom index, Wiener-sum index, inverse Wiener-sum index and the product-form version of the Wiener index. Additional indices used were the total number of paths, the Hosoya Z index, the total walk count index, the number of carbon atoms, and the number of rings in the hydrocarbon. The best models for predicting the boiling points of 76, 104, and 180 acyclic and cyclic alkanes contain the natural logarithm of the cross-products of the Hosoya and detour index and of the Pasaréti index and the number of rings. This result extends earlier work by us and Rücker and Rücker on the use of the Wiener, detour, and Hosoya indices in modeling boiling points of alkanes and cycloalkanes. It also supports later work by Rücker and Rücker on the use of the descriptor combination for the same purpose.

Resistance distance in straight linear 2-trees

2018-11-24

Wayne Barrett , Emily J. Evans , Amanda Francis

View PDF Chat

Wiener number of vertex-weighted graphs and a chemical application

1997-12-01

Sandi Klavžar , Iván Gutman

View PDF Chat

On the spectrum of the forced matching number of graphs

2009-01-01

Peyman Afshani , Hamed Hatami , E. S. Mahmoodian

Let $G$ be a graph that admits a perfect matching. A {\sf forcing set} for a perfect matching $M$ of $G$ is a subset $S$ of $M$, such that $S$ … Let $G$ be a graph that admits a perfect matching. A {\sf forcing set} for a perfect matching $M$ of $G$ is a subset $S$ of $M$, such that $S$ is contained in no other perfect matching of $G$. This notion originally arose in chemistry in the study of molecular resonance structures. Similar concepts have been studied for block designs and graph colorings under the name {\sf defining set}, and for Latin squares under the name {\sf critical set}. Recently several papers have appeared on the study of forcing sets for other graph theoretic concepts such as dominating sets, orientations, and geodetics. Whilst there has been some study of forcing sets of matchings of hexagonal systems in the context of chemistry, only a few other classes of graphs have been considered. Here we study the spectrum of possible forced matching numbers for the grids $P_m \times P_n$, discuss the concept of a forcing set for some other specific classes of graphs, and show that the problem of finding the smallest forcing number of graphs is \NP--complete.

Resistance distance-based graph invariants of subdivisions and triangulations of graphs

2014-09-23

Yujun Yang , Douglas J. Klein

View PDF Chat

Resistance distance and the normalized Laplacian spectrum

2006-11-01

Haiyan Chen , Fuji Zhang

The spanning k-trees, perfect matchings and spectral radius of graphs

2021-10-04

Dandan Fan , Sergey Goryainov , Xueyi Huang +1 more

A $k$-tree is a spanning tree in which every vertex has degree at most $k$. In this paper, we provide a sufficient condition for the existence of a $k$-tree in … A $k$-tree is a spanning tree in which every vertex has degree at most $k$. In this paper, we provide a sufficient condition for the existence of a $k$-tree in a connected graph with fixed order in terms of the adjacency spectral radius and the signless Laplacian spectral radius, respectively. Also, we give a similar condition for the existence of a perfect matching in a balanced bipartite graph with fixed order and minimum degree.

View PDF Chat

Extremal pentagonal chains with respect to the Kirchhoff index

2022-09-16

Wensheng Sun , Yujun Yang

Some bounds on the zero forcing number of a graph

2017-12-06

Michael Gentner , Dieter Rautenbach

View PDF Chat

Forcing matchings on square grids

1998-08-01

Lior Pachter , Peter Kim

Full Control by Locally Induced Relaxation

2007-09-05

Daniel Burgarth , Vittorio Giovannetti

We demonstrate a scheme for controlling a large quantum system by acting on a small subsystem only. The local control is mediated to the larger system by some fixed coupling … We demonstrate a scheme for controlling a large quantum system by acting on a small subsystem only. The local control is mediated to the larger system by some fixed coupling Hamiltonian. The scheme allows us to transfer arbitrary and unknown quantum states from a memory to the large system (``upload access'') as well as the inverse (``download access''). We study the sufficient conditions of the coupling Hamiltonian and give lower bounds on the fidelities for downloading and uploading.

View PDF Chat

Computation of resistance distance with Kirchhoff index of body centered cubic structure

2024-02-06

Wasim Sajjad , Xiang-Feng Pan , Qura Tul Ain

The minimum forcing number for the torus and hypercube

2002-02-01

Matthew Riddle

Innate degree of freedom of a graph

1987-06-01

Douglas J. Klein , Milan Randić

Abstract For a Kekulé structure we consider the smallest number of placements of double bonds such that the full Kekulé structure on the given parent graph is fully determined. These … Abstract For a Kekulé structure we consider the smallest number of placements of double bonds such that the full Kekulé structure on the given parent graph is fully determined. These numbers for each Kekulé structure of the parent graph sum to a novel structural invariant F , called the degree of freedom of the graph. Some qualitative characteristics are identified, and it is noted that apparently it behaves differently from a couple of other invariants related to Kekulé structures.

Global forcing number of grid graphs

2007-01-01

Damir Vukičević , Tomislav Došlić

Let $G$ be a simple connected graph with a perfect matching. Let ${; ; ; \cal M}; ; ; (G)$ denote the set of all perfect matchings in $G$, and … Let $G$ be a simple connected graph with a perfect matching. Let ${; ; ; \cal M}; ; ; (G)$ denote the set of all perfect matchings in $G$, and $f: {; ; ; \cal M}; ; ; (G) \rightarrow \{; ; ; 0, 1\}; ; ; ^{; ; ; |E(G)|}; ; ; $ a characteristic function of perfect matchings of $G$. Any set $S \subseteq E(G)$ such that $f \left | _S \right .$ is an injection is called a global forcing set in $G$, and the cardinality of smallest such $S$ is called the global forcing number of $G$. In this paper we first establish lower bounds on this quantity and show how it can be computed for certain classes of composite graphs, and then we prove an explicit formula for global forcing number of the grid graph $R_{; ; ; p, q}; ; ; = P_p \times P_q$. We also briefly consider a vertex global forcing number of grid graphs and present an explicit formula for it. In the last section we give explicit formulas for global forcing numbers of complete graphs and discuss some further developments.

Extremal values and bounds for the zero forcing number

2016-07-11

Michael Gentner , Lúcia Draque Penso , Dieter Rautenbach +1 more

The Resistance Distance and Kirchhoff Index on Quadrilateral Graph and Pentagonal Graph

2019-01-01

Qun Liu

The quadrilateral graph Q(G) is obtained from G by replacing each edge in G with two parallel paths of length 1 and 3, whereas the pentagonal graph W(G) is obtained … The quadrilateral graph Q(G) is obtained from G by replacing each edge in G with two parallel paths of length 1 and 3, whereas the pentagonal graph W(G) is obtained from G by replacing each edge in G with two parallel paths of length 1 and 4. In this paper, closed-form formulas of resistance distance and Kirchhoff index for quadrilateral graph and pentagonal graph are obtained whenever G is an arbitrary graph.

View PDF Chat

On the forced matching numbers of bipartite graphs

2004-03-25

Peter D. Adams , Mohammad Mahdian , E. S. Mahmoodian

Combinatorial models and algorithms in chemistry. The expanded Wiener number?a novel topological index

1990-09-01

Serge S. Tratch , M. I. Stankevitch , N. S. Zefirov

Abstract An expanded form of the Wiener number is suggested for characterization of molecular graphs and structure‐property correlations. The simple, computer‐oriented method for counting of the novel index is briefly … Abstract An expanded form of the Wiener number is suggested for characterization of molecular graphs and structure‐property correlations. The simple, computer‐oriented method for counting of the novel index is briefly discussed.

Random Walks and Electric Networks

1984-01-01

Peter G. Doyle , J. Laurie Snell

Probability theory, like much of mathematics, is indebted to physics as a source of problems and intuition for solving these problems. Unfortunately, the level of abstraction of current mathematics often … Probability theory, like much of mathematics, is indebted to physics as a source of problems and intuition for solving these problems. Unfortunately, the level of abstraction of current mathematics often makes it difficult for anyone but an expert to appreciate this fact. Random Walks and Electric Networks looks at the interplay of physics and mathematics in terms of an example the relation between elementary electric network theory and random walks where the mathematics involved is at the college level.

View PDF Chat

The Hosoya polynomial decomposition for catacondensed benzenoid graphs

2008-02-22

Shou‐Jun Xu , Heping Zhang

On a novel eccentricity-based invariant of a graph

2016-11-04

Kexiang Xu , Kinkar Chandra Das , A. Dılek Maden

Proof of a conjecture on the zero forcing number of a graph

2016-06-14

Leihao Lu , Baoyindureng Wu , Zixing Tang

View PDF Chat

Efficient dominating sets in circulant graphs with domination number prime

2014-06-26

Yun-Ping Deng

A Graph Reduction Step Preserving Element-Connectivity and Applications

2009-01-01

Chandra Chekuri , Nitish Korula

View PDF Chat

Global Forcing Number of Benzenoid Graphs

2006-03-23

Tomislav Došlić

The Incidence Hopf Algebra of Graphs

2012-01-01

Brandon Humpert , Jeremy L. Martin

The graph algebra is a commutative, cocommutative, graded, connected incidence Hopf algebra, whose basis elements correspond to finite graphs, and whose Hopf product and coproduct admit simple combinatorial descriptions. We … The graph algebra is a commutative, cocommutative, graded, connected incidence Hopf algebra, whose basis elements correspond to finite graphs, and whose Hopf product and coproduct admit simple combinatorial descriptions. We give a new formula for the antipode in the graph algebra in terms of acyclic orientations; our formula contains many fewer terms than Takeuchi's and Schmitt's more general formulas for the antipode in an incidence Hopf algebra. Applications include several formulas (some old and some new) for evaluations of the Tutte polynomial.

View PDF Chat

The behavior of Wiener indices and polynomials of graphs under five graph decorations

2006-07-22

Weigen Yan , Bo‐Yin Yang , Yeong‐Nan Yeh

Generalized Wiener indices in hexagonal chains

2005-07-26

Sen‐Peng Eu , Bo‐Yin Yang , Yeong‐Nan Yeh

Abstract The Wiener index, or the Wiener number, also known as the “sum of distances” of a connected graph, is one of the quantities associated with a molecular graph that … Abstract The Wiener index, or the Wiener number, also known as the “sum of distances” of a connected graph, is one of the quantities associated with a molecular graph that correlates nicely to physical and chemical properties, and has been studied in depth. An index proposed by Schultz is shown to be related to the Wiener index for trees, and Ivan Gutman proposed a modification of the Schultz index with similar properties. We deduce a similar relationship between these three indices for catacondensed benzenoid hydrocarbons (graphs formed of concatenated hexagons, or hexagonal chains, or sometimes acenes). Indeed, we may define three families of generalized Wiener indices, which include the Schultz and Modified Schultz indices as special cases, such that similar explicit formulae for all generalized Wiener indices hold on hexagonal chains. We accomplish this by first giving a more refined proof of the formula for the standard Wiener index of a hexagonal chain, then extending it to the generalized Wiener indices via the notion of partial Wiener indices. Finally, we discuss possible extensions of the result. © 2005 Wiley Periodicals, Inc. Int J Quantum Chem, 2006

A Linear Algorithm for the Hyper-Wiener Index of Chemical Trees

2001-05-26

Roberto Aringhieri , Pierre Hansen , Federico Malucelli

An algorithm with a complexity linear in the number of vertices is proposed for the computation of the Hyper-Wiener index of chemical trees. This complexity is the best possible. Computational … An algorithm with a complexity linear in the number of vertices is proposed for the computation of the Hyper-Wiener index of chemical trees. This complexity is the best possible. Computational experience for alkanes is reported.

Comparison theorems on resistance distances and Kirchhoff indices of<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si15.gif" display="inline" overflow="scroll"><mml:mi>S</mml:mi></mml:math>,<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si16.gif" display="inline" overflow="scroll"><mml:mi>T</mml:mi></mml:math>-isomers

2014-05-21

Yujun Yang , Douglas J. Klein