On the spectral spread of bicyclic graphs with given girth

The spectral spread of a graph is defined to be the difference between the largest and the least eigenvalue of the adjacency matrix of the graph. A graph G is said to be bicyclic, if G is connected and |E(G)| = |V(G)|+ 1. Let B(n, g) be the set of bicyclic graphs on n vertices with girth g. In this paper some properties about the least eigenvalues of graphs are given, by which the unique graph with maximal spectral spread in B(n, g) is determined.     

5连通图中的可去边

An edge e of a k-connected graph G is said to be a removable edge if G O e is still k-connected, where G e denotes the graph obtained from G by deleting e to get G - e, and for any end vertex of e with degree k - 1 in G- e, say x, delete x, and then add edges between any pair of non-adjacent vertices in NG-e （x）. The existence of removable edges of k-connected graphs and some properties of 3-connected and 4-connected graphs have been investigated [1, 11, 14, 15]. In the present paper, we investigate some properties of 5-connected graphs and study the distribution of removable edges on a cycle and a spanning tree in a 5- connected graph. Based on the properties, we proved that for a 5-connected graph G of order at least 10, if the edge-vertex-atom of G contains at least three vertices, then G has at least （3│G│ ＋ 2）/2 removable edges.     

Removable edges in a spanning tree of a k-connected graph

An edge e of a k-connected graph G is said to be a removable edge if G O e is still k-connected, where G O e denotes the graph obtained from G by the following way： deleting e to get G - e, and for any end vertex of e with degree k - 1 in G - e, say x, deleting x, and then adding edges between any pair of non-adjacent vertices in NG-e （x）. The existence of removable edges of k-connected graphs and some properties of k-connected graphs have been investigated. In the present paper, we investigate the distribution of removable edges on a spanning tree of a k-connected graph （k ≥ 4）.     

Graphs with vertex rainbow connection number two

An edge colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. A vertex colored graph G is vertex rainbow connected if any two vertices are connected by a path whose internal vertices have distinct colors. The vertex rainbow connection number of G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G vertex rainbow connected. In 2011, Kemnitz and Schiermeyer considered graphs with rc(G) = 2.We investigate graphs with rvc(G) = 2. First, we prove that rvc(G) 2 if |E(G)|≥n-22 + 2, and the bound is sharp. Denote by s(n, 2) the minimum number such that, for each graph G of order n, we have rvc(G) 2provided |E(G)|≥s(n, 2). It is proved that s(n, 2) = n-22 + 2. Next, we characterize the vertex rainbow connection numbers of graphs G with |V(G)| = n, diam(G)≥3 and clique number ω(G) = n- s for 1≤s≤4.     

双圈图的Laplace谱跨度

The Laplacian spread of a graph is defined to be the difference between the largest eigenvalue and the second smallest eigenvalue of the Laplacian matrix of the graph. In our recent work, we have determined the graphs with maximal Laplacian spreads among all trees of fixed order and among all unicyclic graphs of fixed order, respectively. In this paper, we continue the work on Laplacian spread of graphs, and prove that there exist exactly two bicyclic graphs with maximal Laplacian spread among all bicyclic graphs of fixed order, which are obtained from a star by adding two incident edges and by adding two nonincident edges between the pendant vertices of the star, respectively.     

图的无符号拉普拉斯和距离无符号拉普拉斯特征值

Let G be a simple graph. We first show that ■, where δiand di denote the i-th signless Laplacian eigenvalue and the i-th degree of vertex in G, respectively.Suppose G is a simple and connected graph, then some inequalities on the distance signless Laplacian eigenvalues are obtained by deleting some vertices and some edges from G. In addition, for the distance signless Laplacian spectral radius ρQ(G), we determine the extremal graphs with the minimum ρQ(G) among the trees with given diameter, the unicyclic and bicyclic graphs with given girth, respectively.     

关于一些图类的L(1,2)-边标号

For a graph G and two positive integers j and k, an m-L(j, k)-edge-labeling of G is an assignment on the edges to the set {0,..., m}, such that adjacent edges receive labels differing by at least j, and edges which are distance two apart receive labels differing by at least k. The λ′j,k-number of G is the minimum m of an m-L(j, k)-edge-labeling admitted by G.In this article, we study the L(1, 2)-edge-labeling for paths, cycles, complete graphs, complete multipartite graphs, infinite ?-regular trees and wheels.     

