The smallest values of algebraic connectivity for unicyclic graphs

The algebraic connectivity of G is the second smallest eigenvalue of its Laplacian matrix. Let U_n be the set of all unicyclic graphs of order n. In this paper, we will provide the ordering of unicyclic graphs in U_n up to the last seven graphs according to their algebraic connectivities when n≥13. This extends the results of Liu and Liu [Y. Liu, Y. Liu, The ordering of unicyclic graphs with the smallest algebraic connectivity, Discrete Math. 309 (2009) 4315-4325] and Guo [J.-M. Guo, A conjecture on the algebraic connectivity of connected graphs with fixed girth, Discrete Math. 308 (2008) 5702-5711].     

A conjecture on the algebraic connectivity of connected graphs with fixed girth

In this paper, we completely solve a conjecture on the minimum algebraic connectivity of connected graphs with fixed girth (see [S. Fallat, S. Kirkland, Extremizing algebraic connectivity subject to graph theoretic constraints, Electron. J. Linear Algebra 3 (1998) 48-74]).     

The algebraic connectivity of lollipop graphs

Let C_n,g be the lollipop graph obtained by appending a g-cycle C_g to a pendant vertex of a path on n-g vertices. In 2002, Fallat, Kirkland and Pati proved that for and g?4, α(C_n,g)>α(C_n,g-1). In this paper, we prove that for g?4, α(C_n,g)>α(C_n,g-1) for all n, where α(C_n,g) is the algebraic connectivity of C_n,g.     

Laplacian integral graphs in S(a, b)

Let G_n,m be the family of graphs with n vertices and m edges, when n and m are previously given. It is well-known that there is a subset of G_n,m constituted by graphs G such that the vertex connectivity, the edge connectivity, and the minimum degree are all equal. In this paper, S(a, b)-classes of connected (a, b)-linear graphs with n vertices and m edges are described, where m is given as a function of a,b∈N/2. Some of them have extremal graphs for which the equalities above are extended to algebraic connectivity. These graphs are Laplacian integral although they are not threshold graphs. However, we do build threshold graphs in S(a, b).     

On the maximal eccentric connectivity indices of graphs

For a connected simple graph G, the eccentricity ec(v) of a vertex v in G is the distance from v to a vertex farthest from v, and d(v) denotes the degree of a vertex v. The eccentric connectivity index of G, denoted by ξc(G), is defined as v∈V(G)d(v)ec(v). In this paper, we will determine the graphs with maximal eccentric connectivity index among the connected graphs with n vertices and m edges(n ≤ m ≤ n + 4), and propose a conjecture on the graphs with maximal eccentric connectivity index among the connected graphs with n vertices and m edges(m ≥ n + 5).     

Acyclic edge coloring of graphs with large girths

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by χ’a(G), is the least number of colors such that G has an acyclic edge k-coloring. Let G be a graph with maximum degree Δ and girth g(G), and let 1≤r≤2Δ be an integer. In this paper, it is shown that there exists a constant c > 0 such that if g(G)≥cΔ r log(Δ2/r) then χa(G)≤Δ + r + 1, which generalizes the result of Alon et al. in 2001. When G is restricted to series-parallel graphs, it is proved that χ’a(G) = Δ if Δ≥4 and g(G)≥4; or Δ≥3 and g(G)≥5.     

The upper connected geodetic number and forcing connected geodetic number of a graph

For a connected graph G of order p≥2, a set S⊆V(G) is a geodetic set of G if each vertex v∈V(G) lies on an x-y geodesic for some elements x and y in S. The minimum cardinality of a geodetic set of G is defined as the geodetic number of G, denoted by g(G). A geodetic set of cardinality g(G) is called a g-set of G. A connected geodetic set of G is a geodetic set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected geodetic set of G is the connected geodetic number of G and is denoted by g_c(G). A connected geodetic set of cardinality g_c(G) is called a g_c-set of G. A connected geodetic set S in a connected graph G is called a minimal connected geodetic set if no proper subset of S is a connected geodetic set of G. The upper connected geodetic number is the maximum cardinality of a minimal connected geodetic set of G. We determine bounds for and determine the same for some special classes of graphs. For positive integers r,d and n≥d+1 with r≤d≤2r, there exists a connected graph G with , and . Also, for any positive integers 2≤a<b≤c, there exists a connected graph G such that g(G)=a, g_c(G)=b and . A subset T of a g_c-set S is called a forcing subset for S if S is the unique g_c-set containing T. A forcing subset for S of minimum cardinality is a minimum forcing subset of S. The forcing connected geodetic number of S, denoted by f_c(S), is the cardinality of a minimum forcing subset of S. The forcing connected geodetic number of G, denoted by f_c(G), is f_c(G)=min{f_c(S)}, where the minimum is taken over all g_c-sets S in G. It is shown that for every pair a,b of integers with 0≤a≤b−4, there exists a connected graph G such that f_c(G)=a and g_c(G)=b.     

