On eigenvectors of mixed graphs with exactly one nonsingular cycle

Let G be a mixed graph. The eigenvalues and eigenvectors of G are respectively defined to be those of its Laplacian matrix. If G is a simple graph, [M. Fiedler: A property of eigenvectors of nonnegative symmetric matrices and its applications to graph theory, Czechoslovak Math. J. 25 (1975), 619–633] gave a remarkable result on the structure of the eigenvectors of G corresponding to its second smallest eigenvalue (also called the algebraic connectivity of G). For G being a general mixed graph with exactly one nonsingular cycle, using Fiedler’s result, we obtain a similar result on the structure of the eigenvectors of G corresponding to its smallest eigenvalue. Supported by National Natural Science Foundation of China (10601001), Anhui Provincial Natural Science Foundation (050460102), NSF of Department of Education of Anhui province (2004kj027), the project of innovation team on basic mathematics of Anhui University, and the project of talents group construction of Anhui University.     

Acyclic edge coloring of subcubic graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and it is denoted by a^′(G). From a result of Burnstein it follows that all subcubic graphs are acyclically edge colorable using five colors. This result is tight since there are 3-regular graphs which require five colors. In this paper we prove that any non-regular connected graph of maximum degree 3 is acyclically edge colorable using at most four colors. This result is tight since all edge maximal non-regular connected graphs of maximum degree 3 require four colors.     

Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors

We study how the spectral gap of the normalized Laplacian of a random graph changes when an edge is added to or removed from the graph. There are known examples of graphs where, perhaps counter‐intuitively, adding an edge can decrease the spectral gap, a phenomenon that is analogous to Braess's paradox in traffic networks. We show that this is often the case in random graphs in a strong sense. More precisely, we show that for typical instances of Erd?s‐Rényi random graphs G (n, p ) with constant edge density , the addition of a random edge will decrease the spectral gap with positive probability, strictly bounded away from zero. To do this, we prove a new delocalization result for eigenvectors of the Laplacian of G (n, p ), which might be of independent interest. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 584–611, 2017     

Acyclic edge coloring of 2‐degenerate graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a′(G). A graph is called 2‐degenerate if any of its induced subgraph has a vertex of degree at most 2. The class of 2‐degenerate graphs properly contains series–parallel graphs, outerplanar graphs, non ? regular subcubic graphs, planar graphs of girth at least 6 and circle graphs of girth at least 5 as subclasses. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a′(G)?Δ + 2, where Δ = Δ(G) denotes the maximum degree of the graph. We prove the conjecture for 2‐degenerate graphs. In fact we prove a stronger bound: we prove that if G is a 2‐degenerate graph with maximum degree Δ, then a′(G)?Δ + 1. © 2010 Wiley Periodicals, Inc. J Graph Theory 69: 1–27, 2012     

The generalized acyclic edge chromatic number of random regular graphs

The r‐acyclic edge chromatic number of a graph is defined to be the minimum number of colors required to produce an edge coloring of the graph such that adjacent edges receive different colors and every cycle C has at least min(|C|, r) colors. We show that (r ? 2)d is asymptotically almost surely (a.a.s.) an upper bound on the r‐acyclic edge chromatic number of a random d‐regular graph, for all constants r ≥ 4 and d ≥ 2. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 101–125, 2006     

Acyclic edge colourings of graphs with large girth

An edge colouring of a graph G is called acyclic if it is proper and every cycle contains at least three colours. We show that for every , there exists a such that if G has maximum degree Δ and girth at least g then G admits an acyclic edge colouring with colours. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 511–533, 2017     

The signless Laplacian spectra of the corona and edge corona of two graphs

We give complete information about the signless Laplacian spectrum of the corona of a graph G ₁ and a regular graph G ₂, and complete information about the signless Laplacian spectrum of the edge corona of a connected regular graph G ₁ and a regular graph G ₂.     