The Rainbow Vertex-disconnection in Graphs

Let G be a nontrivial connected and vertex-colored graph. A subset X of the vertex set of G is called rainbow if any two vertices in X have distinct colors. The graph G is called rainbow vertex-disconnected if for any two vertices x and y of G, there exists a vertex subset S of G such that when x and y are nonadjacent, S is rainbow and x and y belong to different components of G-S; whereas when x and y are adjacent, S + x or S + y is rainbow and x and y belong to different components of(G-xy)-S. For a connected graph G, the rainbow vertex-disconnection number of G, denoted by rvd(G), is the minimum number of colors that are needed to make G rainbow vertexdisconnected. In this paper, we characterize all graphs of order n with rainbow vertex-disconnection number k for k ∈ {1, 2, n}, and determine the rainbow vertex-disconnection numbers of some special graphs. Moreover, we study the extremal problems on the number of edges of a connected graph G with order n and rvd(G) = k for given integers k and n with 1 ≤ k ≤ n.     

A characterization of PM-compact Hamiltonian bipartite graphs

The perfect matching polytope of a graph G is the convex hull of the incidence vectors of all perfect matchings in G. A graph is called perfect matching compact(shortly, PM-compact), if its perfect matching polytope has diameter one. This paper gives a complete characterization of simple PM-compact Hamiltonian bipartite graphs. We first define two families of graphs, called the H2C-bipartite graphs and the H23-bipartite graphs, respectively. Then we show that, for a simple Hamiltonian bipartite graph G with |V(G)| ≥ 6, G is PM-compact if and only if G is K3,3, or G is a spanning Hamiltonian subgraph of either an H2C-bipartite graph or an H23-bipartite graph.     

L（1, 2）-edge-labelings for lattices

For a graph G and two positive integers j and k, an m-L(j, k)-edge-labeling of G is an assignment on the edges to the set {0, 1, 2,..., m}, such that adjacent edges which receive labels differ at least by j, and edges which are distance two apart receive labels differ at least by kThe λ j,k-number of G is the minimum m such that an m-L(j, k)-edge-labeling is admitted by GIn this article, the L(1, 2)-edge-labeling for the hexagonal lattice, the square lattice and the triangular lattice are studied, and the bounds for λ j,k-numbers of these graphs are obtained.     

Deleting Vertices and Interlacing Laplacian Eigenvalues

The authors obtain an interlacing relation between the Laplacian spectra of a graph G and its subgraph G - U, which is obtained from G by deleting all the vertices in the vertex subset U together with their incident edges. Also, some applications of this interlacing property are explored and this interlacing property is extended to the edge weighted graphs.     

图的循环带宽和

Abstract. Let G be a simple graph. The cyclic bandwidth sum problem is to determine a labeling of graph G in a cycle such that the total length of edges is as small as possible. In this paper, some upper and lower bounds on cyclic bandwidth sum of graphs are studied.     

INDEPENDENT-SET-DELETABLE FACTOR-CRITICAL POWER GRAPHS

It is said that a graph G is independent-set-deletable factor-critical (in short, ID-factor-critical), if, for every independent set 7 which has the same parity as |V(G)|, G-I has a perfect matching. A graph G is strongly IM-extendable, if for every spanning supergraph H of G, every induced matching of H is included in a perfect matching of H. The k-th power of G, denoted by Gk, is the graph with vertex set V(G) in which two vertices are adjacent if and only if they have distance at most k in G. ID-factor-criticality and IM-extendability of power graphs are discussed in this article. The author shows that, if G is a connected graph, then G3 and T(G) (the total graph of G) are ID-factor-critical, and G4 (when |V(G)| is even) is strongly IM-extendable; if G is 2-connected, then D2 is ID-factor-critical.     

Edge Partition of Graphs Embeddable in the Projective Plane and the Klein Bottle