On total colorings of some special 1-planar graphs

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, we verify the total coloring conjecture for every 1-planar graph G if either Δ(G) ≥ 9 and g(G) ≥ 4, or Δ(G) ≥ 7 and g(G) ≥ 5, where Δ(G) is the maximum degree of G and g(G) is the girth of G.     

On a conjecture of the Randi? index

The Randi? index of a graph G is defined as , where d(u) is the degree of vertex u and the summation goes over all pairs of adjacent vertices u, v. A conjecture on R(G) for connected graph G is as follows: R(G)≥r(G)−1, where r(G) denotes the radius of G. We proved that the conjecture is true for biregular graphs, connected graphs with order n≤10 and tricyclic graphs.     

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.     

Unicyclic graphs with bicyclic inverses

A graph is nonsingular if its adjacency matrix A(G) is nonsingular. The inverse of a nonsingular graph G is a graph whose adjacency matrix is similar to A(G)^?1 via a particular type of similarity. Let H denote the class of connected bipartite graphs with unique perfect matchings. Tifenbach and Kirkland (2009) characterized the unicyclic graphs in H which possess unicyclic inverses. We present a characterization of unicyclic graphs in H which possess bicyclic inverses.     

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.     

A note on path kernels and partitions

The detour order of a graph G, denoted by τ(G), is the order of a longest path in G. A subset S of V(G) is called a P_n-kernel of G if τ(G[S])≤n−1 and every vertex v∈V(G)−S is adjacent to an end-vertex of a path of order n−1 in G[S]. A partition of the vertex set of G into two sets, A and B, such that τ(G[A])≤a and τ(G[B])≤b is called an (a,b)-partition of G. In this paper we show that any graph with girth g has a P_n+1-kernel for every . Furthermore, if τ(G)=a+b, 1≤a≤b, and G has girth greater than , then G has an (a,b)-partition.     

Graham’s pebbling conjecture on product of thorn graphs of complete graphs

The pebbling number of a graph G, f(G), is the least n such that, no matter how n pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of pebbling moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Let p₁,p₂,…,p_n be positive integers and G be such a graph, V(G)=n. The thorn graph of the graph G, with parameters p₁,p₂,…,p_n, is obtained by attaching p_i new vertices of degree 1 to the vertex u_i of the graph G, i=1,2,…,n. Graham conjectured that for any connected graphs G and H, f(G×H)≤f(G)f(H). We show that Graham’s conjecture holds true for a thorn graph of the complete graph with every by a graph with the two-pebbling property. As a corollary, Graham’s conjecture holds when G and H are the thorn graphs of the complete graphs with every .     

On integral Cayley sum graphs

Let S be a subset of a finite abelian group G. The Cayley sum graph Cay⁺(G, S) of G with respect to S is a graph whose vertex set is G and two vertices g and h are joined by an edge if and only if g + h ∈ S. We call a finite abelian group G a Cayley sum integral group if for every subset S of G, Cay⁺(G, S) is integral i.e., all eigenvalues of its adjacency matrix are integers. In this paper, we prove that all Cayley sum integral groups are represented by Z₃ and Zn₂ ⁿ, n ≥ 1, where Z_k is the group of integers modulo k. Also, we classify simple connected cubic integral Cayley sum graphs.     

Connected Resolvability of Graphs

