Search

The general position problem is to find the cardinality of a largest vertex subset S such that no triple of vertices of S lie on a common geodesic. For a connected graph G, the cardinality of S is denoted by gp(G) and called gp-number (or general position number) of G. In the paper, we obtain an upper bound and a lower bound regarding gp-number in all cactus with k cycles and t pendant edges. Furthermore, the gp-number of wheel graph is determined.

For a graph $G$, the first multiplicative Zagreb index $\prod_1(G) $ is the product of squares of vertex degrees, and the second multiplicative Zagreb index $\prod_2(G) $ is the product of products of degrees of pairs of adjacent vertices. In this paper, we explore graphs with extremal $\Pi_{1}(G)$ and $\Pi_{2}(G)$ in terms of (edge) connectivity and pendant vertices. The corresponding extremal graphs are characterized with given connectivity at most $k$ and $p$ pendant vertices. In addition, the maximum and minimum values of $\prod_1(G) $ and $\prod_2(G) $ are provided. Our results extend and enrich some known conclusions., Comment: arXiv admin note: substantial text overlap with arXiv:1704.06943

The first Zagreb index of a graph $G$ is the sum of the square of every vertex degree, while the second Zagreb index is the sum of the product of vertex degrees of each edge over all edges. In our work, we solve an open question about Zagreb indices of graphs with given number of cut vertices. The sharp lower bounds are obtained for these indices of graphs in $\mathbb{V}_{n,k}$, where $\mathbb{V}_{n, k}$ denotes the set of all $n$-vertex graphs with $k$ cut vertices and at least one cycle. As consequences, those graphs with the smallest Zagreb indices are characterized., Comment: Accepted by Journal of Mathematical Analysis and Applications

The energy of a graph $G$, denoted by $E(G)$, is defined as the sum of the absolute values of all eigenvalues of $G$. Let $n$ be an even number and $\mathbb{U}_{n}$ be the set of all conjugated unicyclic graphs of order $n$ with maximum degree at most $3$. Let $S_n^{\frac{n}{2}}$ be the radialene graph obtained by attaching a pendant edge to each vertex of the cycle $C_{\frac{n}{2}}$. In [Y. Cao et al., On the minimal energy of unicyclic H\"{u}ckel molecular graphs possessing Kekul\'{e} structures, Discrete Appl. Math. 157 (5) (2009), 913--919], Cao et al. showed that if $n\geq 8$, $S_n^{\frac{n}{2}}\ncong G\in \mathbb{U}_{n}$ and the girth of $G$ is not divisible by $4$, then $E(G)>E(S_n^{\frac{n}{2}})$. Let $A_n$ be the unicyclic graph obtained by attaching a $4$-cycle to one of the two leaf vertices of the path $P_{\frac{n}{2}-1}$ and a pendent edge to each other vertices of $P_{\frac{n}{2}-1}$. In this paper, we prove that $A_n$ is the unique unicyclic graph in $\mathbb{U}_{n}$ with minimal energy., Comment: 20 pages

The authors Mili$\breve{c}$evi$\acute{c}$ et al. introduced the reformulated Zagreb indices, which is a generalization of classical Zagreb indices of chemical graph theory. In the paper, we characterize the extremal properties of the first reformulated Zagreb index. We first introduce some graph operations which increase or decrease this index. Furthermore, we will determine the extremal tricyclic graphs with minimum and maximum the first Zagreb index by these graph operations., Comment: 8 pages,2 figures

Let G be a simple graph of order $n$ and $\mu_1,\mu_2,\ldots,\mu_n$ the roots of its matching polynomial. The matching energy of $G$ is defined as the sum $\sum_{i=1}^n|\mu_i|$. Let $K_{n-1,1}^k$ be the graph obtained from $K_1\cup K_{n-1}$ by adding $k$ edges between $V(K_1)$ and $V(K_{n-1})$. In this paper, we show that $K_{n-1,1}^k$ has maximum matching energy among all connected graph with order $n$ and edge connectivity $k$., Comment: 9 pages

The energy of a simple graph $G$, denoted by $E(G)$, is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Let $C_n$ denote the cycle of order $n$ and $P^{6,6}_n$ the graph obtained from joining two cycles $C_6$ by a path $P_{n-12}$ with its two leaves. Let $\mathscr{B}_n$ denote the class of all bipartite bicyclic graphs but not the graph $R_{a,b}$, which is obtained from joining two cycles $C_a$ and $C_b$ ($a, b\geq 10$ and $a \equiv b\equiv 2\, (\,\textmd{mod}\, 4)$) by an edge. In [I. Gutman, D. Vidovi\'{c}, Quest for molecular graphs with maximal energy: a computer experiment, {\it J. Chem. Inf. Sci.} {\bf41}(2001), 1002--1005], Gutman and Vidovi\'{c} conjectured that the bicyclic graph with maximal energy is $P^{6,6}_n$, for $n=14$ and $n\geq 16$. In [X. Li, J. Zhang, On bicyclic graphs with maximal energy, {\it Linear Algebra Appl.} {\bf427}(2007), 87--98], Li and Zhang showed that the conjecture is true for graphs in the class $\mathscr{B}_n$. However, they could not determine which of the two graphs $R_{a,b}$ and $P^{6,6}_n$ has the maximal value of energy. In [B. Furtula, S. Radenkovi\'{c}, I. Gutman, Bicyclic molecular graphs with the greatest energy, {\it J. Serb. Chem. Soc.} {\bf73(4)}(2008), 431--433], numerical computations up to $a+b=50$ were reported, supporting the conjecture. So, it is still necessary to have a mathematical proof to this conjecture. This paper is to show that the energy of $P^{6,6}_n$ is larger than that of $R_{a,b}$, which proves the conjecture for bipartite bicyclic graphs. For non-bipartite bicyclic graphs, the conjecture is still open., Comment: 9 pages