Search

A balanced 2-partition of a graph is a bipartition $A,A^c$ of $V(G)$ such that $|A|=|A^c|$. Balogh, Clemen, and Lidick\'y conjectured that for every $K_4$-free graph on $n$ (even) vertices, there exists a balanced 2-partition $A,A^c$ such that $\max\{e(A),e(A^c)\}\leq n^2/16$ edges. In this paper, we present a family of counterexamples to the conjecture and provide a new upper bound ($0.074n^2$) for every sufficiently large even integer $n$., Comment: 18 pages, 3 figures

Key network motifs searching in complex networks is one of the crucial aspects of network analysis. There has been a series of insightful findings and valuable applications for various scenarios through the analysis of network structures. However, in dynamic systems, slight changes in the choice of dynamic equations and parameters can alter the significance of motifs. The known methods are insufficient to address this issue effectively. In this paper, we introduce a concept of perturbation energy based on the system's Jacobian matrix, and define motif centrality for dynamic systems by seamlessly integrating network topology with dynamic equations. Through simulations, we observe that the key motifs obtained by the proposed energy method present better effective and accurate than them by integrating network topology methods, without significantly increasing algorithm complexity. The finding of key motifs can be used to apply for system control, such as formulating containment policies for the spread of epidemics and protecting fragile ecosystems. Additionally, it makes substantial contribution to a deeper understanding of concepts in physics, such as signal propagation and system's stability., Comment: 15 pages, 7 figures

This paper focuses on extensions of the classic Erd\H{o}s-Gallai Theorem for the set of weighted function of each edge in a graph. The weighted function of an edge $e$ of an $n$-vertex uniform hypergraph $\mathcal{H}$ is defined to a special function with respect to the number of edges of the longest Berge path containing $e$. We prove that the summation of the weighted function of all edges is at most $n$ for an $n$-vertex uniform hypergraph $\mathcal{H}$ and characterize all extremal hypergraphs that attain the value, which strengthens and extends the hypergraph version of the classic Erd\H{o}s-Gallai Theorem., Comment: 19 pages

In this paper, we present a sharp upper bound for the spectral radius of an $n$-vertex graph without $F$-minor for sufficient large $n$, where $F$ is obtained from the complete graph $K_r$ by deleting disjointed paths. Furthermore, the graphs which achieved the sharp bound are characterized. This result may be regarded to be an extended revision of the number of edges in an $n$-vertex graph without $F$-minor., Comment: 18 pages, 1 figurs

Let $G$ be an simple graph of order $n$ whose adjacency eigenvalues are $\lambda_1\ge\dots\ge\lambda_n$. The HL--index of $G$ is defined to be $R(G)= \max\{|\lambda_{h}|, |\lambda_{l}|\}$ with $h=\left\lfloor\frac{n+1}{2}\right\rfloor$ and $ l=\left\lceil\frac{n+1}{2}\right\rceil.$ Mohar conjectured that $R(G)\le 1$ for every planar subcubic graph $G$. In this note, we prove that Mohar's Conjecture holds for every $K_4$-minor-free subcubic graph. Note that a $K_4$-minor-free graph is also called a series--parallel graph. In addition, $R(G)\le 1$ for every subcubic graph $G$ which contains a subgraph $K_{2,3}$., Comment: 6 pages, 1figure

Various disasters stem from minor perturbations, such as the spread of infectious diseases, cascading failure in power grids, etc. Analyzing perturbations is crucial for both theoretical and application fields. Previous researchers have proposed basic propagation patterns for perturbation and explored the impact of basic network motifs on the collective response to these perturbations, However, the current framework is limited in its ability to decouple interactions, and therefore cannot analyze more complex structures. In this article, we establish an effective, robust and powerful propagation framework under a general dynamic model. This framework reveals common and dense network motifs that exert a critical influence on signal propagation, often spanning orders of magnitude compared with conclusions generated by previous work. Moreover, our framework provides a new approach to understand the fundamental principles of complex systems and the negative feedback mechanism, which is of great significance for research of system controlling and network resilience., Comment: 15 pages, 3 figures

