Old and new results on algebraic connectivity of graphs

This paper is a survey of the second smallest eigenvalue of the Laplacian of a graph G, best-known as the algebraic connectivity of G, denoted a(G). Emphasis is given on classifications of bounds to algebraic connectivity as a function of other graph invariants, as well as the applications of Fiedler vectors (eigenvectors related to a(G)) on trees, on hard problems in graphs and also on the combinatorial optimization problems. Besides, limit points to a(G) and characterizations of extremal graphs to a(G) are described, especially those for which the algebraic connectivity is equal to the vertex connectivity.     

The game of arboricity

Using a fixed set of colors C, Ann and Ben color the edges of a graph G so that no monochromatic cycle may appear. Ann wins if all edges of G have been colored, while Ben wins if completing a coloring is not possible. The minimum size of C for which Ann has a winning strategy is called the game arboricity of G, denoted by A_g(G). We prove that A_g(G)?3k for any graph G of arboricity k, and that there are graphs such that A_g(G)?2k-2. The upper bound is achieved by a suitable version of the activation strategy, used earlier for the vertex coloring game. We also provide two other strategies based on induction and acyclic colorings.     

Graphs determined by their generalized characteristic polynomials

For a given graph G with (0, 1)-adjacency matrix A_G, the generalized characteristic polynomial of G is defined to be ?_G=?_G(λ,t)=det(λI-(A_G-tD_G)), where I is the identity matrix and D_G is the diagonal degree matrix of G. In this paper, we are mainly concerned with the problem of characterizing a given graph G by its generalized characteristic polynomial ?_G. We show that graphs with the same generalized characteristic polynomials have the same degree sequence, based on which, a unified approach is proposed to show that some families of graphs are characterized by ?_G. We also provide a method for constructing graphs with the same generalized characteristic polynomial, by using GM-switching.     

On the reduced signless Laplacian spectrum of a degree maximal graph

For a (simple) graph G, the signless Laplacian of G is the matrix A(G)+D(G), where A(G) is the adjacency matrix and D(G) is the diagonal matrix of vertex degrees of G; the reduced signless Laplacian of G is the matrix Δ(G)+B(G), where B(G) is the reduced adjacency matrix of G and Δ(G) is the diagonal matrix whose diagonal entries are the common degrees for vertices belonging to the same neighborhood equivalence class of G. A graph is said to be (degree) maximal if it is connected and its degree sequence is not majorized by the degree sequence of any other connected graph. For a maximal graph, we obtain a formula for the characteristic polynomial of its reduced signless Laplacian and use the formula to derive a localization result for its reduced signless Laplacian eigenvalues, and to compare the signless Laplacian spectral radii of two well-known maximal graphs. We also obtain a necessary condition for a maximal graph to have maximal signless Laplacian spectral radius among all connected graphs with given numbers of vertices and edges.     

Connected graphs with maximal Q-index: The one-dominating-vertex case

By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. For every pair of positive integers n,k, it is proved that if 3?k?n-3, then H_n,k, the graph obtained from the star K_1,n-1 by joining a vertex of degree 1 to k+1 other vertices of degree 1, is the unique connected graph that maximizes the largest signless Laplacian eigenvalue over all connected graphs with n vertices and n+k edges.     

Independence and coloring properties of direct products of some vertex-transitive graphs

Let α(G) and χ(G) denote the independence number and chromatic number of a graph G, respectively. Let G×H be the direct product graph of graphs G and H. We show that if G and H are circular graphs, Kneser graphs, or powers of cycles, then α(G×H)=max{α(G)|V(H)|,α(H)|V(G)|} and χ(G×H)=min{χ(G),χ(H)}.     

The spectral radius of graphs without paths and cycles of specified length

Let G be a graph with n vertices and μ(G) be the largest eigenvalue of the adjacency matrix of G. We study how large μ(G) can be when G does not contain cycles and paths of specified order. In particular, we determine the maximum spectral radius of graphs without paths of given length, and give tight bounds on the spectral radius of graphs without given even cycles. We also raise a number of open problems.     

Sharp bounds for the largest eigenvalue of the signless Laplacian of a graph