In a previous paper by the author joint with Baogang XU published in Discrete Math in 2018, we show that every non-planar toroidal graph can be edge partitioned into a planar graph and an outerplanar graph. This edge partition then implies some results in thickness and outerthickness of toroidal graphs. In particular, if each planar graph has outerthickness at most $2$ (conjectured by Chartrand, Geller and Hedetniemi in 1971 and the confirmation of the conjecture was announced by Gon\c{c}alves in 2005), then the outerthickness of toroidal graphs is at most 3 which is the best possible due to $K_7$. In this paper we continue to study the edge partition for projective planar graphs and Klein bottle embeddable graphs. We show that (1) every non-planar but projective planar graph can be edge partitioned into a planar graph and a union of caterpillar trees; and (2) every non-planar Klein bottle embeddable graph can be edge partitioned into a planar graph and a subgraph of two vertex amalgamation of a caterpillar tree with a cycle with pendant edges. As consequences, the thinkness of projective planar graphs and Klein bottle embeddabe graphs are at most $2$, which are the best possible, and the outerthickness of these graphs are at most $3$.     

赋权图的w密度和w平衡性

The notion of w-density for the graphs with positive weights on vertices and nonnegative weights on edges is introduced. A weighted graph is called w-balanced if its w-density is no less than the w-density of any subgraph of it. In this paper,a good characterization of w-balanced weighted graphs is given. Applying this characterization ,many large w-balanced weighted graphs are formed by combining smaller ones. In the case where a graph is not w-balanced,a polynomial-time algorithm to find a subgraph of maximum w-density is proposed. It is shown that the w-density theory is closely related to the study of SEW(G,w) games.     

Neighbor sum distinguishing edge coloring of subcubic graphs

A proper edge-k-coloring of a graph G is a mapping from E(G) to {1, 2,..., k} such that no two adjacent edges receive the same color. A proper edge-k-coloring of G is called neighbor sum distinguishing if for each edge uv ∈ E(G), the sum of colors taken on the edges incident to u is different from the sum of colors taken on the edges incident to v. Let χ_Σ'(G) denote the smallest value k in such a coloring of G. This parameter makes sense for graphs containing no isolated edges(we call such graphs normal). The maximum average degree mad(G) of G is the maximum of the average degrees of its non-empty subgraphs. In this paper, we prove that if G is a normal subcubic graph with mad(G) 5/2,then χ_Σ'(G) ≤ 5. We also prove that if G is a normal subcubic graph with at least two 2-vertices, 6 colors are enough for a neighbor sum distinguishing edge coloring of G, which holds for the list version as well.     

Vertex-distinguishing IE-total Colorings of Complete Bipartite Graphs K8,n

Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. For each vertex x of G, let C(x) be the set of colors of vertex x and edges incident to x under f. For an IE-total coloring f of G using k colors, if C(u) 6= C(v) for any two different vertices u and v of G, then f is called a k-vertex-distinguishing IE-total-coloring of G or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χievt(G) and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. The VDIET colorings of complete bipartite graphs K8,n are discussed in this paper. Particularly, the VDIET chromatic number of K8,n are obtained.     

Number of Induced Matchings of Graphs

A matching M of a graph G is an induced matching if no two edges in M arejoined by an edge of G.Let iz(G) denote the total number of induced matchings of G,named iz-index.It is well known that the Hosoya index of a graph is the total number of matchings and the Hosoya index of a path can be calculated by the Fibonacci sequence.In this paper,we investigate the iz-index of graphs by using the Fibonacci-Narayana sequence and characterize some types of graphs with minimum and maximum iz-index,respectively.     

混合图的Hermitian邻接矩阵的零维数

A mixed graph means a graph containing both oriented edges and undirected edges. The nullity of the Hermitian-adjacency matrix of a mixed graph G, denoted by ηH(G),is referred to as the multiplicity of the eigenvalue zero. In this paper, for a mixed unicyclic graph G with given order and matching number, we give a formula on ηH(G), which combines the cases of undirected and oriented unicyclic graphs and also corrects an error in Theorem 4.2 of [Xueliang LI, Guihai YU. The skew-rank of oriented graphs. Sci. Sin. Math., 2015, 45:93-104(in Chinese)]. In addition, we characterize all the n-vertex mixed graphs with nullity n-3, which are determined by the spectrum of their Hermitian-adjacency matrices.