Stanley introduced the concept of chromatic symmetric functions of graphs which extends and refines the notion of chromatic polynomials of graphs, and asked whether trees are determined up to isomorphism by their chromatic symmetric functions. Using the technique of differentiation with respect to power-sum symmetric functions, we give a positive answer to Stanley's question for the class of trees with exactly two vertices of degree at least 3. In addition, we prove that for any tree $T$, the generalized degree sequence for subtrees of $T$ is determined by the chromatic symmetric function of $T$, providing evidence to a conjecture of Crew.

Let $A(G)$ and $D(G)$ be the adjacency and degree matrices of a simple graph $G$ on $n$ vertices, respectively. The \emph{$A_\alpha$-spectral radius} of $G$ is the largest eigenvalue of $A_\alpha (G)=\alpha D(G)+(1-\alpha)A(G)$ for a real number $\alpha \in[0,1]$. In this paper, for $\alpha \in (0,1)$, we obtain a sharp upper bound for the $A_\alpha$-spectral radius of graphs on $n$ vertices without a subgraph isomorphic to a liner forest for $n$ large enough and characterize all graphs which attain the upper bound. As a result, we completely obtain the maximum signless Laplacian spectral radius of graphs on $n$ vertices without a subgraph isomorphic to a liner forest for $n$ large enough., Comment: 18 pages

For a graph $G$, the unraveled ball of radius $r$ centered at a vertex $v$ is the ball of radius $r$ centered at $v$ in the universal cover of $G$. We obtain a lower bound on the weighted spectral radius of unraveled balls of fixed radius in a graph with positive weights on edges, which is used to present an upper bound on the $s$-th (where $s\ge 2$) smallest normalized Laplacian eigenvalue of irregular graphs under minor assumptions. Moreover, when $s=2$, the result may be regarded as an Alon--Boppana type bound for a class of irregular graphs., Comment: 12 pages

Let $Q(G)=D(G)+A(G)$ be the signless Laplacian matrix of a simple graph of order $n$, where $D(G)$ and $A(G)$ are the degree diagonal matrix and the adjacency matrix of $G$, respectively. In this paper, we present a sharp upper bound for the signless spectral radius of $G$ without any tree and characterize all extremal graphs which attain the upper bound, which may be regarded as a spectral extremal version for the famous Erd\H{o}s-S\'{o}s conjecture., Comment: 12 pages

Let $G$ be a graph of order $n$, and let $A(G)$ and $D(G)$ be the adjacency matrix and the degree matrix of $G$ respectively. Define the convex linear combinations $A_\alpha (G)$ of $A (G)$ and $D (G) $ by $$A_\alpha (G)=\alpha D(G)+(1-\alpha)A(G)$$ for any real number $0\leq\alpha\leq1$. The \emph{$\alpha$-index} of $G$ is the largest eigenvalue of $A_\alpha(G)$. In this paper, we determine the maximum $\alpha$-index and characterize all extremal graphs for $K_r$ minor-free graphs, $K_{s,t}$ minor-free graphs, and star-forest-free graphs for any $0<\alpha<1$ by unified eigenvector approach, respectively., Comment: 16 pages

The bipartite Tur\'{a}n number of a graph $H$, denoted by $ex(m,n; H)$, is the maximum number of edges in any bipartite graph $G=(X,Y; E)$ with $|X|=m$ and $|Y|=n$ which does not contain $H$ as a subgraph. In this paper, we determined $ex(m,n; F_{\ell})$ for arbitrary $\ell$ and appropriately large $n$ with comparing to $m$ and $\ell$, where $F_\ell$ is a linear forest which consists of $\ell$ vertex disjoint paths. Moreover, the extremal graphs have been characterized. Furthermore, these results are used to obtain the maximum spectral radius of bipartite graphs which does not contain $F_{\ell}$ as a subgraph and characterize all extremal graphs which attain the maximum spectral radius., Comment: 18 pages