Let G be a simple connected graph with n vertices and m edges. Denote the degree of vertex v_i by d(v_i). The matrix Q(G)=D(G)+A(G) is called the signless Laplacian of G, where D(G)=diag(d(v₁),d(v₂),…,d(v_n)) and A(G) denote the diagonal matrix of vertex degrees and the adjacency matrix of G, respectively. Let q₁(G) be the largest eigenvalue of Q(G). In this paper, we first present two sharp upper bounds for q₁(G) involving the maximum degree and the minimum degree of the vertices of G and give a new proving method on another sharp upper bound for q₁(G). Then we present three sharp lower bounds for q₁(G) involving the maximum degree and the minimum degree of the vertices of G. Moreover, we determine all extremal graphs which attain these sharp bounds.     

The bondage numbers of graphs with small crossing numbers

The bondage number b(G) of a nonempty graph G is the cardinality of a smallest edge set whose removal from G results in a graph with domination number greater than the domination number γ(G) of G. Kang and Yuan proved b(G)?8 for every connected planar graph G. Fischermann, Rautenbach and Volkmann obtained some further results for connected planar graphs. In this paper, we generalize their results to connected graphs with small crossing numbers.     

Dominating direct products of graphs

An upper bound for the domination number of the direct product of graphs is proved. It in particular implies that for any graphs G and H, γ(G×H)?3γ(G)γ(H). Graphs with arbitrarily large domination numbers are constructed for which this bound is attained. Concerning the upper domination number we prove that Γ(G×H)?Γ(G)Γ(H), thus confirming a conjecture from [R. Nowakowski, D.F. Rall, Associative graph products and their independence, domination and coloring numbers, Discuss. Math. Graph Theory 16 (1996) 53-79]. Finally, for paired-domination of direct products we prove that γ_pr(G×H)?γ_pr(G)γ_pr(H) for arbitrary graphs G and H, and also present some infinite families of graphs that attain this bound.     

A sharp upper bound on algebraic connectivity using domination number

Let G be a connected graph of order n. The algebraic connectivity of G is the second smallest eigenvalue of the Laplacian matrix of G. A dominating set in G is a vertex subset S such that each vertex of G that is not in S is adjacent to a vertex in S. The least cardinality of a dominating set is the domination number. In this paper, we prove a sharp upper bound on the algebraic connectivity of a connected graph in terms of the domination number and characterize the associated extremal graphs.     

Cycle extendability in graphs and digraphs

In 1990, Hendry conjectured that all chordal Hamiltonian graphs are cycle extendable, that is, the vertices of each non-Hamiltonian cycle are contained in a cycle of length one greater. Let A be a symmetric (0,1)-matrix with zero main diagonal such that A is the adjacency matrix of a chordal Hamiltonian graph. Hendry’s conjecture in this case is that every k×k principle submatrix of A that dominates a full cycle permutation k×k matrix is a principle submatrix of a (k+1)×(k+1) principle submatrix of A that dominates a (k+1)×(k+1) full cycle permutation matrix. This article generalizes the concept of cycle-extendability to S-extendable; that is, with S⊆{1,2,…,n} and G a graph on n vertices, G is S-extendable if the vertices of every non-Hamiltonian cycle are contained in a cycle length i greater, where i∈S. We investigate this concept in directed graphs and in particular tournaments, i.e., anti-symmetric matrices with zero main diagonal.     

On conjectures involving second largest signless Laplacian eigenvalue of graphs

Let G=(V,E) be a simple graph. Denote by D(G) the diagonal matrix of its vertex degrees and by A(G) its adjacency matrix. Then the Laplacian matrix of G is L(G)=D(G)-A(G) and the signless Laplacian matrix of G is Q(G)=D(G)+A(G). In this paper we obtain a lower bound on the second largest signless Laplacian eigenvalue and an upper bound on the smallest signless Laplacian eigenvalue of G. In [5], Cvetkovi? et al. have given a series of 30 conjectures on Laplacian eigenvalues and signless Laplacian eigenvalues of G (see also [1]). Here we prove five conjectures.     

Maximum generic nullity of a graph

For a graph G of order n, the maximum nullity of G is defined to be the largest possible nullity over all real symmetric n×n matrices A whose (i,j)th entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. Maximum nullity and the related parameter minimum rank of the same set of matrices have been studied extensively. A new parameter, maximum generic nullity, is introduced. Maximum generic nullity provides insight into the structure of the null-space of a matrix realizing maximum nullity of a graph. It is shown that maximum generic nullity is bounded above by edge connectivity and below by vertex connectivity. Results on random graphs are used to show that as n goes to infinity almost all graphs have equal maximum generic nullity, vertex connectivity, edge connectivity, and minimum degree.     