For an ordered set W = {w ₁, w ₂,..., w _k} of vertices and a vertex v in a connected graph G, the representation of v with respect to W is the k-vector r(v|W) = (d(v, w ₁), d(v, w ₂),... d(v, w _k)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations with respect to W. A resolving set for G containing a minimum number of vertices is a basis for G. The dimension dim(G) is the number of vertices in a basis for G. A resolving set W of G is connected if the subgraph 〈W〉 induced by W is a nontrivial connected subgraph of G. The minimum cardinality of a connected resolving set in a graph G is its connected resolving number cr(G). Thus 1 ≤ dim(G) ≤ cr(G) ≤ n?1 for every connected graph G of order n ≥ 3. The connected resolving numbers of some well-known graphs are determined. It is shown that if G is a connected graph of order n ≥ 3, then cr(G) = n?1 if and only if G = K _n or G = K _1,n?1. It is also shown that for positive integers a, b with a ≤ b, there exists a connected graph G with dim(G) = a and cr(G) = b if and only if $\left( {a,b} \right) \notin \left\{ {\left( {1,k} \right):k = 1\;{\text{or}}\;k \geqslant 3} \right\}$ Several other realization results are present. The connected resolving numbers of the Cartesian products G × K ₂ for connected graphs G are studied.     

The connectivity of large digraphs and graphs

This paper studies the relation between the connectivity and other parameters of a digraph (or graph), namely its order n, minimum degree δ, maximum degree Δ, diameter D, and a new parameter l_pi;, 0 ≤ π ≤ δ ? 2, related with the number of short paths (in the case of graphs l₀ = ?(g ? 1)/2? where g stands for the girth). For instance, let G = (V,A) be a digraph on n vertices with maximum degree Δ and diameter D, so that n ≤ n(Δ, D) = 1 + Δ + Δ ² + … + Δ^D (Moore bound). As the main results it is shown that, if κ and λ denote respectively the connectivity and arc-connectivity of G, . Analogous results hold for graphs. © 1993 John Wiley & Sons, Inc.     

Circular game chromatic number of graphs

In a circular r-colouring game on G, Alice and Bob take turns colouring the vertices of G with colours from the circle S(r) of perimeter r. Colours assigned to adjacent vertices need to have distance at least 1 in S(r). Alice wins the game if all vertices are coloured, and Bob wins the game if some uncoloured vertices have no legal colour. The circular game chromatic number χ_cg(G) of G is the infimum of those real numbers r for which Alice has a winning strategy in the circular r-colouring game on G. This paper proves that for any graph G, , where is the game colouring number of G. This upper bound is shown to be sharp for forests. It is also shown that for any graph G, χ_cg(G)≤2χ_a(G)(χ_a(G)+1), where χ_a(G) is the acyclic chromatic number of G. We also determine the exact value of the circular game chromatic number of some special graphs, including complete graphs, paths, and cycles.     

Extra edge connectivity and isoperimetric edge connectivity

An edge set S of a connected graph G is a k-extra edge cut, if G-S is no longer connected, and each component of G-S has at least k vertices. The cardinality of a minimum k-extra edge cut, denoted by λ_k(G), is the k-extra edge connectivity of G. The kth isoperimetric edge connectivity γ_k(G) is defined as , where ω(U) is the number of edges with one end in U and the other end in . Write β_k(G)=min{ω(U):U⊂V(G),|U|=k}. A graph G with is said to be γ_k-optimal.In this paper, we first prove that λ_k(G)=γ_k(G) if G is a regular graph with girth g?k/2. Then, we show that except for K_3,3 and K₄, a 3-regular vertex/edge transitive graph is γ_k-optimal if and only if its girth is at least k+2. Finally, we prove that a connected d-regular edge-transitive graph with d?6e_k(G)/k is γ_k-optimal, where e_k(G) is the maximum number of edges in a subgraph of G with order k.     

Tough Ramsey Graphs Without Short Cycles

A graph G is t-tough if any induced subgraph of it with x > 1 connected components is obtained from G by deleting at least tx vertices. It is shown that for every t and g there are t-tough graphs of girth strictly greater than g. This strengthens a recent result of Bauer, van den Heuvel and Schmeichel who proved the above for g = 3, and hence disproves in a strong sense a conjecture of Chvátal that there exists an absolute constant t ₀ so that every t ₀-tough graph is pancyclic. The proof is by an explicit construction based on the tight relationship between the spectral properties of a regular graph and its expansion properties. A similar technique provides a simple construction of triangle-free graphs with independence number m on (m ^4/3) vertices, improving previously known explicit constructions by Erdös and by Chung, Cleve and Dagum.