We call a real multi-dimensional array a {\em tensor} for short. In enumerating vertices of the polytopes of stochastic tensors, different approaches have been used: {(1)} Combinatorial method via Latin squares; {(2)} Analytic (topological) approach by using hyperplanes; {(3)} Computational geometry (polytope theory) approach; and (4) Optimization (linear programming) approach. As all these approaches are worthy of consideration and investigation in the enumeration problem, various bounds have been obtained. This note is to compare the existing upper bounds arose from different approaches., Comment: 9 pages

The subtrees and BC-subtrees (subtrees where any two leaves are at even distance apart) have been extensively studied in recent years. Such structures, under special constraints on degrees, have applications in many fields. Through an approach based on generating functions, we present recursive algorithms for enumerating various subtrees and BC-subtrees of maximum degree $\leq k$ in trees. The algorithms are illustrated through detailed examples. We also briefly discuss, in trees, the densities of subtrees (resp.~BC-subtrees) of maximum degree $\leq k(\geq 2)$ among all subtrees (resp.~BC-subtrees)., Comment: 24 pages, 5 figures

A connected graph $G$ is said to be $k$-connected if it has more than $k$ vertices and remains connected whenever fewer than $k$ vertices are deleted. In this paper, for a connected graph $G$ with sufficiently large order, we present a tight sufficient condition for $G$ with fixed minimum degree to be $k$-connected based on the $Q$-index. Our result can be viewed as a spectral counterpart of the corresponding Dirac type condition., Comment: 11 pages. arXiv admin note: text overlap with arXiv:2109.07347

For $0\leq \alpha < 1$, the $\mathcal{A}_{\alpha}$-spectral radius of a $k$-uniform hypergraph $G$ is defined to be the spectral radius of the tensor $\mathcal{A}_{\alpha}(G):=\alpha \mathcal{D}(G)+(1-\alpha) \mathcal{A}(G)$, where $\mathcal{D}(G)$ and $A(G)$ are diagonal and the adjacency tensors of $G$ respectively. This paper presents several lower bounds for the difference between the $\mathcal{A}_{\alpha}$-spectral radius and an average degree $\frac{km}{n}$ for a connected $k$-uniform hypergraph with $n$ vertices and $m$ edges, which may be considered as the measures of irregularity of $G$. Moreover, two lower bounds on the $\mathcal{A}_{\alpha}$-spectral radius are obtained in terms of the maximum and minimum degrees of a hypergraph., Comment: 22 pages

Let $F_{a_1,\dots,a_k}$ be a graph consisting of $k$ cycles of odd length $2a_1+1,\dots, 2a_k+1$, respectively which intersect in exactly a common vertex, where $k\geq1$ and $a_1\ge a_2\ge \cdots\ge a_k\ge 1$. In this paper, we present a sharp upper bound for the signless Laplacian spectral radius of all $F_{a_1,\dots,a_k}$-free graphs and characterize all extremal graphs which attain the bound. The stability methods and structure of graphs associated with the eigenvalue are adapted for the proof., Comment: 11 pages

In this paper, we present two sharp upper bounds for the spectral radius of (bipartite) graphs with forbidden a star forest and characterize all extremal graphs. Moreover, the minimum least eigenvalue of the adjacency matrix of graph with forbidden a star forest and all extremal graphs for graphs are obtained., Comment: 15 pages

The distance energy of a simple connected graph $G$ is defined as the sum of absolute values of its distance eigenvalues. In this paper, we mainly give a positive answer to a conjecture of distance energy of clique trees proposed by Lin, Liu and Lu [H.~Q.~ Lin, R.~F.~Liu, X.~W.~Lu, The inertia and energy of the distance matrix of a connected graph, {\it Linear Algebra Appl.,} 467 (2015), 29-39.], Comment: 10 pages, 1 figure