On the hole index of L(2,1)-labelings of r-regular graphs

An L(2,1)-labeling of a graph G is an assignment of nonnegative integers to the vertices of G so that adjacent vertices get labels at least distance two apart and vertices at distance two get distinct labels. A hole is an unused integer within the range of integers used by the labeling. The lambda number of a graph G, denoted λ(G), is the minimum span taken over all L(2,1)-labelings of G. The hole index of a graph G, denoted ρ(G), is the minimum number of holes taken over all L(2,1)-labelings with span exactly λ(G). Georges and Mauro [On the structure of graphs with non-surjective L(2,1)-labelings, SIAM J. Discrete Math. 19 (2005) 208-223] conjectured that if G is an r-regular graph and ρ(G)?1, then ρ(G) must divide r. We show that this conjecture does not hold by providing an infinite number of r-regular graphs G such that ρ(G) and r are relatively prime integers.     

Radius-edge-invariant and diameter-edge-invariant graphs

The eccentricity e(v) of v is the distance to a farthest vertex from v. The radius r(G) is the minimum eccentricity among the vertices of G and the diameter d(G) is the maximum eccentricity. For graph G−e obtained by deleting edge e in G, we have r(G−e)?r(G) and d(G−e)?d(G). If for all e in G, r(G−e)=r(G), then G is radius-edge-invariant. Similarly, if for all e in G, d(G−e)=d(G), then G is diameter-edge-invariant. In this paper, we study radius-edge-invariant and diameter-edge-invariant graphs and obtain characterizations of radius-edge-invariant graphs and diameter-edge-invariant graphs of diameter two.     

On the nullity of tricyclic graphs

The nullity of a graph G, denoted by η(G), is the multiplicity of the eigenvalue zero in its spectrum. It is known that η(G)?n-2 if G is a simple graph on n vertices and G is not isomorphic to nK₁. The extremal graphs attaining the upper bound n-2 and the second upper bound n-3 have been obtained. In this paper, the graphs with nullity n-4 are characterized. Furthermore the tricyclic graphs with maximum nullity are discussed.     

Characteristic polynomial of a generalized complete product of matrices

For a simple graph G, let denote the complement of G relative to the complete graph and let P_G(x)=det(xI-A(G)) where A(G) denotes the adjacency matrix of G. The complete product G∇H of two simple graphs G and H is the graph obtained from G and H by joining every vertex of G to every vertex of H. In [2]P_G∇H(x) is represented in terms of P_G, , P_H and . In this paper we extend the notion of complete product of simple graphs to that of generalized complete product of matrices and obtain their characteristic polynomials.     

Zeta functions of line, middle, total graphs of a graph and their coverings

We consider the (Ihara) zeta functions of line graphs, middle graphs and total graphs of a regular graph and their (regular or irregular) covering graphs. Let L(G), M(G) and T(G) denote the line, middle and total graph of G, respectively. We show that the line, middle and total graph of a (regular and irregular, respectively) covering of a graph G is a (regular and irregular, respectively) covering of L(G), M(G) and T(G), respectively. For a regular graph G, we express the zeta functions of the line, middle and total graph of any (regular or irregular) covering of G in terms of the characteristic polynomial of the covering. Also, the complexities of the line, middle and total graph of any (regular or irregular) covering of G are computed. Furthermore, we discuss the L-functions of the line, middle and total graph of a regular graph G.     

Maximum nullity of outerplanar graphs and the path cover number

Let G=(V,E) be a graph with V={1,2,…,n}. Define S(G) as the set of all n×n real-valued symmetric matrices A=[a_ij] with a_ij≠0,i≠j if and only if ij∈E. By M(G) we denote the largest possible nullity of any matrix A∈S(G). The path cover number of a graph G, denoted P(G), is the minimum number of vertex disjoint paths occurring as induced subgraphs of G which cover all the vertices of G.There has been some success with relating the path cover number of a graph to its maximum nullity. Johnson and Duarte [5], have shown that for a tree T,M(T)=P(T). Barioli et al. [2], show that for a unicyclic graph G,M(G)=P(G) or M(G)=P(G)-1. Notice that both families of graphs are outerplanar. We show that for any outerplanar graph G,M(G)?P(G). Further we show that for any partial 2-path G,M(G)=P(G).