A note on acyclic edge coloring of complete bipartite graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic (2-colored) cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a^′(G). Let Δ=Δ(G) denote the maximum degree of a vertex in a graph G. A complete bipartite graph with n vertices on each side is denoted by K_n,n. Alon, McDiarmid and Reed observed that a^′(K_p−1,p−1)=p for every prime p. In this paper we prove that a^′(K_p,p)≤p+2=Δ+2 when p is prime. Basavaraju, Chandran and Kummini proved that a^′(K_n,n)≥n+2=Δ+2 when n is odd, which combined with our result implies that a^′(K_p,p)=p+2=Δ+2 when p is an odd prime. Moreover we show that if we remove any edge from K_p,p, the resulting graph is acyclically Δ+1=p+1-edge-colorable.     

Eigenvectors of random graphs: Nodal Domains

We initiate a systematic study of eigenvectors of random graphs. Whereas much is known about eigenvalues of graphs and how they reflect properties of the underlying graph, relatively little is known about the corresponding eigenvectors. Our main focus in this article is on the nodal domains associated with the different eigenfunctions. In the analogous realm of Laplacians of Riemannian manifolds, nodal domains have been the subject of intensive research for well over a hundred years. Graphical nodal domains turn out to have interesting and unexpected properties. Our main theorem asserts that there is a constant c such that for almost every graph G, each eigenfunction of G has at most two large nodal domains, and in addition at most c exceptional vertices outside these primary domains. We also discuss variations of these questions and briefly report on some numerical experiments which, in particular, suggest that almost surely there are just two nodal domains and no exceptional vertices. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 39–58, 2011     

On edge domination numbers of graphs

Let and be the signed edge domination number and signed star domination number of G, respectively. We prove that holds for all graphs G without isolated vertices, where n=|V(G)|?4 and m=|E(G)|, and pose some problems and conjectures.     

A new upper bound for the independence number of edge chromatic critical graphs

In 1968, Vizing conjectured that if G is a Δ‐critical graph with n vertices, then α(G)≤n/2, where α(G) is the independence number of G. In this paper, we apply Vizing and Vizing‐like adjacency lemmas to this problem and prove that α(G)<(((5Δ?6)n)/(8Δ?6))<5n/8 if Δ≥6. © 2010 Wiley Periodicals, Inc. J Graph Theory 68: 202‐212, 2011     

Semistrong edge coloring of graphs

Weakening the notion of a strong (induced) matching of graphs, in this paper, we introduce the notion of a semistrong matching. A matching M of a graph G is called semistrong if each edge of M has a vertex, which is of degree one in the induced subgraph G[M]. We strengthen earlier results by showing that for the subset graphs and for the Kneser graphs the sizes of the maxima of the strong and semistrong matchings are equal and so are the strong and semistrong chromatic indices. Similar properties are conjectured for the n‐dimensional cube. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 39–47, 2005     

A note on mixed graphs and directed splitting off

We give counterexamples to two conjectures of Bill Jackson in Some remarks on arc-connectivity, vertex splitting, and orientation in graphs and digraphs (Journal of Graph Theory 12 (3):429–436, 1988) concerning orientations of mixed graphs and splitting off in digraphs, and prove the first conjecture in the (di-) Eulerian case(s). Beside that we solve a degree constrained non-uniform directed augmentation problem for di-Eulerian mixed graphs. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 213–221, 1998     

The size of edge chromatic critical graphs with maximum degree 6

In 1968, Vizing [Uaspekhi Mat Nauk 23 (1968) 117–134; Russian Math Surveys 23 (1968), 125–142] conjectured that for any edge chromatic critical graph with maximum degree , . This conjecture has been verified for . In this article, by applying the discharging method, we prove the conjecture for . © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 149–171, 2009     

关于混合图的谱扰动

本文刻画了如下的混合图:在添加一个环时,它恰有一个 Laplace特征值以整数增加,其它的 Laplace特征值保持不变.本文是文章[Linear Algebra and its Applications 374(2003):307-316]的一个延续性的文章.     

Group edge choosability of planar graphs without adjacent short cycles

In this paper,we prove that 2-degenerate graphs and some planar graphs without adjacent short cycles are group(Δ(G)+1)-edge-choosable,and some planar graphs with large girth and maximum degree are groupΔ(G)-edge-choosable.