This paper is concerned with the extreme points of the polytopes of stochastic tensors. By a tensor we mean a multi-dimensional array over the real number field. A line-stochastic tensor is a nonnegative tensor in which the sum of all entries on each line (i.e., one free index) is equal to 1; a plane-stochastic tensor is a nonnegative tensor in which the sum of all entries on each plane (i.e., two free indices) is equal to 1. In enumerating extreme points of the polytopes of line- and plane-stochastic tensors of order 3 and dimension $n$, we consider the approach by linear optimization and present new lower and upper bounds. We also study the coefficient matrices that define the polytopes., Comment: 12 pages

The Steiner distance of vertices in a set $S$ is the minimum size of a connected subgraph that contain these vertices. The sum of the Steiner distances over all sets $S$ of cardinality $k$ is called the Steiner $k$-Wiener index and studied as the natural generalization of the famous Wiener index in chemical graph theory. In this paper we study the extremal structures, among trees with a given segment sequence, that maximize or minimize the Steiner $k$-Wiener index. The same extremal problems are also considered for trees with a given number of segments., Comment: 10 pages

Let $G_1$ and $G_2$ be two simple connected graphs. The invariant \textit{coronal} of graph is used in order to determine the $\alpha$-eigenvalues of four different types of graph equations that are $G_1 \circ G_2, G_1\lozenge G_1$ and the other two`s are $G_1 \odot G_2$ and $G_1 \circleddash G_2$ which are obtained using the $R$-graph of $G_1$. As an application we construct infinitely many pairs of non-isomorphic $\alpha$-Isospectral graph., Comment: 15 pages, 3figures

Tur\'{a}n type extremal problem is how to maximize the number of edges over all graphs which do not contain fixed forbidden subgraphs. Similarly, spectral Tur\'{a}n type extremal problem is how to maximize (signless Laplacian) spectral radius over all graphs which do not contain fixed subgraphs. In this paper, we first present a stability result for $k\cdot P_3$ in terms of the number of edges and then determine all extremal graphs maximizing the signless Laplacian spectral radius over all graphs which do not contain a fixed linear forest with at most two odd paths or $k\cdot P_3$ as a subgraph, respectively., Comment: 14 pagew, 2 figures. arXiv admin note: text overlap with arXiv:1801.06763

Subtree number index $\emph{STN}(G)$ of a graph $G$ is the number of nonempty subtrees of $G$. It is a structural and counting based topological index that has received more and more attention in recent years. In this paper we first obtain exact formulas for the expected values of subtree number index of random polyphenylene and spiro chains, which are molecular graphs of a class of unbranched multispiro molecules and polycyclic aromatic hydrocarbons. Moreover, we establish a relation between the expected values of the subtree number indices of a random polyphenylene and its corresponding hexagonal squeeze. We also present the average values for subtree number indices with respect to the set of all polyphenylene and spiro chains with $n$ hexagons., Comment: 16pages, 3 figures

The Wiener index of a connected graph is the sum of the distance of all pairs of distinct vertices. It was introduced by Wiener in 1947 to analyze some aspects of branching by fitting experimental data for several properties of alkane compounds. Denote by $\mathcal{U}_{n,r}$ the set of unicyclic graphs with $n$ vertices and $r$ vertices of even degree. In this paper we present a structural result on the graphs in $\mathcal{U}_{n,r}$ with minimum Wiener index and completely characterize such graphs when $ r\leq \frac{n+3}{2}$., Comment: 13 pages, 4figures

A graph on $2k+1$ vertices consisting of $k$ triangles which intersect in exactly one common vertex is called a $k$-fan and denoted by $F_k$. This paper aims to determine the graphs of order $n$ that have the maximum (adjacency) spectral radius among all graphs containing no $F_k$, for $n$ sufficiently large., Comment: 17 pages

The eccentricity of a vertex $v$ in a graph $G$ is the maximum distance from $v$ to any other vertex. The vertices whose eccentricity are equal to the diameter (the maximum eccentricity) of $G$ are called peripheral vertices. In trees the eccentricity at $v$ can always be achieved by the distance from $v$ to a peripheral vertex. From this observation we are motivated to introduce normality of a vertex $v$ as the minimum distance from $v$ to any peripheral vertex. We consider the properties of the normality as well as the middle part of a tree with respect to this concept. Various related observations are discussed and compared with those related to the eccentricity. Then, analogous to the sum of eccentricities we consider the sum of normalities. After briefly discussing the extremal problems in general graphs we focus on trees and trees under various constraints. As opposed to the path and star in numerous extremal problems, we present several interesting and unexpected extremal structures. Lastly we consider the difference between eccentricity and normality, and the sum of these differences. We also introduce some unsolved problems in the context., Comment: 14 pages 9figures

In this paper, we prove that if $G$ is a $K_{2,t}$-minor free graph of order $n\geq t^2+4t+1$ with $t\geq 3$, the signless Laplacian spectral radius $q(G)\leq \frac{1}{2}(n+2t-2+\sqrt{(n-2t+2)^2+8t-8}\ )$ with equality if and only if $n\equiv 1~(\mathrm{mod}~t)$ and $G=F_{2,t}(n)$, where $F_{s,t}(n):=K_{s-1}\vee (p\cdot K_t\cup K_r)$ for $n-s+1=pt+r$ and $0\leq r

The Erd\H{o}s-Gallai Theorem states that every graph of average degree more than $l-2$ contains a path of order $l$ for $l\ge 2$. In this paper, we obtain a stability version of the Erd\H{o}s-Gallai Theorem in terms of minimum degree. Let $G$ be a connected graph of order $n$ and $F=(\bigcup_{i=1}^kP_{2a_i})\bigcup(\bigcup_{i=1}^lP_{2b_i+1})$ be $k+l$ disjoint paths of order $2a_1, \ldots, 2a_{k}, 2b_1+1, \ldots, 2b_l+1,$ respectively, where $k\ge 0$, $0\le l\le 2$, and $k+l\geq 2$. If the minimum degree $\delta(G)\ge \sum_{i=1}^ka_i+\sum_{i=1}^lb_i-1$, then $F\subseteq G$ except several classes of graphs for sufficiently large $n$, which extends and strengths the results of Ali and Staton for an even path and Yuan and Nikiforov for an odd path., Comment: 21 pages, 4 figures

For a given graph $H$, the anti-Ramsey number of $H$ is the maximum number of colors in an edge-coloring of a complete graph which does not contain a rainbow copy of $H$. In this paper, we extend the decomposition family of graphs to the decomposition family sequence of graphs and show that $K_5$ is determined by its decomposition family sequence. Based on this new graph notation, we determine the anti-Ramsey numbers for new families of graphs, including the Petersen graph, vertex-disjoint union of cliques, etc., and characterize the extremal colorings., Comment: 20 pages, 3 figures

It is known that complete multipartite graphs are determined by their distance spectrum but not by their adjacency spectrum. The Seidel spectrum of a graph $G$ on more than one vertex does not determine the graph, since any graph obtained from $G$ by Seidel switching has the same Seidel spectrum. We consider $G$ to be determined by its Seidel spectrum, up to switching, if any graph with the same spectrum is switching equivalent to a graph isomorphic to $G$. It is shown that any graph which has the same spectrum as a complete $k$-partite graph is switching equivalent to a complete $k$-partite graph, and if the different partition sets sizes are $p_1,\ldots, p_l$, and there are at least three partition sets of each size $p_i$, $i=1,\ldots, l$, then $G$ is determined, up to switching, by its Seidel spectrum. Sufficient conditions for a complete tripartite graph to be determined by its Seidel spectrum are discussed, and a conjecture is made on complete tripartite graphs on more than 18 vertices., Comment: 12 page 2 figures

Motivated from the study of eccentricity, center, and sum of eccentricities in graphs and trees, we introduce several new distance-based global and local functions based on the smallest distance from a vertex to some leaf (called the `uniformity' at that vertex). Some natural extremal problems on trees are considered. Then the middle parts of a tree is discussed and compared with the well-known center of a tree. The values of the global functions are also compared with the sum of eccentricities and some sharp bounds are established. Last but not the least, we show that the difference between the eccentricity and the uniformity, when considered as a local function, behaves in a very similar way as the eccentricity itself., Comment: 12 pages

