Unicyclic and bicyclic graphs having minimum degree distance

In this paper characterizations of connected unicyclic and bicyclic graphs in terms of the degree sequence, as well as the graphs in these classes minimal with respect to the degree distance are given.     

Reciprocal complementary Wiener numbers of trees, unicyclic graphs and bicyclic graphs

The reciprocal complementary Wiener number of a connected graph G is defined as

where V(G) is the vertex set, d(u,v|G) is the distance between vertices u and v, d is the diameter of G. We determine the trees with the smallest, the second smallest and the third smallest reciprocal complementary Wiener numbers, and the unicyclic and bicyclic graphs with the smallest and the second smallest reciprocal complementary Wiener numbers.     

The minimum degree distance of graphs of given order and size

In this note, we study the degree distance of a graph which is a degree analogue of the Wiener index. Given n and e, we determine the minimum degree distance of a connected graph of order n and size e.     

On the eccentric distance sum of trees and unicyclic graphs

Let G be a simple connected graph with the vertex set V(G). The eccentric distance sum of G is defined as ξd(G)=_∑v∈V(G)ε(v)DG(v), where ε(v) is the eccentricity of the vertex v and DG(v)=_∑u∈V(G)d(u,v) is the sum of all distances from the vertex v. In this paper we characterize the extremal unicyclic graphs among n-vertex unicyclic graphs with given girth having the minimal and second minimal eccentric distance sum. In addition, we characterize the extremal trees with given diameter and minimal eccentric distance sum.     

On the Laplacian coefficients of bicyclic graphs

Let G be a graph of order n and let be the characteristic polynomial of its Laplacian matrix. Generalizing the approach in [D. Stevanovi?, A. Ili?, On the Laplacian coefficients of unicyclic graphs, Linear Algebra and its Applications 430 (2009) 2290-2300.] on graph transformations, we show that among all bicyclic graphs of order n, the kth coefficient c_k is smallest when the graph is B_n (obtained from C₄ by adding one edge connecting two non-adjacent vertices and adding n−4 pendent vertices attached to the vertex of degree 3).     

单圈图和双圈图的最大无符号拉普拉斯分离度

设G是一个n阶简单图,q_{1}(G)\geq q_{2}(G)\geq \cdots \geq q_{n}(G)是其无符号拉普拉斯特征值. 图G的无符号拉普拉斯分离度定义为S_{Q}(G)=q_{1}(G)-q_{2}(G). 确定了n阶单圈图和双圈图的最大的无符号拉普拉斯分离度,并分别刻画了相应的极图.     

On the Laplacian spectral radii of bicyclic graphs

A graph G of order n is called a bicyclic graph if G is connected and the number of edges of G is n+1. Let B(n) be the set of all bicyclic graphs on n vertices. In this paper, we obtain the first four largest Laplacian spectral radii among all the graphs in the class B(n) (n≥7) together with the corresponding graphs.     

Degree complete graphs

Ryser [Combinatorial Mathematics, Carus Mathematical Monograph, vol. 14, Wiley, New York, 1963] introduced a partially ordered relation ‘?’ on the nonnegative integral vectors. It is clear that if S=(s₁,s₂,…,s_n) is an out-degree vector of an orientation of a graph G with vertices 1,2,…,n, then

(Π)     

Some results on the spectral radii of bicyclic graphs

A bicyclic graph is a connected graph in which the number of edges equals the number of vertices plus one. Let Δ(G) and ρ(G) denote the maximum degree and the spectral radius of a graph G, respectively. Let B(n) be the set of bicyclic graphs on n vertices, and B(n,Δ)={G∈B(n)∣Δ(G)=Δ}. When Δ≥(n+3)/2 we characterize the graph which alone maximizes the spectral radius among all the graphs in B(n,Δ). It is also proved that for two graphs G₁ and G₂ in B(n), if Δ(G₁)>Δ(G₂) and Δ(G₁)≥⌈7n/9⌉+9, then ρ(G₁)>ρ(G₂).     

Matching energy of unicyclic and bicyclic graphs with a given diameter

Gutman and Wagner proposed the concept of matching energy (ME) and pointed out that the chemical applications of ME go back to the 1970s. Let G be a simple graph of order n and be the roots of its matching polynomial. The ME of G is defined to be the sum of the absolute values of . In this article, we characterize the graphs with minimal ME among all unicyclic and bicyclic graphs with a given diameter d. © 2014 Wiley Periodicals, Inc. Complexity 21: 224–238, 2015     

Q‐integral unicyclic,bicyclic and tricyclic graphs

A graph is called Q‐integral if its signless Laplacian spectrum consists of integers. In this paper, we characterize a class of k‐cyclic graphs whose second smallest signless Laplacian eigenvalue is less than one. Using this result we determine all the Q‐integral unicyclic, bicyclic and tricyclic graphs.     

Strong chromatic index of unit distance graphs

The strong chromatic index of a graph , denoted by , is defined as the least number of colors in a coloring of edges of , such that each color class is an induced matching (or: if edges and have the same color, then both vertices of are not adjacent to any vertex of ). A graph is a unit distance graph in if vertices of can be uniquely identified with points in , so that is an edge of if and only if the Euclidean distance between the points identified with and is 1. We would like to find the largest possible value of , where is a unit distance graph (in and ) of maximum degree . We show that , where is a unit distance graph in of maximum degree . We also show that the maximum possible size of a strong clique in unit distance graph in is linear in and give a tighter result for unit distance graphs in the plane.     

On the excess of vertex-transitive graphs of given degree and girth

We consider a restriction of the well-known Cage Problem to the class of vertex-transitive graphs, and consider the problem of finding the smallest vertex-transitive $k$-regular graphs of girth $g$. Counting cycles to obtain necessary arithmetic conditions on the parameters $(k,g)$, we extend previous results of Biggs, and prove that, for any given excess $e$ and any given degree $k\ge 4$, the asymptotic density of the set of girths $g$ for which there exists a vertex-transitive $(k,g)$-cage with excess not exceeding $e$ is 0.     

On extremal unicyclic molecular graphs with maximal Hosoya index

Let G be a unicyclic n-vertex graph and Z(G) be its Hosoya index, let F_n stand for the nth Fibonacci number. It is proved in this paper that Z(G)≤F_n+1+F_n−1 with the equality holding if and only if G is isomorphic to C_n, the n-vertex cycle, and that if G≠C_n then Z(G)≤F_n+1+2F_n−3 with the equality holding if and only if G=Q_n or D_n, where graph Q_n is obtained by pasting one endpoint of a 3-vertex path to a vertex of C_n−2 and D_n is obtained by pasting one endpoint of an (n−3)-vertex path to a vertex of C₄.     

Integral distance graphs

Suppose D is a subset of all positive integers. The distance graph G(Z, D) with distance set D is the graph with vertex set Z, and two vertices x and y are adjacent if and only if |x − y| ≡ D. This paper studies the chromatic number χ(Z, D) of G(Z, D). In particular, we prove that χ(Z, D) ≤ |D| + 1 when |D| is finite. Exact values of χ(G, D) are also determined for some D with |D| = 3. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 287–294, 1997