In this paper, we present an equitable partition theorem of tensors, which gives the relations between $H$-eigenvalues of a tensor and its quotient equitable tensor and extends the equitable partitions of graphs to hypergraphs. Furthermore, with the aid of it, some properties and $H$-eigenvalues of the generalized power hypergraphs are obtained, which extends some known results, including some results of Yuan, Qi and Shao., Comment: 16 pages

For a symmetric bivariable function $f(x,y)$, let the {\it connectivity function} of a connected graph $G$ be $M_f(G)=\sum_{uv\in E(G)}f(d(u),d(v))$, where $d(u)$ is the degree of vertex $u$. In this paper, we prove that for an escalating (de-escalating) function $f(x,y)$, there exists a BFS-graph with the maximum (minimum) connectivity function $M_f(G)$ among all graphs with a $c-$cyclic degree sequence $\pi=(d_1,d_2, \ldots, d_n)$ and $d_n=1$, and obtain the majorization theorem for connectivity function for unicyclic and bicyclic degree sequences. Moreover, some applications of graph invariants based on degree are included., Comment: 23 pages

Let $C_{v}(k;T)$ be the number of the closed walks of length $k$ starting at vertex $v$ in a tree $T$. We prove that for a given tree degree sequence $\pi$, then for any tree with degree sequence $\pi$, the sequence $C(k;T)\equiv(C_{v}(k;T), v\in V(T))$ is weakly majorized by the sequence $C(k, T_{\pi}^*)\equiv C(k, T_{\pi}^*, v\in V(T^*))$, where $T_{\pi}^*$ is the greedy tree corresponding to $\pi$. In addition, for two trees degree sequences $\pi,~\pi'$, if $\pi$ is majorized by $\pi'$, then $C(k;T_{\pi}^*)$ is weakly majorized by $C(k;T_{\pi'}^*)$., Comment: 16 pages 2 figures, Applied Mathematics and Computation, 2018

Let $F_{p,q}$ be the generalized friendship graph $K_1\bigvee (pK_q)$ on $pq+1$ vertices obtained by joining a vertex to all vertices of $p$ disjoint copies of the complete graph $K_q$ on $q$ vertices. In this paper, we prove that $F_{p,q}$ is determined by its normalized Laplacian spectrum if and only if $q\ge 2$, or $q=1$ and $p\le 2$., Comment: 10 pages, Linear Algebra and its Applications, 2018

The Tur\'an type extremal problem asks to maximize the number of edges over all graphs which do not contain fixed subgraphs. Similarly, the spectral Tur\'an type extremal problem asks to maximize spectral radius of all graphs which do not contain fixed subgraphs. In this paper, we determine the maximum spectral radius of all graphs without containing a linear forest as a subgraph and characterize all corresponding extremal graphs. In addition, the maximum number of edges and spectral radius of all bipartite graphs without containing $k\cdot P_3$ as a subgraph are obtained and all extremal graphs are also characterized. Moreover, some relations between Tu\'an type extremal problems and spectral Tur\'an type extremal problems are discussed., Comment: 15

A balanced bipartite graph $G$ is said to be $2p$-Hamilton-biconnected if for any balanced subset $W$ of size $2p$ of $V(G)$, the subgraph induced by $V(G)\backslash W$ is Hamilton-biconnected. In this paper, we prove that "Let $p\geq0$ and $G$ be a balanced bipartite graph of order $2n$ with minimum degree $\delta(G)\geq k$, where $n\geq 2k-p+2$ and $k\geq p$. If the number of edges $ e(G)>n(n-k+p-1)+(k+2)(k-p+1), $ then $G$ is $2p$-Hamilton-biconnected except some exceptions." Furthermore, this result is used to present two new spectral conditions for a graph to $2p$-Hamilton-biconnected. Moreover, the similar results are also presented for nearly balanced bipartite graphs., Comment: 22 pages, 2 figures

In this paper, we present several upper bounds for the adjacency and signless Laplacian spectral radii of uniform hypergraphs in terms of degree sequences., Comment: 10 pages

Hyper-Wiener index was introduced as one of the main generalizations of the well known Wiener index. Through the years properties of the Wiener index have been extensively studied in both Mathematics and Chemistry. The Hyper-Wiener index, although received much attention, is far from being thoroughly examined due to its complex definition. We consider the local version of the Hyper-Wiener index ($WW(G)$), defined as $ww_G(v)=\sum\limits_{u\in V(G)}(d^2(u,v)+d(u,v))$ for a vertex $v$ in a graph $G$, in trees. For established results on the Wiener index ($W(.)$), we present analogous studies on $WW(.)$. In addition to interesting observations, some conjectures and questions are also proposed., Comment: 16 pages, 4figures, 3 tables

This paper is devoted to the study of lower and upper bounds for the number of vertices of the polytope of $n\times n\times n$ stochastic tensors (i.e., triply stochastic arrays of dimension $n$). By using known results on polytopes (i.e., the Upper and Lower Bound Theorems), we present some new lower and upper bounds. We show that the new upper bound is tighter than the one recently obtained by Chang, Paksoy and Zhang [Ann. Funct. Anal. 7 (2016), no.~3, 386--393] and also sharper than the one in Linial and Luria's [Discrete Comput. Geom. 51 (2014), no.~1, 161--170]. We demonstrate that the analog of the lower bound obtained in such a way, however, is no better than the existing ones.

The Erd\H{o}s-S\'{o}s Conjecture states that every graph with average degree more than $k-2$ contains all trees of order $k$ as subgraphs. In this paper, we consider a variation of the above conjecture: studying the maximum size of an $(n,m)$-bipartite graph which does not contain all $(k,l)$-bipartite trees for given integers $n\ge m$ and $k\ge l$. In particular, we determine that the maximum size of an $(n,m)$-bipartite graph which does not contain all $(n,m)$-bipartite trees as subgraphs (or all $(k,2)$-bipartite trees as subgraphs, respectively). Furthermore, all these extremal graphs are characterized., Comment: 22 pages 2figures

The Tur\'{a}n number of a graph $H$, $ex(n,H)$, is the maximum number of edges in any graph of order $n$ which does not contain $H$ as a subgraph. Lidick\'{y}, Liu and Palmer determined $ex(n, F_m)$ for $n$ sufficiently large and proved that the extremal graph is unique, where $F_m$ is disjoint paths of $P_{k_1}, \ldots, P_{k_m}$ [Lidick\'{y},B., Liu,H. and Palmer,C. (2013). On the Tur\'{a}n number of forests. Electron. J. Combin. 20(2) Paper 62, 13 pp]. In this paper, by mean of a different approach, we determine $ex(n, F_m)$ for all integers $n$ with minor conditions, which extends their partial results. Furthermore, we partly confirm the conjecture proposed by Bushaw and Kettle for $ex(n, k\cdot P_l)$ [Bushaw,N. and Kttle,N. (2011) Tur\'{a}n numbers of multiple paths and equibipartite forests. Combin. Probab. Comput. 20 837-853]. Moreover, we show that there exist two family graphs $F_m$ and $F_m^{\prime}$ such that $ex(n, F_m)=ex(n, F_m^{\prime})$ for all integers $n$, which is related to an old problem of Erd\H{o}s and Simonovits., Comment: 19 pages

The atom-bond connectivity (ABC) index is a degree-based topological index. It was introduced due to its applications in modeling the properties of certain molecular structures and has been since extensively studied. In this note, we examine the influence on the extremal values of the ABC index by various graph parameters. More specifically, we consider the maximum ABC index of connected graphs of given order, with fixed independence number, number of pendent vertices, chromatic number and edge-connectivity respectively. We provide characterizations of extremal structures as well as some conjectures. Numerical analysis of the extremal values are also presented., Comment: 16 pages, 4figures

In this paper, we obtain a sharp upper bound for the spectral radius of a nonnegative matrix. This result is used to present upper bounds for the adjacency spectral radius, the Laplacian spectral radius, the signless Laplacian spectral radius, the distance spectral radius, the distance Laplacian spectral radius, the distance signless Laplacian spectral radius of a graph or a digraph. These results are new or generalize some known results., Comment: 16 pages in Czechoslovak Math. J., 2016. arXiv admin note: text overlap with arXiv:1507.07059

The Kirchhoff index $Kf(G)$ of a graph $G$ is the sum of resistance distances between all unordered pairs of vertices, which was introduced by Klein and Randi\'c. In this paper we characterized all extremal graphs with Kirchhoff index among all graphs obtained by deleting $p$ edges from a complete graph $K_n$ with $p\leq\lfloor\frac{n}{2}\rfloor$ and obtained a sharp upper bound on the Kirchhoff index of these graphs. In addition, all the graphs with the first to ninth maximal Kirchhoff indices are completely determined among all connected graphs of order $n>27$., Comment: 21 pages, 3 figures, International Journal of Computer Mathematics, 2016

Let $\mathcal{L}(T,\lambda)=\sum_{k=0}^n(-1)^{k}c_{k}(T)\lambda^{n-k}$ be the characteristic polynomial of its Laplacian matrix of a tree $T$. This paper studied some properties of the generating function of the coefficients sequence $(c_0, \cdots, c_n)$ which are related with the matching polynomials of division tree of $T$. These results, in turn, are used to characterize all extremal trees having the minimum Laplacian coefficient generation function and the minimum incidence energy of trees with described maximum degree, respectively., Comment: 32 pages 2 figures in J. Comb. Optim. 2016

The Tur\'{a}n number of a graph $H$, $ex(n,H)$, is the maximum number of edges in a simple graph of order $n$ which does not contain $H$ as a subgraph. Let $k\cdot P_3$ denote $k$ disjoint copies of a path on $3$ vertices. In this paper, we determine the value $ex(n, k\cdot P_3)$ and characterize all extremal graphs. This extends a result of Bushaw and Kettle [N. Bushaw and N. Kettle, Tur\'{a}n Numbers of multiple and equibipartite forests, Combin. Probab. Comput., 20(2011) 837-853.], which solved the conjecture proposed by Gorgol in [I. Gorgol. Tur\'{a}n numbers for disjoint copies of graphs. {\it Graphs Combin.}, 27 (2011) 661-667.]., Comment: 15 pages

The terminal Wiener index of a tree is the sum of distances for all pairs of pendent vertices, which recently arises in the study of phylogenetic tree reconstruction and the neighborhood of trees. This paper presents a sharp upper and lower bounds for the terminal Wiener index in terms of its order and diameter and characterizes all extremal trees which attain these bounds. In addition, we investigate the properties of extremal trees which attain the maximum terminal Wiener index among all trees of order $n$ with fixed maximum degree., Comment: 15 pages, 1 figure

This paper surveys some recent results and progress on the extremal prob- lems in a given set consisting of all simple connected graphs with the same graphic degree sequence. In particular, we study and characterize the extremal graphs having the maximum (or minimum) values of graph invariants such as (Laplacian, p-Laplacian, signless Laplacian) spectral radius, the first Dirichlet eigenvalue, the Wiener index, the Harary index, the number of subtrees and the chromatic number etc, in given sets with the same tree, unicyclic, graphic degree sequences. Moreover, some conjectures are included., Comment: 22 pages, 2 figures. arXiv admin note: text overlap with arXiv:1209.2188 by other authors